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

Введение 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, где при шифровании используется публичный ключ. Но вначале хочу предупредить вас еще раз. Код, представленный в этой статье, предназначен только для ознакомительных целей. Криптография - весьма обширная и сложная область, и чтобы у вас не было проблем, я не рекомендую шифровать информацию при помощи моей поделки.

Алгоритм RSA

Шифрование с использованием публичного ключа

Шифрование при помощи публичного ключа используется повсеместно. Если вы хотя бы раз оплачивали что-то в интернете, то уже пользовались этим методом (я надеюсь!). Сразу же возникает вопрос о том, как работает эта защита. Если я ввожу номер своей кредитной карты, чтобы что-то купить, почему кроме адресата никто не может подсмотреть эти сведения? Приведу метафору. Чтобы открыть сейф, вам требуется ключ (или молоток, но, к счастью, сейфы и замки защищены от такого рода деятелей). В шифровании с использованием публичного ключа происходит примерно то же самое. Вы показываете замок на всеобщее обозрение, но ключ от этого замка есть только у избранных, а другими методами открыть дверь практически невозможно.

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

Демо-программа на базе алгоритма RSA

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

• симметричное : посторонним лицам может быть известен алгоритм шифрования, но неизвестна небольшая порция секретной информации - ключа, одинакового для отправителя и получателя сообщения; Примеры: 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(В);

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

Наконец-то настало время заняться описанием RSA-криптосистемы. Помимо объяснения, как она работает, мы должны в деталях обсудить ее безопасность; другими словами, почему настолько трудно взломать сообщение, зашифрованное RSA-криптосистемой?

§ 12.1. О начале и конце

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

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

Для простоты предположим, что текст сообщения содержит только слова, записанные заглавными буквами. Таким образом, сообщение, в конечном счете, - последовательность букв и пробелов. Первый шаг состоит в замене каждой буквы сообщения числом, которое выбирается из следующей таблицы:

(см. скан)

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

Например, численное представление девиза «ПОЗНАЙ СЕБЯ» выглядит так:

Выбрав простые мы получим произведение Поэтому численное представление сообщения, выписанное выше, нужно разбить на блоки, меньшие чем 23 393. Приведем одно из таких разбиений.

Конечно, выбор блоков не однозначен, но и не совсем произволен. Например, во избежание двусмысленностей на стадии

расшифровки не следует выделять блоки, начинающиеся с нуля.

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

Обратите внимание на то, что каждая буква таблицы кодируется двузначным числом. Так делается для предотвращения путаницы. Предположим, мы пронумеровали буквы по порядку, начиная с 1, т.е. А соответствует 1, Б - 2, и так далее. В этом случае мы не сможем точно сказать, обозначает ли блок 12 пару букв или только одну букву двенадцатую букву алфавита. Конечно, для численного представления сообщения можно использовать любое однозначное соответствие между буквами и числами, например, -кодировку, при которой перевод сообщения в цифровую форму автоматически выполняется компьютером.

§ 12.2. Шифровка и дешифровка

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

Напомним, что по известным р и q число легко вычисляется. Действительно,

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

Заметим, что каждый блок сообщения шифруется отдельно. Поэтому зашифрованное сообщение, фактически, состоит из отдельных закодированных блоков. Более того, мы не можем объединить эти блоки в одно большое число, поскольку в результате расшифровать сообщение станет невозможно. Вскоре мы увидим причину этого.

Вернемся к примеру, который начали рассматривать в первом параграфе. Мы зафиксировали так что Теперь нужно выбрать число Напомним, что оно должно быть взаимно простым с Наименьшее простое число, не делящее 23088, равно 5. Положим Чтобы закодировать первый блок сообщения из § 12.1, нам предстоит определить вычет числа 25245 по модулю 23 393. С помощью программы символьных вычислений (или калькулятора, если хватит терпения) мы получим, что искомый вычет равен 22 752. Итак, Все же зашифрованное сообщение представляется следующей последовательностью блоков:

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

