2015-08-21
545
Начало асимметричным шифрам было положено в работе «Новые направления в современной криптографии» Уитфилда Диффи и Мартина Хеллмана, опубликованной в 1976 году. Находясь под влиянием работы Ральфа Меркле о распространении открытого ключа, они предложили метод получения секретных ключей, используя открытый канал. Этот метод экспоненциального обмена ключей, который стал известен как обмен ключами Диффи – Хеллмана, был первым опубликованным практичным методом для установления разделения секретного ключа между заверенными пользователями канала. В 2002 году Хеллман предложил называть данный алгоритм «Диффи – Хеллмана – Меркле», признавая вклад Меркле в изобретение криптографии с открытым ключом. Эта же схема была разработана Малькольмом Вильямсоном в 1970-х, но держалась в секрете до 1997 года. Метод Меркле по распространению открытого ключа был изобретён в 1974 и опубликован в 1978 году, его также называют загадкой Меркле.
Асимметричные методы используют два взаимосвязанных ключа: для шифрования и расшифрования. Один ключ является закрытым (секретным) и известным только получателю. Его используют для расшифрования. Второй из ключей является открытым (несекретным), т.е. он может спокойно передаваться по незащищенным каналам связи и быть опубликован, например, вместе с адресом пользователя. Его используют для выполнения шифрования.
Формально асимметричный метод можно описать следующим образом. Обозначим результат шифрования текста T с помощью открытого ключа – E(T), а результат расшифровки текста с помощью закрытого ключа - D(T). Тогда асимметричный метод должен отвечать следующим трем требованиям:
§ D(E(T)) = T;
§ D практически невозможно определить по E;
§ Е нельзя взломать.
Преимущество указанного метода состоит в уменьшении количества ключей, с которыми приходится оперировать. Однако данный алгоритм имеет существенный недостаток - требует значительной вычислительной мощности. Использование асимметричного метода шифрования представлено на Рис. 3.1.
Рис. 3.1. Использование асимметричного метода шифрования с открытым ключом.
В настоящее время наиболее известными и надежными являются следующие асимметричные алгоритмы:
§ алгоритм RSA (Rivest, Shamir, Adleman);
§ алгоритм Эль Гамаля (Elgamal);
§ ГОСТ Р 34.10-2001.
Алгоритм RSA принят в качестве следующих международных стандартов: ISO/IEC/DIS 9594-8 и X.509. Алгоритм использует факт, что нахождение больших (например, 100-битных) простых чисел в вычислительном отношении осуществляется легко, однако разложение на множители произведения двух таких чисел в вычислительном отношении представляется невыполнимым.
В настоящее время Международная сеть электронного перечисления платежей SWIFT требует от банковских учреждений, пользующихся ее услугами, применения именно этого алгоритма криптографического преобразования информации.
Алгоритм работает так:
1. Отправитель выбирает два очень больших простых числа P и Q и вычисляет два произведения N = PQ и M = (P-1)(Q-1).
2. Затем он выбирает случайное целое число D, взаимно простое с M, и вычисляет E, удовлетворяющее условию DE = 1 mod M.
3. После этого он публикует D и N как свой открытый ключ шифрования, сохраняя E как закрытый ключ.
4. Если S - сообщение, длина которого, определяемая по значению выражаемого им целого числа, должна быть в интервале (1, N), то оно превращается в шифровку возведением в степень D по модулю N и отправляется получателю S1 = SD mod N.
5. Получатель сообщения расшифровывает его, возводя в степень E по модулю N, так как S = S1E mod N = SDE mod N.
Таким образом, открытым ключом служит пара чисел N и D, а секретным ключом число E. Смысл этой системы шифрования основан на так называемой малой теореме Ферма, которая утверждает, что при простом числе P и любом целом числе K, которое меньше P, справедливо тождество KP-1 = 1 mod P. Эта теорема позволяет определить, является ли какое-либо число простым или составным.
