Изучив  эту статью, трое ученых Рональд  Райвест (Ronald Linn Rivest), Ади Шамир (Adi Shamir) и Леонард Адлеман (Leonard Adleman) из Массачусетского  Технологического Института (MIT) приступили к поискам математической функции, которая бы позволяла реализовать сформулированную Уитфилдом Диффи и Мартином Хеллманом модель криптографической системы с открытым ключом. После работы над более чем 40 возможными вариантами, им удалось найти алгоритм, основанный на различии в том, насколько легко находить большие простые числа и насколько сложно раскладывать на множители произведение двух больших простых чисел, получивший впоследствии название RSA. Система была названа по первым буквам фамилий её создателей.

     Описание RSA было опубликовано в августе 1977 года в журнале Scientific American. Авторы RSA поддерживали идею её активного распространения. В свою очередь, Агентство национальной безопасности (США), опасаясь использования этого алгоритма в негосударственных структурах, на протяжении нескольких лет безуспешно требовало прекращения распространения системы. Ситуация порой доходила до абсурда — например, когда программист Адам Бек(Adam Back) описал алгоритм RSA на языке Perl, состоящий из пяти строк, правительство США запретило распространение этой программы за пределами страны. Люди, недовольные подобным ограничением, в знак протеста напечатали текст этой программы на своих футболках.

     В 1983 году MIT был выдан патент 4405829 США, срок действия которого истёк 21 сентября 2000 года.

     В 1977 году создателями RSA была зашифрована фраза «The Magic Words are Squeamish Ossifrage» («Волшебные слова — это брезгливый ягнятник»). За расшифровку была обещана награда в 100 долларов США. Лишь в конце 1995 года удалось практически реализовать раскрытие шифра RSA для 500-значного ключа. На протяжении полугода более 600 добровольцев жертвовали процессорное время 1600 машин (две из которых были факс-машинами). Координирование проходило через Интернет, и это был один из первых подобных проектов распределённых вычислений. Полученную награду победители пожертвовали в фонд свободного программного обеспечения.

     В декабре 1997 года была обнародована информация, согласно которой британский математик  Клиффорд Кокс (Clifford Cocks), работавший в  центре правительственной связи (GCHQ) Великобритании, описал аналогичную систему в 1973 году, несколькими месяцами позже в 1974 году Малькольм Вильямсон изобрел математический алгоритм, основанный на коммутативности возведения в степень, аналогичный алгоритму Диффи-Хеллмана-Меркле. 

     Алгоритм создания открытого и секретного ключей

     RSA-ключи  генерируются следующим образом:

• Выбираются два случайных простых числа p и q заданного размера (например, 1024 бита каждое).
• Вычисляется их произведение n = pq, которое называется модулем.
• Вычисляется значение функции Эйлера от числа n:
• Выбирается целое число e ( ), взаимно простое со значением функции . Обычно в качестве e берут простые числа, содержащие небольшое количество единичных битов в двоичной записи, например, простые числа Ферма 17, 257, или 65537.

     Число e называется открытой экспонентой.

     Время, необходимое для шифрования с  использованием быстрого возведения в  степень, пропорционально числу  единичных бит в e.

     Слишком малые значения e, например 3, потенциально могут ослабить безопасность схемы RSA.

• Вычисляется число d, обратное к числу e по модулю , то есть число, удовлетворяющее условию:

       или: , где k — некоторое целое число.

     Число d называется секретной экспонентой. 

     Шифрование и расшифрование

     Предположим, сторона  хочет послать стороне сообщение .

     Сообщением  являются целые числа лежащие  от до , т.е .

     

 

 

 

Пример

 

Хеш-функции.

     Хеширование — преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или дайджестом сообщения.

     Хеширование применяется для сравнения данных: если у двух массивов хеш-коды разные, массивы гарантированно различаются; если одинаковые — массивы, скорее всего, одинаковы. В общем случае однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше чем вариантов входного массива; существует множество массивов, дающих одинаковые хеш-коды — так называемые коллизии. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.

     Среди множества существующих хеш-функций принято выделять криптографически стойкие, применяемые в криптографии. Для того, чтобы хеш-функция H считалась криптографически стойкой, она должна удовлетворять трем основным требованиям, на которых основано большинство применений хеш-функций в криптографии:

