Первой и наиболее известной криптографической системой с открытым ключом была предложенная в 1978 году так называемая система RSA. Ее название происходит от первых букв фамилий авторов Rivest, Shamir и Aldeman, которые придумали ее во время совместных исследований в Массачусетском технологическом институте в 1977 году. Она основана на трудности разложения очень больших целых чисел на простые сомножители. Международная сеть электронного перечисления платежей SWIFT уже требует от банковских учреждений, пользующихся ее услугами, применения именно этой криптографической системы. Алгоритм ее работает так:

. Отправитель выбирает два очень больших простых числа Р и Q и вычисляет два произведения N=PQ и M=(P-1)(Q-1).

. Затем он выбирает случайное целое число D, взаимно простое с М, и вычисляет Е, удовлетворяющее условию DE = 1 MOD М.

. После этого он публикует D и N как свой открытый ключ шифрования, сохраняя Е как закрытый ключ.

. Если S - сообщение, длина которого, определяемая по значению выражаемого им целого числа, должна быть в интервале (1, N), то оно превращается в шифровку возведением в степень D по модулю N и отправляется получателю S'=(S**D) MOD N.

. Получатель сообщения расшифровывает его, возводя в степень Е по модулю N, так как S = (S'**E) MOD N = (S**(D*E)) MOD N.

Таким образом, открытым ключом служит пара чисел N и D, а секретным ключом число Е. Смысл этой системы шифрования становится прозрачным, если упомянуть про малую теорему Ферма, которая утверждает, что при простом числе Р и любом целом числе К, которое меньше Р, справедливо тождество К**(P-1)=1 MOD Р. Эта теорема позволяет определять, является ли какое-либо число простым или же составным.

Приведем простой пример на малых простых числах Р=211 и Q=223. В этом случае N=47053 и М=46620. Выберем открытый ключ шифрования D=16813 и вычислим секретный ключ расшифровывания Е= 19837. Теперь, взяв за сообщение название метода RSA, переведем его в число. Для этого будем считать букву R равной 18, S равной 19, А равной 1 по порядковому номеру их положения в английском алфавите. На представление каждой буквы отведем по 5 бит числа, представляющего открытый текст. В этом случае слову RSA соответствует следующее число:=((1*32)+19)*32+18=1650

С помощью открытого ключа получаем шифровку:

S'=(S**D) MOD N=1650**16813 MOD 47053=3071

Получатель расшифровывает ее с помощью секретного ключа:

S = (S'**E) MOD N=3071**19837 MOD 47053=1650

Авторы RSA в примере из своей первой публикации использовали D=9007 и N=11438162575788886766923577997614661201021829672124236256256184 29357069352457338978305971235639587050589890751475992900268795 43541.

Приняв за исходный открытый текст фразу из "Юлия Цезаря" Шекспира: ITS ALL GREEK TO ME, представленную целым числом S=920190001121200071805051100201501305, они получили такую шифровку'=1999351314978051004523171227402606474232040170583914631037037174062597160894892750439920962672582675012893554461353823769748026.

Зачем приведены эти длинные наборы цифр, взятые из книги американского математика Мартина Гарднера, читатель узнает ниже. Криптостойкость системы RSA основана на том, что М не может быть просто вычислена без знания простых сомножителей Р и Q, а нахождение этих сомножителей из N считалась трудно разрешимой задачей. Однако недавние работы по разложению больших чисел на сомножители показали, что для этого могут быть использованы разные и даже совершенно неожиданные средства. Сначала авторы RSA предлагали выбрать простые числа Р и Q случайно, по 50 десятичных знаков каждое. Считалось, что такие большие числа очень трудно разложить на простые сомножители при криптоанализе. Райвест полагал, что разложение на простые множители числа из почти что 130 десятичных цифр, приведенного в их публикации, потребует более 40 квадриллионов лет машинного времени. Но математики Ленстра из фирмы Bellcore и Манасси из фирмы DEC разложили число из 155 десятичных цифр на простые сомножители всего за 6 недель, соединив для этого 1000 ЭВМ, находящихся в разных странах мира. Выбранное число, называемое девятым числом Ферма, с 1983 года находилось в списке чисел, разложение которых считалось наиболее желательным. Это число взято потому, что оно считалось неразложимым при существующей вычислительной технике и достаточно большим для того, чтобы его можно считать безопасным для формирования N в RSA. Как заявил Ленстра, ведущий в Bellcore исследования по электронной защите информации и разложению больших чисел, их целью было показать разработчикам и пользователям криптографических систем, с какими угрозами они могут встретиться и насколько осторожны должны быть при выборе алгоритмов шифрования. По мнению Ленстра и Манасси, их работа компрометирует и создает большую угрозу применениям криптографических систем RSA. Перейти на страницу: 1 2

Другие статьи по теме

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

Микропроцессорный тахометр Развитие микроэлектроники и широкое ее применение в промышленном производстве, в устройствах и системах управления самыми разнообразными объектами и процессами является в настоящее время ...

Цифровизация участка первичной сети связи Развитие науки и техники способствовало развитию телекоммуникационных сетей как всего мира, так и Украины. Передача мультимедийного трафика на первичной сети связи Украины осуществляется ...