Асимметричные системы шифрования

Наиболее перспективными системами криптографической защиты данных являются системы с открытым ключом, который начали интенсивно развиваться с 1976 года, когда два американца Диффи и Хелман разработали основы использования двухключевой криптографии. В таких системах для шифрования данных используется один ключ, а для расшифровки другой. Первый ключ не является секретным и может быть опубликован для использования всеми пользователями системы, которые зашифровывают данные. Расшифровка данных с помощью известного ключа невозможна. Для расшифровки данных получатель зашифрованной информации использует второй ключ, который является секретным. Разумеется, ключ расшифровки не может быть определен из ключа шифрования. Использование двух ключей позволяет решить проблемы распространения ключей для абонентов, находящихся на географическом отдалении друг от друга.

Использование пары открытый/ закрытый ключ также используется для защиты документов от изменения с помощью криптографической контрольной суммы – цифровой подписи. Рассмотрим наиболее известные системы асимметричного шифрования.

Шифр Ривеста - Шамира – Алдемана RSA

Первой и наиболее известной криптографической системой с открытым ключом была предложенная в 1978 году система RSA. Ее название происходит от первых букв фамилий авторов Rivest, Shamir и Aldeman, которые придумали ее во время совместных исследований в Массачусетском Технологическом институте в 1977 году. Она основана на вычислительной сложности задачи разложения очень больших целых чисел на простые сомножители. Алгоритм ее работает следующим образом:

Генерация параметров метода

• 1.    Выбираем два больших простых числа p и q.

• 2.    Вычисляем N = p •q, и функцию Эйлера ^ (N ) = ⁽ p ^{- 1)} ’ ⁽ q ^{- 1)} (значение ^ ⁽ N ) равно количеству натуральных чисел k < N, взаимно простых с N).

• 3.    Находим число е, взаимно-простое с ^ ⁽ N ) ,

• 4.    Находим число d из условия наибольший общий делитель e ∙ d = 1 mod ^ ⁽ N ) . Для нахождения d используем расширенный алгоритм Евклида. Для этого решим в целых числах уравнение a ’ ^ ⁽ N) + b ’ e = ¹ . (*)

• 5.    Значение d положим равным найденному b. Если множитель b окажется меньшим нуля, следует заменить его на b + ^ ⁽ N ) .

Пара (N,e) объявляется открытым ключом и используется для шифрования. Параметр d является секретным и используется для расшифровки данных.

Шифрование

e

Шифрование производится по формуле y     od N, где x - код исходного символа. Обратное раскодирование производится по формуле x = у mod N, и основано на теореме Эйлера x = 1 mod N.

Проверим вычисление. Из формулы (*) e ’ d = ^{1 -} a ’ ^ ^{( N} ) получим

yd mod N = xed mod N = x1-a^(N) mod N = x .