Алгоритм шифрования rsa. Пример алгоритма шифрования rsa

Рассмотрим работу асимметричного RSA . Он был предложен тремя математиками Рональдом Ривестом (R. Rivest ), Ади Шамиром (A. Shamir ) и Леонардом Адльманом (L. Adleman ) в 1978 году.

Под простым числом будем понимать такое число, которое делится только на 1 и на само себя. Эвклид в своих «Началах» показал, что для любого простого числа есть большее простое число, то есть количество простых чисел бесконечно.

Доказательство. Допустим, что существует наибольшее простое число p , определим произведение всех простых чисел P =2∙3∙5∙7∙…∙p .

Рассмотрим число P +1. Оно или само является простым числом большим p или произведением простых чисел, которые больше P . Мы пришли к противоречию, значит количество простых чисел бесконечно.

2∙3+1=7; 2∙3∙5+1=31; 2∙3∙5∙7+1=211;

2∙3∙5∙7∙11+1=2311; 2∙3∙5∙7∙11∙13+1=30031=59∙509.

Взаимно простыми числами будем называть такие числа, которые не имеют ни одного общего делителя, кроме 1 .

Наконец, под результатом операции i mod j будем считать остаток от целочисленного деления i на j. Чтобы использовать алгоритм RSA, надо сначала сгенерировать открытый и секретный ключи, выполнив следующие шаги.

1. Выберем два очень больших простых числа р и q .

2. Определим n как результат умножения р на q (n=p·q).

3. Выберем большое случайное число, которое назовем d . Это число должно быть взаимно простым с результатом умножения (р – 1) · (q – 1).

4. Определим такое число е , для которого является истинным следующее соотношение (е·d) mod ((p – 1) · (q – 1)) = 1.

5. Назовем открытым ключом числа е и n , а секретным ключом – числа d и n .

Теперь, чтобы зашифровать данные по известному ключу {е, n }, необходимо сделать следующее:

– разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа M(i) ;

– зашифровать текст, рассматриваемый как последовательность чисел M(i) по формуле С(i) = (M(i) e) mod n . Чтобы расшифровать эти данные, используя секретный ключ {d, n}, необходимо выполнить следующие вычисления: M(i)=(C(i) d) mod n . В результате будет получено множество чисел M(i), которые представляют собой исходный текст.

Алгоритм RSA основан на одной из доказанных теорем Эйлера, частный случай которой утверждает, что если число n представимо в виде двух простых чисел p и q , то для любого x имеет место равенство

x (p-1)(q-1) mod n = 1.

Для дешифрования RSA- сообщений воспользуемся этой формулой. Для этого возведем обе ее части в степень (-y ):

(x (- y)(p-1)(q-1)) mod n = 1 (- y) = 1.

Теперь умножим обе ее части на x:

(x (-y)(p-1)(q-1)+1) mod n = 1· x = x.

Вспомним теперь, как создавались открытый и закрытый ключи. Мы подбирали d такое, что

e·d+(p-1)(q-1) ·y = 1,

e·d = (-y)(p-1)(q-1)+1.

Следовательно, в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e·d). Получаем (x e · d) mod n = x . Для того чтобы прочесть сообщение c i = ((m i) e)mod n достаточно возвести его в степень d по модулю m :

((c i) d)mod n = ((m i) e · d) mod n = m i .

Приведем простой пример использования метода RSA для шифрования сообщения «CAB». Для простоты будем использовать очень маленькие числа (на практике используются большие числа).

1. Выберем р= 3и q= 11.

2. Определим n= 3· 11=33.

3. Найдем (р–1) (q–1)= 20. В качестве d выберем любое число, которое является взаимно простым с 20, например d= 3.

4. Выберем число е . В качестве такого числа может быть взято любое число, для которого удовлетворяется соотношение (е· 3) mod 20 = 1,
например 7.

5. Представим шифруемое сообщение как последовательность целых чисел в диапазоне 0...32. Пусть буква А изображается числом 1, буква В – числом 2, а буква С – числом 3. Тогда сообщение можно представить в виде последовательности чисел 312. Зашифруем сообщение, используя ключ {7, 33}:

С(1)=(З 7) mod 33 = 2187 mod 33 = 9,

