Читать «Золотой билет» онлайн - страница 77
Лэнс Фотноу
Допустим, Диффи хочет отправить Хеллману такое сообщение: «Наступление в полночь». Хеллман создает пару ключей; открытый ключ он посылает Диффи и другим заинтересованным участникам, а закрытый держит в тайне. С помощью открытого ключа Диффи зашифровывает сообщение «Наступление в полночь» и отправляет результат Хеллману. Секретный ключ ему знать не нужно, поскольку для шифрования он не используется. Хакер, перехвативший шифровку, не сможет восстановить исходный текст даже в том случае, если знает открытый ключ. А вот Хеллман с помощью закрытого ключа расшифрует сообщение и узнает о том, что наступление начинается в полночь.
Неужели можно шифровать сообщения ключом, который все знают?! Можно – но только если P и NP не равны: в противном случае закрытый ключ легко и быстро восстанавливается по открытому.
В 1976 году большинство ученых уже склонялись к тому, что P ≠ NP, а потому системы с открытым ключом имеют право на жизнь. Диффи и Хеллман такую систему предложили, однако более широкое распространение получила криптосистема RSA, которую в 1978 году разработали Рональд Ривест, Ади Шамир и Леонард Адлеман. Система была названа по первым буквам фамилий ее создателей – Rivest, Shamir, Adleman.
В основе алгоритма RSA лежит тот факт, что умножать легко, а раскладывать на множители – очень трудно. Возьмем, к примеру, два достаточно больших простых числа, 5754853343 и 2860486313. Найти их произведение легко: это 16461679220973794359. А вот с обратным процессом все обстоит гораздо сложнее – попробуйте-ка по числу 16461679220973794359 восстановить сомножители 5754853343 и 2860486313! В системе RSA используются громадные простые числа, состоящие, как правило, из нескольких сот цифр. Нельзя утверждать, что разложение на простые множители практически неразрешимо, пока неравенство классов P и NP остается недоказанным; однако по мнению ученых задача эта представляет огромную вычислительную трудность.
За свое изобретение Ривест, Шамир и Адлеман в 2002 году получили премию Тьюринга.
Удивительный факт: позднее выяснилось, что впервые подобную криптосистему описал в 1973 году Клиффорд Кокс, работавший в то время в Центре правительственной связи Великобритании. Эта информация была обнародована лишь в 1997 году.
С системой RSA вы наверняка неоднократно сталкиваетесь каждый день. Возьмем для примера какой-нибудь часто посещаемый веб-сайт (в вашем браузере он может отображаться немного по-другому).
Рис. 8.4. Верхняя часть страницы
Обратите внимание на букву
Рис. 8.5. Верхняя часть страницы
Буква
