Кpиптогpафия от папиpуса до компьютеpа



Шифр Ривеста-Шамира-Алдемана - часть 2


S=((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, они получили такую шифровку

S'=199935131497805100452317122740260647423204017058391463103703
     717406259716089489275043992096267258267501289355446135382376
     9748026.

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




Содержание  Назад  Вперед