С(2) = (1 7) mod 33 = 1 mod 33 = 1,

С(З) = (2 7) mod 33 = 128 mod 33 = 29.

6. Попытаемся расшифровать сообщение {9, 1, 29}, полученное в результате зашифровывания по известному ключу, на основе секретного ключа {3, 33}:

M(1) = (9 3) mod 33 = 729 mod 33 = 3,

М(2) = (1 3) mod 33 = 1 mod 33 = 1,

М(З) = (29 3) mod 33 = 24389 mod 33 = 2.

Таким образом, в результате расшифровывания сообщения получено исходное сообщение «CAB».

Криптостойкость алгоритма RSA основывается на предположении, что исключительно трудно определить секретный ключ по известному открытому, поскольку для этого необходимо решить задачу о существовании делителей целого числа. Данная задача не допускает в настоящее время эффективного (полиномиального) решения. В связи с этим для ключей, состоящих из 200 двоичных цифр (а именно такие числа рекомендуется использовать), традиционные методы поиска делителей требуют выполнения огромного числа операций (около 10 23).

Криптосистема RSA используется в самых различных платформах и во многих отраслях. Она встраивается во многие коммерческие продукты, число которых постоянно увеличивается. Ее используют операционные системы Microsoft, Apple, Sun и Novell. В аппаратном исполнении алгоритм RSA применяется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, широко используется в криптографическом оборудовании фирмы Zaxus (Rasal). Кроме того, алгоритм входит в состав всех основных протоколов для защищенных коммуникаций Internet, в том числе S/MIME, SSL и S/WAN, а также используется во многих учреждениях, например, в правительственных службах, в большинстве корпораций, в государственных лабораториях и университетах.

Технологию шифрования RSA BSAFE используют более 500 миллионов пользователей всего мира. Так как в большинстве случаев при этом используется алгоритм RSA, то его можно считать наиболее распространенной криптосистемой общего ключа в мире, и это количество имеет явную тенденцию к увеличению по мере роста пользователей Internet.

RSА использует два типа ключей - e и d , где e - открытый, a d - секретный. Предположим, что P - исходный текст и C - зашифрованный текст. Алиса использует C = P e mod n , чтобы создать зашифрованный текст C из исходного текста P ; Боб использует P = C d mod n , чтобы извлечь исходный текст (файл), переданный Алисой. Модулей n создается очень большое количество с помощью процесса генерации ключей, который мы обсудим позже.

Для шифрования и дешифрования применяют возведение в степень по модулю. Как мы уже обсуждали в лекциях 12-13, при использовании быстрого алгоритма возведение в степень по модулю выполнимо в полиномиальное время. Однако нахождение модульного логарифма так же сложно, как и разложение числа по модулю. Для него нет алгоритма с полиномиальным временем. Это означает, что Алиса может зашифровать сообщение общедоступным ключом (e) в полиномиальное время. Боб также может расшифровать его в полиномиальное время (потому что он знает d ). Но Ева не может расшифровать это сообщение, потому что она должна была бы вычислить корень e -той степени из C с использованием модульной арифметики. Рисунок 14.5 показывает идею RSA .

Рис. 14.5.

Другими словами, Алиса использует одностороннюю функцию (возведение в степень по модулю) с лазейкой, известной только Бобу. Ева не знает лазейку, поэтому не может расшифровать сообщение. Если когда-нибудь найдут полиномиальный алгоритм для модуля вычисления корня e -той степени из n , то возведение в степень по модулю n не будет больше односторонней функцией.

Процедура

Рисунок 14.6 показывает общую идею процедуры, используемой в RSA .

RSA использует возведение в степень по модулю для шифрования/дешифрования. Для того чтобы атаковать закрытый текст, Ева должна вычислить

Две алгебраические структуры

RSA использует две алгебраических структуры: кольцо и группу.

Кольца шифрования/дешифрования . Шифрование и дешифрование сделаны с использованием коммутативного кольца с двумя арифметическими операциями: сложение и умножение. В RSA это кольцо общедоступно, потому что модуль n общедоступен. Любой может послать сообщение Бобу, используя это кольцо для шифрования.