Получается в результате операции:

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

Наконец, как мы утверждали во введении и на протяжении всей книги, для взлома RSA-криптосистемы необходимо разложить на множители, потому что для дешифровки сообщения нужно знать Однако после того, как работа системы подробно описана, ясно, что последнее утверждение не совсем точно. Чтобы прочесть шифровку, кроме самого нужно знать только обратный к элемент по модулю Поэтому для взлома системы достаточно вычислить при известных Оказывается, это вычисление равносильно разложению числа на множители, как мы убедимся в § 12.4.

В обсуждаемом примере Для определения применим расширенный алгоритм Евклида к числам и 5.

(см. скан)

Таким образом, Следовательно, обратным к 5 по модулю будет -9235 и

Наименьшее натуральное число, сравнимое с -9235 по модулю Значит, для раскодирования блока шифрованного сообщения мы должны возвести его в степень 13 853 по модулю 23 393. В нашем примере первый закодированный блок - это 22 752. Вычисляя вычет числа 22 75213853 по модулю 23 393, получим Заметьте, что даже при таких малых числах требования, предъявляемые при работе RSA-криптосистемы, превышают возможности большинства карманных калькуляторов.

§ 12.3. Почему она работает?

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

На самом деле, достаточно доказать, что

Действительно, как 6, так и неотрицательные целые числа, меньшие Поэтому они сравнимы по модулю тогда и только тогда, когда они равны. Это, в частности, объясняет, почему мы разбиваем численное представление сообщения на блоки, меньшие Кроме того, отсюда видно, что блоки

закодированного сообщения необходимо записывать отдельно: в противном случае наши рассуждения не будут работать.

Из рецептов шифрования и дешифрования следует, что

Поскольку элементы взаимно обратны по модулю найдется такое натуральное к, что Более того, по условию, числа больше Следовательно, Подставляя вместо произведения в уравнение (3.1), получаем

Теперь воспользуемся теоремой Эйлера, которая утверждает, что Отсюда т. е.

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

Внимательно просмотрев еще раз наши рассуждения, Вы заметите, что мы не учитывали условий теоремы Эйлера. На самом деле, прежде чем применять теорему, необходимо убедиться во взаимной простоте чисел За этим, казалось бы, нужно следить при подготовке сообщения к шифровке, т.е. во время разбиения численного представления сообщения на блоки нужно добиваться уверенности в том, что все получающиеся блоки взаимно просты с К счастью, в этом нет необходимости, потому что на самом деле сравнение выполнено для любого блока. И ошибка кроется не в результате, который мы хотим доказать, а только лишь в самом доказательстве. Правильный подход основывается на рассуждениях, использованных при доказательстве теоремы Корселта в главе 7.

Напомним, что где различные простые числа. Определим вычеты числа по модулям Поскольку

вычисления для обоих простых чисел аналогичны, мы проработаем в деталях только случай Итак, мы уже убедились в том, что

для некоторого целого Следовательно,

Мы хотели бы теперь применить теорему Ферма, но имеем право сделать это, только если не делит Пусть это требование выполнено. Тогда и мы получаем, что

Заменив теорему Ферма теоремой Эйлера, мы не решили возникшей проблемы: сравнение справедливо только для некоторых, но не для всех блоков. Однако теперь блоки, для которых рассуждения не проходят, должны делиться на Далее, если делит то как 6, так и сравнимы с 0 по модулю а значит сравнимы между собой. Таким образом, доказываемое сравнение справедливо и в этом случае. Следовательно, сравнение истинно для любого целого числа Обратите внимание на то, что мы не. могли использовать подобное рассуждение, когда применяли теорему Эйлера к Действительно, неравенство не означает сравнения потому что число составное.

Итак, мы доказали, что Аналогично доказывается сравнение Другими словами, делится и на и на Но различные простые числа, так что Таким образом, лемма из § 3.6 гарантирует нам, что делит А так как мы имеем для любого целого числа Другими словами, Как мы отметили в начале параграфа, этого достаточно для доказательства равенства поскольку обе его части - неотрицательные целые числа, меньшие Подводя итог, можно утверждать, что