1. Необратимость: для заданного значения хеш-функции m должно быть вычислительно неосуществимо найти блок данных X, для которого H(X) = m.
2. Стойкость к коллизиям первого рода: для заданного сообщения M должно быть вычислительно неосуществимо подобрать другое сообщение N, для которого H(N) = H(M).
3. Стойкость к коллизиям второго рода: должно быть вычислительно неосуществимо подобрать пару сообщений , имеющих одинаковый хеш.

 

     Следует отметить, что не доказано существование  необратимых хеш-функций, для которых вычисление какого-либо прообраза заданного значения хеш-функции теоретически невозможно. Обычно нахождение обратного значения является лишь вычислительно сложной задачей.

     Для криптографических хеш-функций также  важно, чтобы при малейшем изменении аргумента значение функции сильно изменялось (лавинный эффект). В частности, значение хеша не должно давать утечки информации даже об отдельных битах аргумента. Это требование является залогом криптостойкости алгоритмов хеширования, хеширующих пользовательский пароль для получения ключа.

     В 1993 году NSA совместно с NIST разработали  алгоритм безопасного хеширования (сейчас известный как SHA-0) (опубликован  в документе FIPS PUB 180) для стандарта безопасного хеширования. Однако вскоре NSA отозвало данную версию, сославшись на обнаруженную ими ошибку, которая так и не была раскрыта. И заменило его исправленной версией, опубликованной в 1995 году в документе FIPS PUB 180-1. Эта версия и считается тем, что называют SHA-1. Немного спустя, на конференции CRYPTO в 1998 году два французских исследователя представили атаку на алгоритм SHA-0, которая не работала на алгоритме SHA-1 Возможно, это и была ошибка, открытая NSA.

     SHA-1 реализует хеш-функцию, построенную  на идее функции сжатия. Входами  функции сжатия являются блок сообщения длиной 512 бит и выход предыдущего блока сообщения. Выход представляет собой значение всех хеш-блоков до этого момента. Иными словами хеш блока M_i равен h_i = f(M_i,h_{i − 1}). Хеш-значением всего сообщения является выход последнего блока.

       Исходное сообщение разбивается  на блоки по 512 бит в каждом. Последний блок дополняется до  длины, кратной 512 бит. Сначала  добавляется 1 а потом нули, чтобы  длина блока стала равной (512 - 64 = 448) бит. В оставшиеся 64 бита записывается длина исходного сообщения в битах. Если последний блок имеет длину более 448, но менее 512 бит, дополнение выполняется следующим образом: сначала добавляется 1, затем нули вплоть до конца 512-битного блока; после этого создается ещё один 512-битный блок, который заполняется вплоть до 448 бит нулями, после чего в оставшиеся 64 бита записывается длина исходного сообщения в битах. Дополнение последнего блока осуществляется всегда, даже если сообщение уже имеет нужную длину.

       Инициализируются пять 32-битовых  переменных:

     A = a = 0x67452301

     B = b = 0xEFCDAB89

     C = c = 0x98BADCFE

     D = d = 0x10325476

     E = e = 0xC3D2E1F0

       Определяются четыре нелинейные операции и четыре константы:

     Главный цикл итеративно обрабатывает каждый 512-битный блок. Итерация состоит из четырех этапов по двадцать операций в каждом. Блок сообщения преобразуется  из 16 32-битовых слов M_i в 80 32-битовых слов W_j по следующему правилу: 

     W_t = M_t                                      при 0≤t≤15 
W_t = (W_t-3 W_t-8 W_t-14 W_t-16) << 1     при 16≤t≤79 

     здесь << — это циклический сдвиг влево 

     для t от 0 до 79  
 temp = (a<<5) + F_t(b,c,d) + e + W_t + K_t    
 e = d  
 d = c  
 c = b<<30                                 
 b = a  
 a = temp

     После этого a, b, c, d, e прибавляются к A, B, C , D , E соответственно. Начинается следующая  итерация.

     Итоговым  значением будет объединение  пяти 32-битовых слов в одно 160-битное хеш-значение.

 

     ЭЦП. Схема Эль-Гамаля.

     Электро́нная  цифрова́я по́дпись (ЭЦП) — реквизит электронного документа, позволяющий установить отсутствие искажения информации в электронном документе с момента формирования ЭЦП и проверить принадлежность подписи владельцу сертификата ключа ЭЦП. Значение реквизита получается в результате криптографического преобразования информации с использованием закрытого ключа ЭЦП.