Группы генерирования ключей . RSA использует мультипликативную группу для генерации ключей. Группа поддерживает только умножение и деление (мультипликативную инверсию), которые необходимы для того, чтобы создать открытые и секретные ключи. Эту группу надо скрыть, потому что ее модуль является секретным. Мы увидим, что если Ева найдет этот модуль, она сможет легко атаковать криптографическую систему.

RSA использует две алгебраических структуры: открытое кольцо R = < Z n , +, x > и секретную группу G = < Z (n)* , x > .

Генерация ключей

Боб использует шаги, показанные в алгоритме 14.2 , чтобы создать свои открытый и секретный ключи. После генерации ключей Боб объявляет кортеж (e, n) как свой открытый ключ доступа: Боб сохраняет d как свой секретный ключ. Боб может отказаться от p, q и ; они не могут изменить его секретный ключ, не изменяя модуль. Для безопасности рекомендуется размер для каждого простого p или q - 512 бит (почти 154 десятичные цифры). Это определяет размер модуля, n 1024 бита (309 цифр).

В RSA кортеж (e, n) - открытый ключ доступа; целое число d - секретный ключ .

Шифрование

Передать сообщение Бобу может любой, используя его открытый ключ доступа. Шифрование в RSA может быть выполнено с использованием алгоритма с полиномиальной сложностью по времени, как показано в алгоритме 14.3 . Быстрый алгоритм возведения в степень был рассмотрен в лекциях 12-13. Размер исходного текста должен быть меньше чем n ; если размер исходного текста больше, то он должен быть разделен на блоки.

Криптосистема RSA на каждом такте шифрования преобразует двоичный блок открытого текста m длины size(n), рассматриваемый как целое число, в соответствии с формулой: c = m e (mod n).

При этом n = pq, где p и q - случайные простые числа большой разрядности, которые уничтожаются после формирования модуля и ключей. Открытый ключ состоит из пары чисел e и n. Подключ e выбирается как достаточно большое число из диапазона 1 < e < φ(n), с условием: НОД(e, j(n)) = 1, где j(n) - наименьшее общее кратное чисел p–1 и q–1. Далее, решая в целых числах x, y уравнение xe + yφ(n) = 1, полагается d = х, т.е. ed = 1(j(n)). При этом для всех m выполняется соотношение m ed = m(n), поэтому знание d позволяет расшифровывать криптограммы.

Чтобы гарантировать надежную защиту информации, к системам с открытым ключом предъявляются два следующих требования.

1. Преобразование исходного текста должно исключать его восстановление на основе открытого ключа.

2. Определение закрытого ключа на основе открытого также должно быть вычислительно нереализуемым. При этом желательна точная нижняя оценка сложности (количества операций) раскрытия шифра.

Алгоритмы шифрования с открытым ключом получили широкое распространение в современных информационных системах.

Рассмотрим построение криптосистемы RSA на простом примере.

1. Выберем p = 3 и q = 11.

2. Определим n = 3 ∙ 11 = 33.

3. Найдем j(n) = (p – 1)(q – 1) = 20.

5. Выберем число d, удовлетворяющее 7d = 1(mоd 20).

Легко увидеть, что d = 3(mоd 20).

Представим шифруемое сообщение как последовательность целых чисел с помощью соответствия: А = 1, B = 2, С = 3, ..., Z = 26. Поскольку size(n) = 6, то наша криптосистема в состоянии зашифровывать буквы латинского алфавита, рассматриваемые как блоки, Опубликуем открытый ключ (e, n) = (7, 33) и предложим прочим участникам системы секретной связи зашифровывать с его помощью сообщения, направляемые в наш адрес.Пусть такимсообщением будет CAB, которое в выбранном нами кодировке принимает вид (3, 1, 2).Отправитель должензашифроватькаждый блок и отправитьзашифрованное сообщение в наш адрес:

RSA(C) = RSA(3) = 3 7 = 2187 = 9(mod 33);
RSA(A) = RSA(1) = 1 7 = 1(mod 33);
RSA(B) = RSA(1) = 2 7 = 128 = 29(mod 33).

Получив зашифрованное сообщение (9, 1, 29), мы сможем его расшифровать на основе секретного ключа (d, n) = (3, 33), возводя каждый блок в степень d = 3:

