Под катом описаны примеры выбора «плохих» параметров шифра RSA.

«Следует подчеркнуть необходимость соблюдения осторожности в выборе модуля RSA (числа n ) для каждого из корреспондентов сети. В связи с этим можно сказать следующее. Читатель может самостоятельно убедиться в том, что зная одну из трех величин p , q или φ(n) , можно легко найти секретный ключ RSA…».

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

Для этого достаточно располагать зашифрованным текстом, заданным модулем шифра n , открытым ключом е шифра и выполнить всего три шага атаки «бесключевого чтения». После четвертого атакующего шага устанавливается, что на предыдущем шаге был получен исходный текст, он может быть прочитан. Покажем, насколько просто это делается.

Вначале приведем сам пример со стр. 313-315 из названного пособия.

Пример

Шифрование короткого исходного текстового сообщения: RSA .
Получатель устанавливает шифр с характеристиками n=pq=527 , где р=17 , q=31 и φ(n)=(р –1)(q – 1)=480 . В качестве открытого ключа е выбрано число, взаимно простое с φ(n) , е=7 . Для этого числа с помощью расширенного алгоритма Евклида найдены целые числа u и v , удовлетворяющие соотношению е∙u+φ(n)∙v=1 :

480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v=2, u=–137 .

Поскольку –137≡343(mod480) , то d=343 .

Проверка: 7∙343=2401≡1(mod480) .

Текстовое сообщение представляется в виде последовательности чисел, содержащихся в интервале . Для этого буквы R , S и A кодируются пятиразрядными двоичными числами. Используются порядковые номера этих букв в английском алфавите при их двоичном представлении:

R=18 10 =(10010) 2 , S=19 10 =(10011) 2 ,
A=1 10 =(00001) 2 .

Тогда RSA=(100101001100001) 2 . Разбиение текста на блоки ограниченной длины дает представление из двух блоков: RSA=(100101001), (100001)=(М 1 =297, М 2 =33) .

Последовательно шифруются блоки исходного текста М 1 =297 , М 2 =33 :
y 1 =Е k (М 1)=М 1 e ≡297 7 (mod527)=474 .

Здесь воспользовались тем, что:

297 7 =((297 2) 3)297≡(mod527)=(200 3 (mod527)297)(mod527)=474 ,
y 2 =Е k (М 2)=M 2 e ≡33 7 (mod527)=407 .

Шифрованный текст, как и исходный, получаем в виде двух блоков: у 1 =474 ; у 2 =407 .

Расшифрование представляется последовательностью действий D k (y i)=(y i) d =(y i) 343 (mod 527) , i=1,2 .

Вычисления возведения в степень d более удобно проводить, предварительно представляя показатель степени суммой степеней числа 2 , а именно: 343=256+64+16+4+2+1 .

Используя это представление показателя степени d=343 , получаем:

