23. Ассиметричные криптосистемы.

Асимметричные криптосистемы (системы открытого шифрования, с открытым ключом, public key systems) разр в сер 560 годов, изложен в 76- смысл данных криптосистем состоит в том, что для зашифрования и расшифрования используются разные преобразования. Одно из них - зашифрование - является абсолютно открытым для всех. Другое же - расшифрование - остается секретным. Таким образом, любой, кто хочет что-либо зашифровать, пользуется открытым преобразованием. Но расшифровать и прочитать это сможет лишь тот, кто владеет секретным преобразованием.

Асимметричная криптография изначально задумана как средство передачи сообщений от одного объекта к другому.

Основное ее достоинство: пропадает проблема передачи секретного ключа (как у симметричных систем).

Открытый и секретный ключ связаны между собой, но получить секретный ключ, зная открытый, практически невозможно.

Наибольшее распространение и практическое применение нашла схема шифрования с открытым ключом RSA. Алгоритм RSA защищен патентом США N 4405829. Разработан в 1978 году в Массачусетском технологическом институте (США). Получил название по первым буквам фамилий авторов: Рон Райверст (Rivest), Ади Шамир (Shamir) и Лен Адлеман (Adleman). Криптостойкость основана на вычислительной сложности задачи разложении большого числа на простые множители.

Алгоритм ELGamal разработан в 1985 году. Назван по фамилии автора - Эль-Гамаль. Используется в стандарте США на цифровую подпись DSS (Digital Signature Standard). Криптостойкость основана на вычислительной сложности задачи логарифмирования целых чисел в конечных полях.

Совсем недавно появился подход, который может составить конкуренцию RSA – криптография на основе эллиптических кривых (ECC – Elliptic curve cryptography). Привлекательность подхода состоит в том, что по сравнению с RSA, эквивалентная защита может быть достигнута при меньшей длине ключа, что существенно уменьшает вычислительные затраты.\

. С = Eku(M), M = Dkr(C). У каждого пользователя имеется секретный ключ и открытый.

24. Алгоритм rsa

Основан на разложении большего числа на простые числа. На первом этапе необходимо определить ключи, которые будут использоваться.

1) выбираются простые большие числа p,q.

2) вычисляем произведение.

3) вычисляется функция Эйлера Э(n) = (p-1)(q-1).

4) выбирается число Е (1 < E < Э(n)), такое что НОД = 1, т.е число и значение функции взаимопросты. Если есть 2 числа, С явл делителем А и В, то любой делитель А и В является делителем С. НОД можно выбрать из простых чисел, при этом число должно быть меньше чем значение функции Эйлера и не явл его делителем.

5) Из уравнения с*d =1 mod Э(n) находят число с. A=BmodN → A mod N = B mod N. Для того чтобы решить уравнение можно воспользоваться следующим равенством с*d =к Э(n) + 1, приэтом подбирая значения К можно найти d, при этом оно должно оставаться целым и меньшим чем функция Эйлера.

6) открытый ключ KU ={e,n}. Закрытый ключ KR = {d,n}. Рекомендации по выбору откр и закр ключа. Длина ключа выбирается из диапазона 1024-2048 бит. Значения p и q не должны сильно различаться по величине и должны попадать в диапазон 10⁷⁵ – 10¹⁰⁰. Числа p-1 и q-1 должны содержать в своих разложениях достаточно простой большой множитель.

ПРОЦЕДУРА ЗАШИФРОВАНИЯ.

1. Отправитель разбивает свое сообщение на отдельные блоки по К бит. К = [Log₂(n)], [] - взятие целой части. Каждый блок может быть интерпретирован как число из диапазона 0-2^К-1. Величина n фактически ограничивается количеством различных символов в наборе открытого текста. Для каждого числа открытого текста вычисляется выражение Сi = (mi)^emod n. Для расшифрования – выражение Mi = (Ci)^dmod n. Так как криптосистема работает с большим числом и выполн медленная процедура возведения в степень, то применяют разл подходы для увеличения производительности, например число Е стараются выбирать большим, при этом естественный d становится громадным, а оно участвует в процедуре расшифрования. Применение небольшой Е приводит к проблемам по защите небольших сообщений.