9 3 = 729 = 3(mоd 33);
1 3 = 1(mоd 33);
29 3 = 24389 = 2(mоd 33).

Для нашего примера легко найти секретный ключ перебором. На практике это невозможно, т.к. для использования на практике рекомендуются в настоящее время следующие значения size(n):

· 512–768 бит - для частных лиц;

· 1024 бит - для коммерческой информации;

· 2048 бит- для секретной информации.

Пример реализации алгоритма RSA представлен в листингах 18.1 и 18.2 (компиляторы - Delphi, FreePascal).

Листинг 18.1. Пример реализации алгоритма RSA на языке Pascal

program Rsa;
{$APPTYPE CONSOLE}
{$IFDEF FPC}
{$MODE DELPHI}
{$ENDIF}

uses SysUtils, uBigNumber;

//Генератор случайных чисел

var t: array of Byte;
var pos: Integer;
var cbox: array of Byte =
(237, 240, 161, 1, 130, 141, 205, 98, 27, 169, 181, 202, 173, 47, 114, 224, 35, 183, 79, 82, 153, 220, 172, 22, 17, 11, 200, 131, 14, 154, 167, 91, 250, 31, 213, 112, 126, 241, 236, 155, 198, 96, 87, 143, 244, 151, 134, 38, 129, 233, 186, 101, 41, 94, 231, 115, 113, 199, 51, 145, 229, 37, 69, 180, 85, 33, 207, 163, 102, 187, 4, 89, 7, 44, 75, 88, 81, 120, 10, 232, 221, 168, 230, 158, 247, 211, 216, 156, 95, 64, 242, 215, 77, 165, 122, 5, 15, 119, 100, 43, 34, 48, 30, 39, 195, 222, 184, 92, 78, 135, 103, 166, 147, 32, 60, 185, 26, 251, 214, 90, 139, 45, 73, 150, 97, 116, 136, 68, 219, 248, 191, 192, 16, 8, 243, 50, 132, 105, 62, 201, 204, 65, 0, 99, 182, 121, 194, 108, 160, 170, 56, 226, 206, 254, 117, 178, 9, 197, 234, 127, 58, 171, 40, 29, 177, 142, 3, 228, 188, 162, 212, 157, 49, 175, 174, 140, 70, 106, 123, 66, 196, 246, 179, 42, 218, 71, 217, 227, 18, 164, 24, 67, 159, 25, 111, 255, 193, 245, 2, 238, 133, 21, 137, 152, 109, 148, 63, 124, 203, 104, 54, 55, 223, 80, 107, 210, 225, 149, 252, 76, 12, 189, 93, 46, 23, 13, 36, 209, 61, 249, 110, 144, 86, 52, 253, 72, 28, 53, 57, 125, 59, 235, 84, 128, 208, 146, 20, 74, 6, 239, 190, 83, 19, 138, 118, 176);