474 2 ≡174(mod527),
474 4 ≡237(mod527),
474 8 ≡307(mod527),
474 16 ≡443(mod527),
474 32 ≡205(mod527),
474 64 ≡392(mod527),
474 128 ≡307(mod527),
474 256 ≡443(mod527),
и окончательно 474 343 (mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297 .

Аналогично вычисляется значение 407 343 (mod527)=33 .

Переход к буквенному представлению расшифрованного сообщения дает: RSA .

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

Атака на шифр RSA

Рассмотрим пример атаки на шифр RSA. Воспользуемся данными примера, приведенного на странице 313-315 в учебном пособии «Основы криптографии» А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин, Москва. «Гелиос АРВ», 2001.

Неудачность (недопустимость) выбранных параметров системы в этом примере легко показывается вычислениями, реализующими атаку бесключевого чтения исходного текста. Сущность такой атаки состоит в следующем. Заданы открытый ключ шифра RSA (е=7 , n=527 ) и шифрованный текст. В примере шифрованный текст представлен двумя блоками
у=(у 1 =474, у 2 =407) .

Каждый шифрованный блок атакуется индивидуально, вначале атакуем у 1 =474 , после его дешифрования, атакуем другой блок у 2 =407 .

Далее формируется путем многократного зашифрования с сохранением результатов двух последовательных шагов алгоритма атаки и с использованием открытого ключа последовательность числовых значений у i , у 1 =у имеющийся шифрованный текст.

В алгоритме атаки на шифрованный текст определяется такой номер шага j , для которого y i e j (mod n)=(y i e j–1 (mod n)) e (mod n)=y i , i>1 . Из последнего соотношения видим, что при возведении в степень е значения (y i e j–1 (mod n)) получается начальный шифoртекст y i = у 1 .

Но это и означает, что на этом шаге шифровался открытый текст. Непосредственными вычислениями (их оказывается совсем немного) с использованием экранного калькулятора находим то значение j , при котором цикл шифрования завершается значением y 1 , с которого цикл и был начат.

Атака на первый блок у 1 =474 шифртекста.
Шаг 1 :   474 7 (mod527)=382 ;
Шаг 2 :   382 7 (mod527)=423 ;
Шаг 3 :   423 7 (mod527)=297 ;
Шаг 4 :   на этом шаге шифруется уже найденный исходный текст, но его необходимо выполнить, так как атакующий исходного текста не знает. Признаком завершения атаки является совпадение начального значения шифртекста (474 ) и результата 4-го шага зашифрования. Именно такое совпадение и имеет место.

297 7 (mod527)=474 получили начальный (первый) блок шифртекста. Атака на первый блок завершена успешно у 1 =474 . Предшествующий результат шага 3 равен открытому тексту М 1 =297 .

n=527 r=297 по модулю n=527 . Это записывается так y i =у 1 =297 . Формируем степенные вычеты
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 =297 .

Атака на второй блок у 2 =407 шифртекста.
Шаг 1 :   407 7 (mod527)=16 ;
Шаг 2 :   16 7 (mod527)=101 ;
Шаг 3 :   101 7 (mod527)=33 ;
Шаг 4 :   33 7 (mod527)=407 .

Вновь на третьем шаге получен блок исходного текста (М 2 =33 ), но атакующему это неизвестно, и он выполняет следующий (четвертый шаг), результат которого (407 ) совпадает с начальным шифртекстом у 2 =407 .

По существу в кольце вычетов по модулю n=527 реализовался короткий цикл обработки вычета r=33 по модулю n=527 . Это записывается так y i =у 2 =33 .
Формируем степенные вычеты ((33 7 (mod527)) 7 (mod527)) 7 (mod527)=33 .

Результат атаки (исходный текст М 1 =297 , М 2 =33 ) получен трехкратным шифрованием заданного шифртекста. Больший успех для атакующего шифртекст трудно представить.

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

Ни на одном из заданных е не удается зашифровать исходные тексты, представляемые числами
187 , 341 , 154 и 373 .

Пример (невозможность шифрования значений некоторых исходных текстов)

Пусть исходные тексты представлены четырьмя блоками y=(y 1 =154, y 2 =187, y 3 =341, y 4 =373) . Экспонента е открытого ключа шифра может быть любым взаимно простым числом с функцией Эйлера φ(n)=φ(527)=480 . Впрочем, для рассматриваемого случая открытый ключ е может быть задан произвольно. Действительно, пусть е=2, 4, 7, 9, 17, 111 тогда:

154 2 (mod527)=1 ;
154 4 (mod527)=1 ;
154 7 (mod527)=154 ;
154 9 (mod527)=154 ;
154 17 (mod527)=154 ;
154 111 (mod527)=154 ;
187 2 (mod527)=187 ;
187 4 (mod527)=187 ;
187 7 (mod527)=187 ;
187 9 (mod527)=187 ;
187 17 (mod527)=187 ;
187 111 (mod527)=187 ;
341 2 (mod527)=341 ;
341 4 (mod527)=1 ;
341 7 (mod527)=341 ;
341 9 (mod527)=341 ;
341 17 (mod527)=341 ;
341 111 (mod527)=341 ;
373 2 (mod527)=1 ;
373 4 (mod527)=373 ;
373 7 (mod527)=373 ;
373 9 (mod527)=373 ;
373 17 (mod527)=373 ;
373 111 (mod527)=373 .

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

В зависимости от структуры используемых ключей методы шифрования подразделяются на:

• симметричное : посторонним лицам может быть известен алгоритм шифрования, но неизвестна небольшая порция секретной информации - ключа, одинакового для отправителя и получателя сообщения; Примеры: DES, 3DES, AES, Blowfish, Twofish, ГОСТ 28147-89
• асимметричное шифрование: посторонним лицам может быть известен алгоритм шифрования, и, возможно открытый ключ, но неизвестен закрытый ключ, известный только получателю. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), а так же SSH, PGP, S/MIME и т. д. Российский стандарт, использующий асимметричное шифрование - .

На данный момент асимметричное шифрование на основе открытого ключа RSA (расшифровывается, как Rivest, Shamir and Aldeman - создатели алгоритма) использует большинство продуктов на рынке информационной безопасности.

Его криптостойкость основывается на сложности разложения на множители больших чисел, а именно - на исключительной трудности задачи определить секретный ключ на основании открытого, так как для этого потребуется решить задачу о существовании делителей целого числа. Наиболее криптостойкие системы используют 1024-битовые и большие числа.

Рассмотрим алгоритм RSA с практической точки зрения.

Для начала необходимо сгенерировать открытый и секретные ключи:

• Возьмем два больших простых числа p and q.
• Определим n, как результат умножения p on q (n= p*q).
• Выберем случайное число, которое назовем d. Это число должно быть взаимно простым (не иметь ни одного общего делителя, кроме 1) с результатом умножения (p-1)*(q-1).
• Определим такое число е, для которого является истинным следующее соотношение (e*d) mod ((p-1)*(q-1))=1.
• Hазовем открытым ключем числа e и n, а секретным - d и n.

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

• разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа M(i)=0,1,2..., n-1(т.е. только до n-1).
• зашифровать текст, рассматриваемый как последовательность чисел M(i) по формуле C(i)=(M(I)^e)mod n.

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

Следующий пример наглядно демонстрирует алгоритм шифрования RSA:

Зашифруем и расшифруем сообщение "САВ" по алгоритму RSA. Для простоты возьмем небольшие числа - это сократит наши расчеты.

• Выберем p=3 and q=11.
• Определим n= 3*11=33.
• Hайдем (p-1)*(q-1)=20. Следовательно, d будет равно, например, 3: (d=3).
• Выберем число е по следующей формуле: (e*3) mod 20=1. Значит е будет равно, например, 7: (e=7).
• Представим шифруемое сообщение как последовательность чисел в диапозоне от 0 до 32 (незабывайте, что кончается на n-1). Буква А =1, В=2, С=3.

Теперь зашифруем сообщение, используя открытый ключ {7,33}

C1 = (3^7) mod 33 = 2187 mod 33 = 9;
C2 = (1^7) mod 33 = 1 mod 33 = 1;
C3 = (2^7) mod 33 = 128 mod 33 = 29;

Теперь расшифруем данные, используя закрытый ключ {3,33}.

M1=(9^3) mod 33 =729 mod 33 = 3(С);
M2=(1^3) mod 33 =1 mod 33 = 1(А);
M3=(29^3) mod 33 = 24389 mod 33 = 2(В);

Данные расшифрованы!

Введение 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 на каждом такте шифрования преобразует двоичный блок открытого текста 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