алгоритм предыдущего параграфа приводит к практической криптосистеме. Теперь нужно убедиться в ее надежности.

§ 12.4. Почему система надежна?

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

Чтобы раскодировать блок, зашифрованный с помощью RSA, мы должны узнать число обратное к по модулю Проблема в том, что практически единственный известный способ сделать это основывается на применении расширенного алгоритма Евклида к Однако для вычисления по формуле из § 9.4 нам нужно знать что подтверждает первоначальное утверждение: взлом RSA требует разложения на множители. А поскольку трудности разложения носят принципиальный характер, система RSA безопасна.

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

известны, то мы с легкостью вычисляем Действительно,

так что сумма искомых простых делителей известна. Далее,

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

Значит, алгоритм, вычисляющий фактически раскладывает число на множители, так что это одного поля ягодки. Но успокаиваться пока рано. Можно пойти дальше в своих фантазиях и предположить, что кто-то изобрел алгоритм, определяющий непосредственно по Но Так что, если нам известны то мы знаем число, кратное Оказывается, такой информации тоже достаточно для разложения Вероятностный алгоритм, приводящий к такому разложению, можно найти в . В упражнении 7 приведен похожий (но более простой) алгоритм разложения в предположении, что криптосистему Рабина можно взломать. Он даст вам представление о вероятностном алгоритме из .

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

§ 12.5. Выбор простых

Из предыдущего обсуждения вытекает, что для безопасности RSA-криптосистемы важно правильно выбрать простые числа Естественно, если они малы, то система легко взламывается. Однако недостаточно выбрать большие Действительно, даже если р и q огромны, но разность мала, их произведение легко разлагается на множители с помощью алгоритма Ферма (см. § 3.4).

Это не праздный разговор. В 1995 году два студента одного американского университета взломали версию RSA, находящуюся в общественном пользовании. Такое стало возможным из-за плохого выбора простых множителей системы.

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

Предположим, мы хотим создать RSA-криптосистему с открытым ключом в котором целое число имеет около знаков. Сначала выберем простое число количество знаков которого лежит между возьмем близким к В настоящее время рекомендованный для персонального использования размер ключа равен 768 битам, т.е. должно приблизительно состоять из 231 цифры. Чтобы построить такое число, нам потребуются два простых, скажем, из 104 и 127 знаков. Обратите внимание на то, что выбранные таким образом простые достаточно далеки друг от друга, т.е. применение алгоритма Ферма для разложения в этой ситуации непрактично. Кроме того, нам нужно удостовериться в том, что в разложении чисел на простые множители участвуют не только малые делители, но и большие. Действительно, в противном случае, число становится легкой добычей для некоторых известных алгоритмов разложения (см. ). Рассмотрим теперь метод, с помощью которого находят простые числа, удовлетворяющие перечисленным условиям.

Сначала нам потребуется один простой результат о распределении простых чисел. Напомним, что обозначает количество простых, не превосходящих х. Учитывая теорему о простых числах, мы видим, что для больших х число приблизительно равно где натуральный логарифм

по основанию (см. § 4.5). Пусть очень большое, какое-то положительное число. Мы хотим оценить количество простых чисел, лежащих между прикинуть разность Благодаря теореме о простых числах и свойствам логарифма, разность приблизительно равна

Предполагая, что очень мало, мы можем считать значение равным 0 и получить разумную оценку разности Итак, число простых, заключенных между приблизительно равно Естественно, оценка тем точнее, чем больше х и меньше Для более подробного знакомства с такой оценкой см. ([Д.10]).

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

простых числа. В конце второго параграфа главы 11 мы сформулировали стратегию, предназначенную для доказательства простоты данного нечетного числа Она состоит из трех шагов.

Схема Райвеста - Шамира - Адлемана (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