procedure InicMyRandom;
var i: Integer;
var s: string;
begin
WriteLn("Введите какой-либо текст для инициализации генератора
случайных чисел (до 256 символов):");
ReadLn(s);
i:= 1;
while (i<=255) and (i<=Length(s)) do

Введение 3

Основная часть 5

1История создания 5

2Описание алгоритма 5

2.1Создание ключей 6

2.2Шифрование и расшифрование 6

2.3Пример использования 7

Заключение 9

Список использованных источников 10

Введение

Криптография – специальная система изменения обычного письма, используемая с целью сделать текст понятным лишь для ограниченного числа лиц, знающих эту систему .

Криптография – наука о защите информации с использованием математических методов .

Современная криптография включает в себя:

симметричные криптосистемы;

асимметричные криптосистемы;

системы электронной цифровой подписи (ЭЦП);

хеш-функции;

управление ключами;

получение скрытой информации;

квантовая криптография.

Симметричное шифрование - симметричными называются алгоритмы, в которых для шифрования и дешифрования используется один и тот же (известный только отправителю и получателю) секретный ключ.

Распространенные алгоритмы симметричного шифрования:

AES (англ. Advanced Encryption Standard) - американский стандарт шифрования;

ГОСТ 28147-89 - отечественный стандарт шифрования данных;

DES (англ. Data Encryption Standard) - стандарт шифрования данных в США до AES;

3DES (Triple-DES, тройной DES);

IDEA (англ. International Data Encryption Algorithm);

SEED - корейский стандарт шифрования данных;

Camellia - сертифицированный для использовании в Японии шифр;

XTEA - наиболее простой в реализации алгоритм .

Асимметричные криптоалгоритмы призваны в первую очередь устранить основной недостаток симметричных криптосистем – сложность управления и распространения ключей.

Основой всех асимметричных криптоалгоритмов является большая вычислительная сложность восстановления открытого текста без знания закрытого ключа.

Примеры асимметричных криптоалгритмов:

Diffie-Hellmann;

RSA – Rivest, Shamir, Adelman – основан на сложности задачи разложения на множители больших чисел за короткое время;

DSA – Digital Signature algorithm, стандарт США;

ГОСТ Р 34.10 – 94, 2001, стандарты РФ .

В данном реферате подробно рассмотрим ассиметричный криптоалгоритм шифрования – алгоритм RSA.

Основная часть

Алгоритм RSA (буквенная аббревиатура от фамилий Rivest, Shamir и Adleman) – криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел. Криптосистема RSA стала первой системой, пригодной и для шифрования, и для цифровой подписи.

История создания

Опубликованная в ноябре 1976 года статья Уитфилда Диффи и Мартина Хеллмана «Новые направления в криптографии» перевернула представление о криптографических системах, заложив основы криптографии с открытым ключом. Разработанный впоследствии алгоритм Диффи - Хеллмана позволял двум сторонам получить общий секретный ключ, используя незащищенный канал связи. Однако этот алгоритм не решал проблему аутентификации. Без дополнительных средств пользователи не могли быть уверены, с кем именно они сгенерировали общий секретный ключ.

Изучив эту статью, трое учёных Рональд Ривест (англ. Ronald Linn Rivest), Ади Шамир (англ. Adi Shamir) и Леонард Адлеман (англ. Leonard Adleman) из Массачусетского Технологического Института (MIT) приступили к поискам математической функции, которая бы позволяла реализовать сформулированную Уитфилдом Диффи и Мартином Хеллманом модель криптографической системы с открытым ключом. После работы над более чем 40 возможными вариантами, им удалось найти алгоритм, основанный на различии в том, насколько легко находить большие простые числа и насколько сложно раскладывать на множители произведение двух больших простых чисел, получивший впоследствии название RSA. Система была названа по первым буквам фамилий её создателей.

Описание алгоритма

Первым этапом любого асимметричного алгоритма является создание пары ключей – открытого и закрытого и распространение открытого ключа "по всему миру".

Создание ключей

Для алгоритма RSA этап создания ключей состоит из следующих операций:

Число называется открытой экспонентой

Шифрование и расшифрование

Предположим, отправитель хочет послать получателю сообщение .

Сообщениями являются целые числа в интервале от 0 до , т.е. . На рисунке 1 представлена схема алгоритма RSA.

Рисунок 1 – Схема алгоритма RSA

Алгоритм Отправителя:

Алгоритм Получателя:

Уравнения (1) и (2), на которых основана схема RSA, определяют взаимно обратные преобразования множества .

Пример использования

В таблице 1 представлен пример использования алгоритма RSA. Отправитель отправил зашифрованное сообщение «111111» и получатель, используя свой закрытый ключ, расшифровал его.

Таблица 1 – Поэтапное выполнение алгоритма RSA

Заключение

В данном реферате был подробно рассмотрен алгоритм ассиметричного шифрования RSA. Была описана история его создания, описаны алгоритмы создания ключей, шифрования и расшифровки. Также представлен пример практического использования алгоритма RSA.

Список использованных источников

Семенов Ю.А. Протоколы Internet // М.: Проспект, 2011. – 114 с.

Беляев А.В. Методы и средства защиты информации // ЧФ СПбГТУ, 2010. – 142с.

Венбо М. Современная криптография. Теория и практика // М.: Вильямс, 2005. - 768 с.

Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты // М.: Триумф, 2002. - 816 с.

Алгоритм RSA // Интернет ресурс: http://ru.wikipedia.org/wiki/Rsa

Схема Райвеста - Шамира - Адлемана (RSA) в настоящее время является единственной, получившей широкое признание и практически применяемой схемой шифрования с открытым ключом.

Схема RSA представляет собой блочный шифр, в котором и открытый текст, и шифрованный текст представляются целыми числами из диапазона от 0 до п - 1 для некоторого п.

Открытый текст шифруется блоками, каждый из которых содержит двоичное значение, меньшее некоторого заданного числа п. Это значит, что длина блока должна быть не больше log2(«). На практике длина блока выбирается равной 2 к битам, где 2 к Схема, разработанная Райвестом, Шамиром и Адлеманом, основана на выражениях со степенями. Шифрование и дешифрование для блока открытого текста М и блока шифрованного текста С можно представить в виде следующих формул:

Как отправитель, так и получатель должны знать значение п. Отправитель знает значение е, и только получателю известно значение d. Таким образом, данная схема является алгоритмом шифрования с открытым ключом KU= {е, п), и личным ключом KR = {d, п}.

Чтобы этот алгоритм мог использоваться для шифрования с открытым ключом, должны быть выполнены следующие требования:

Должны существовать такие значения е, d и п, что M ed = M(mod п) для всех М п.

Должны относительно легко вычисляться IVT и С с1 для всех значений М п.

Должно быть практически невозможно определить d по имеющимся ей п.

Проанализируем сначала первое требование, а остальные рассмотрим позже. Необходимо найти соотношение вида

Здесь как нельзя лучше подойдет следствие из теоремы Эйлера: для таких любых двух простых чисел р и q и таких любых двух целых чисел пит, что n=pqn0 и произвольного целого числа к выполняются следующие соотношения:

где ф(я) является функцией Эйлера, значение которой равно числу положительных целых чисел, меньших п и взаимно простых с п.

В случае простых р и q имеем ф(pq) - (р - 1 )(q - 1). Поэтому требуемое соотношение получается при условии

Это эквивалентно следующим соотношениям:

т.е. ей d являются взаимно обратными по модулю ф(я). Обратите внимание, что в соответствии с правилами арифметики в классах вычетов это может иметь место только тогда, когда d (а следовательно и е) является взаимно простым с ф(и). В эквивалентной записи (ф(/7), d)=.

Теперь у нас есть все, чтобы представить схему RSA. Компонентами схемы являются:

р и q - два простых числа (секретные, выбираются);

п - pq (открытое, вычисляется);

такое е , что (ф(я), е) = 1,1 е

d = е л (mod ф(/?)) (секретное, вычисляется).

Личный ключ складывается из {d,n}, а открытый- из {е, п}. Предположим, что пользователь А опубликовал свой открытый ключ, и теперь пользователь В собирается переслать ему сообщение М.

Тогда пользователь В вычисляет шифрованное сообщение

Получив этот шифрованный текст, пользователь А дешифрует его, вычисляя

Имеет смысл привести здесь обоснование этого алгоритма. Были выбраны ей d такие, что

Значит, еЛшеет вид кц>(п)+. Но по следствию теоремы Эйлера, для таких любых двух простых чисел р и qu целых чисел п = pqn М, чтоО выполняются соотношения

Поэтому

Теперь имеем

Таблица 10.1 резюмирует алгоритм RSA, а на рис. 10.1 показан пример его применения. В этом примере ключи вычисляются следующим образом:

• 1. Выбираются два простых числа: р- 7 wq- 17.
• 2. Вычисляется п =pq = 7 х 17=119.
• 3. Вычисляется ф(п) - (р -){q - 1) = 96.
• 4. Выбирается е , взаимно простое с ф(п) = 96 и меньшее, чем ф(я); в данном случаев = 5.
• 5. Определяется такое d, что de = 1 (mod 96) и d 96. Соответствующим значением будет d= 77, так как 77 х 5 = 385 = 4 х 96 + 1.
• 6. В результате получаются открытый ключ KU= (5, 119} и личный ключ KR = {77, 119}.

В данном примере показано использование этих ключей с вводимым открытым текстом М = 19. При шифровании 19 возводится в пятую степень, что в результате дает 2 476 099. В результате деления на 119 определяется остаток, равный 66. Следовательно, 19 5 = 66(mod 119), и поэтому шифрованным текстом будет 66. После дешифрования выясняется, что

Рис. 10.1.

Таблица 10.1