Математики, шпионы и хакеры. Кодирование и криптография | страница 54
Пытаясь найти новые, более эффективные алгоритмы, Диффи придумал систему, в которой ключ для шифрования отличается от ключа, используемого для расшифровки, и, следовательно, они никак не могут быть получены один из другого.
В этой теоретической системе отправитель имеет два ключа: для шифрования и для расшифровки. Из этих двух отправитель делает открытым только первый, чтобы любой человек, желающий отправить ему сообщение, мог зашифровать его. Получив это сообщение, отправитель расшифрует его, используя второй ключ, который, конечно, останется в тайне. Возможно ли использовать такие системы на практике?
Простые числа спешат на помощь: алгоритм шифрования RSA
В августе 1977 г. знаменитый американский писатель и популяризатор науки Мартин Гарднер озаглавил свою колонку по занимательной математике в журнале Scientific American так: «Новый вид шифра, на расшифровку которого потребуются миллионы лет». После объяснения принципа системы шифрования с открытым ключом он показал само зашифрованное сообщение и открытый ключ N, используемый в этом шифре:
Гарднер призвал читателей попробовать расшифровать сообщение, используя предоставленную информацию, и даже дал подсказку: для решения необходимо разложить число N на простые множители р и q. Более того, Гарднер назначил приз в размере $100 (приличная сумма на тот момент) тому, кто первым получит правильный ответ. Каждый, кто захочет побольше узнать о шифре, писал Гарднер, может обратиться к создателям шифра — Рону Ривесту, Ади Шамиру и Лену Адлеману из Лаборатории информации Массачусетского технологического института.
Правильный ответ был получен лишь через 17 лет. Он стал результатом сотрудничества более чем 600 человек. Ключами оказались р = 32769132993266 709549961988190834461413177642967992942539798288533 и q = 3490529510847650949147849619903898133417764638493387843990820577, а зашифрованная фраза звучала так: «Волшебные слова — это брезгливый ягнятник».
Алгоритм, представленный Гарднером, известен как RSA — буквенная аббревиатура от фамилий Rivest (Ривест), Shamir (Шамир) и Adleman (Адлеман). Это первое практическое применение придуманной Диффи системы шифрования с открытым ключом, которая повсеместно используется и по сей день. Надежность ее практически гарантирована, потому что процесс расшифровки является невероятно сложным, почти невозможным делом. Далее мы рассмотрим основы этой системы в упрощенной форме.
Подробнее об алгоритме RSA
