Криптографическая система с открытым ключом Ривеста — Шамира — Алдемана (RSA)

Криптографическая система с открытым ключом Ривеста — Шамира — Алдемана (RSA)

Криптографическая система с открытым ключом Ривеста — Шамира — Алдемана (RSA). Она основана на трудности разложения очень больших целых чисел на простые сомножители. Алгоритм ее работы предусматривает следующие действия:

1.    Источник сообщения выбирает два очень больших простых числа p и q и вычисляет два произведения , а также некоторое целое число d, взаимно простое с m. На основе этой тройки он вычисляет е

2.    Число е сохраняется в секрете, a d и e сообщаются всем абонентам как открытый ключ шифрования (публикуются в справочнике вроде телефонного).

3.    Сообщение С, длина которого, определяемого по длине выражаемого им целого числа, находится в интервале [1;n], преобразуется в шифрограмму по правилу

4.    Получатель сообщения расшифровывает его, возводя шифровку в степень e по модулю n

Авторы RSA в примере из своей первой публикации использовали d=9007 и n= 1143816257578888676692357799761466120102182967212423625625618429357 069352457338978305971235639587050589 8907514 7599290026879543541. Но для иллюстрации работы алгоритма шифрации RSA  рассматривается более простой пример на малых простых числах р= 211 и q= 223. В этом случае n = 47053 и m = 46620. При выборе открытого ключа шифрования d= 6813 вычисляется секретный ключ расшифровки е= 19837. Теперь, взяв за сообщение название метода RSA, его следует перевести в число. Для этого будем буквам латинского алфавита ставить в соответствие их порядковые номера. Поэтому R:= 18, S:= 19, А:= 1. На двоичное представление каждой буквы отводится по 5 бит, как в коде Бодо.

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

Криптостойкость системы RSA основана на том, что m не может быть просто вычислена без знания простых сомножителей p и q, а нахождение этих сомножителей из n считалось трудно разрешимой задачей. Однако недавние работы по разложению больших чисел на сомножители показали, что для этого могут быть использованы разные и даже совершенно неожиданные средства. Сначала авторы RSA предлагали выбрать простые числа р и q случайно, по 50 десятичных знаков каждое. Считалось, что такие большие числа очень трудно разложить на простые сомножители при криптоанализе. Оказалось, что это не так.

Теперь разработчикам криптографических алгоритмов с открытым ключом на базе RSA приходится избегать применения разложимых чисел длиной менее 200 десятичных разрядов. Самые последние публикации предлагают для этого применять числа в 250 и даже 300 десятичных разрядов. А так как для шифрования каждого блока информации приходится соответствующее число возводить в колоссально большую степень по модулю n, то для современных компьютеров это задача на грани возможного. Поэтому для практической реализации шифрования RSA приходится разрабатывать специальные процессоры. Чрезвычайно слабое быстродействие криптографических систем на основе RSA лишь ограничивает область применения, но вовсе не перечеркивает их ценность.

Яндекс.Метрика