Історія

Опублікована в листопаді 1976 року стаття Уітфілд Діффі і Мартіна Хеллмана «Нові напрямки в криптографії» перевернула уявлення про криптографічних системах, заклавши основи криптографії з відкритим ключем. Розроблений згодом алгоритм Діффі-Хеллмана-Меркле дозволяв двом сторонам одержати загальний секретний ключ, використовуючи незахищений канал зв'язку. Однак цей алгоритм не вирішував проблему аутентифікації. Без додаткових коштів, один з користувачів не міг бути впевнений, що він обмінявся ключами саме з тим користувачем, який йому був потрібний.

Вивчивши цю статтю, троє вчених Рональд Райвест (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 році [2], кількома місяцями пізніше в 1974 році Малькольм Вільямсон винайшов математичний алгоритм, заснований на комутативності зведення в ступінь, аналогічний алгоритму Діффі-Хеллмана-Меркле.