Во второй части мы рассмотрим популярный алгоритм RSA, где при шифровании используется публичный ключ. Но вначале хочу предупредить вас еще раз. Код, представленный в этой статье, предназначен только для ознакомительных целей. Криптография – весьма обширная и сложная область, и чтобы у вас не было проблем, я не рекомендую шифровать информацию при помощи моей поделки.
Во второй части мы рассмотрим популярный алгоритм RSA, где при шифровании используется публичный ключ. Но вначале хочу предупредить вас еще раз. Код, представленный в этой статье, предназначен только для ознакомительных целей. Криптография - весьма обширная и сложная область, и чтобы у вас не было проблем, я не рекомендую шифровать информацию при помощи моей поделки.
Алгоритм RSA
Шифрование с использованием публичного ключа
Шифрование при помощи публичного ключа используется повсеместно. Если вы хотя бы раз оплачивали что-то в интернете, то уже пользовались этим методом (я надеюсь!). Сразу же возникает вопрос о том, как работает эта защита. Если я ввожу номер своей кредитной карты, чтобы что-то купить, почему кроме адресата никто не может подсмотреть эти сведения? Приведу метафору. Чтобы открыть сейф, вам требуется ключ (или молоток, но, к счастью, сейфы и замки защищены от такого рода деятелей). В шифровании с использованием публичного ключа происходит примерно то же самое. Вы показываете замок на всеобщее обозрение, но ключ от этого замка есть только у избранных, а другими методами открыть дверь практически невозможно.
RSA – один из алгоритмов, реализующих вышеуказанную схему. Кроме того, мы можем использовать этот алгоритм для подтверждения подлинности нашей личности. Если вы, используя секретный ключ, отсылаете кому-то зашифрованное сообщение, адресат при помощи публичного ключа может расшифровать ваше послание. Эта технология позволяет подписывать сообщения, и тем самым подтверждается подлинность отправителя.
Демо-программа на базе алгоритма RSA
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 использует возведение в степень по модулю для шифрования/дешифрования.
Для того чтобы атаковать закрытый текст, Ева должна вычислить
Рис. 14.6.
Две алгебраические структуры
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 ; если размер исходного текста больше, то он должен быть разделен на блоки.
Введение 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. В самом деле, этому вопросу по всему рунету и на этом ресурсе в частности посвящено столько статей, что сказать о нем что то новое практически невозможно.
Ну что там, ей богу, можно еще придумать и так все давным-давно понятно. Рецепт приготовления прост:
Два простых числа P и Q.
Перемножить до получения числа N.
Выбрать произвольное E.
Найти D=E -1 (mod(P-1 )(Q-1 )).
Для шифрования сообщение M возводим в степень E по модулю N. Для дешифрования криптотекст C в степень D по все тому же модулю N. Все криптопримитив готов. Берем и пользуемся, так? На самом деле, не так. Дело все в том, что это и в самом деле не более чем криптопримитив и в реальном мире все самую чуточку сложнее.
Немного теории
Для того чтобы понять почему крайне не рекомендуется использовать RSA в его наиболее простой форме сперва отметим следующее требование, выдвигаемое к асимметричным криптосистемам.Требование 1:
Современная асимметричная криптосистема может(но это еще не факт) считаться стойкой, если злоумышленник, имея два открытых текста M 1 и M 2 , а также один шифротекст C b не может с вероятностью большей, чем 0.5 определить какому из двух открытых текстов соответствует шифротекст C b .
Посмотрим, удовлетворяет ли RSA данному требованию. Итак, представим, злоумышленник Мэлори прослушивает переписку Алисы и Боба. В один чудесный для себя день он видит, что Боб в открытом виде задал Алисе очень важный вопрос, знание ответа на который обогатит, ну или, по крайней мере, безмерно потешит любопытство Мэлори. Алиса односложно отвечает Бобу на этот вопрос личного характера. Она шифрует свой ответ открытым ключом Боба и отправляет шифротекст. Далее Мэлори перехватывает шифротекст и подозревает, что в нем зашифровано либо «Да», либо «Нет». Всё, что ему теперь нужно сделать для того чтобы узнать ответ Алисы это зашифровать открытым ключом Боба слово «Да» и если полученный криптотекст совпадет с перехваченным, то это означает, что Алиса ответила «Да», в противном же случает злоумышленник поймет, что ответом было «Нет».
Как видно из этого, пускай несколько надуманного, но все же не столь и утопичного примера, RSA не столь надежна как это принято считать. Да конечно, можно сказать, что Алиса сама дура и никто ее не просил отвечать на такой серьезный для нее вопрос односложно. Так что же теперь запретить использование односложных ответов в криптографии? Конечно, нет. Все не так плохо, достаточно чтобы алгоритм добавлял к тексту некоторую случайную информацию, которую бы невозможно было предугадать и коварный Мэлори будет бессилен. Ведь, в самом деле, не сможет же он предсказать, что ответ «Да» после обработки алгоритмом превратится, например, в «Да4FE6DA54», а следовательно и зашифровать это сообщение он не сможет и нечего ему будет сравнивать с перехваченным криптотекстом.
Таким образом, уже сейчас можно сказать, что RSA во всех своих проявлениях будь то PGP или SSL не шифрует только отправленные на вход шифрующей функции данные. Алгоритм сперва добавляет к этим данным блоки содержащие случайный набор бит. И только после этого полученный результат шифруется. Т.е. вместо привычной всем
C=M E (mod N
)
получаем более близкую к действительности
C=(M||Rand) E (mod N
),
где Rand случайное число.
Такую методику называют схемами дополнения. В настоящее время использование RSA без схем дополнения является не столько плохим тоном, сколько непосредственно нарушением стандартов .
Но это далеко не все. Считается, что даже если криптоситема удовлетворяет сформулированному выше требованию, это еще не доказывает ее пригодность в практических целях. Сформулируем еще одно требование к стойкости асимметричного алгоритма.
Требование 2:
Пусть злоумышленник имеет доступ к расшифровывающему «черному ящику». Т.е. любой криптотекст по просьбе злоумышленника может быть расшифрован. Далее злоумышленник создает два открытых текста M 1 и M 2 . Один из этих текстов шифруется и полученный в результате криптотекст C b возвращается злоумышленнику. Задача злоумышленника угадать с вероятностью большей чем 0.5 какому из сообщений M 1 и M 2 соответсвует криптотекст C b . При этом он может попросить расшифровать любое сообщение, кроме C b (в противном случае игра не имеет смысла). Говорят что криптосистема стойкая, если злоумышленник, даже в таких прекрасных для себя условиях, не сможет указать какому исходному тексту соответствует C b с вероятностью большей 0.5.
В свете вышесказанного посмотрим как с этим обстоят дела в RSA.
Итак, злоумышленник имеет два сообщения M 1 и M 2 . А также криптотекст
C b =M 1 E (mod N
).
Ему необходимо указать какому конкретно из двух текстов соответствует C b . Для этого он может предпринять следующее. Зная открытый ключ E, он может создать сообщение
C"=2 E *C b (mod N
).
Далее он просит расшифровывающий «черный ящик» расшифровать сообщение C". А затем несложная арифметика ему в помощь. Имеем:
M"=C" D (mod N
)=2 ED *M 1 ED (mod N
)=2*M 1 (mod N
).
Т.е. вычислив M"/2 злоумышленник увидит M 1 . А это означает, что он поймет что в нашем примере было зашифровано сообщение M 1 , а следовательно мы еще раз убедились в неприемлемости использования RSA в его наивном виде на практике.
Устранить и эту неприятность помогают схемы дополнения. Только теперь к ним выдвигается требование не только о том, чтобы дополнительная информация была абсолютно случайной и непрогнозируемой. Но так же и том, чтобы дополнительные блоки помогали определить был ли шифротекст получен в результате работы шифрующей функции или он смоделирован злоумышленником. Причем в случае, если будет обнаружено, что шифротекст смоделирован вместо расшифрованных данных атакующему будет выдано сообщение о несоответствие данных реальному криптотексту.
Казалось бы, реализация такой схемы дополнения является труднорешаемой задачей, но ведь в криптографии уже есть готовый инструмент контроля целостности данных. Конечно же, это хеш-функции. Все современные схемы дополнений реализованы на идее применения хеш-функции в качестве проверки расшифрованных данных на подлинность.
В RSA при подписи и при шифровании данных используют две различные схемы дополнений. Схема, реализуемая для подписания документов, называется RSA-PSS(probabilistic signature scheme) или вероятностная схема подписи. Схема, используемая при шифровании – RSA-OAEP(Optimal asymmetric encryption padding) или оптимизированное асимметричное дополнение шифрования , на примере OAEP и рассмотрим как на самом деле происходит шифрование сообщений в RSA.
RSA-OAEP
Итак чтобы зашифровать абсолютно любое сообщение в RSA-OAEP делается следующее:- Выбираются две хеш-функции G(x) и H(x) таким образом, чтобы суммарная длина результатов хеш-функций не превышала длины ключа RSA.
- Генерируется случайная строка битов l. Длина строки должна быть равна длине результата хеш-функции H(x).
- Сообщение M разбивают на блоки по k-бит. Затем к каждому полученному блоку m дописывают (n-k) нулей. Где n-длина хеш-функции G(x).
- Определяют следующий набор бит: {m||0 (n-k) ⊕G(l)}||{l⊕H(m||0 (n-k) ⊕G(l))}
- Полученные биты представляют в виде целого числа M 1
- Криптотекст получают по формуле: C=M 1 E (mod N )
- Находят M 1 по формуле M 1 =C D (mod N )
- В полученном наборе бит отсекают левую часть. В смысле: левой частью служат n левых бит числа M 1 где n-длина хеш-функции G(x). Обозначим эти биты условно T. И заметим, что T={m||0 (n-k) ⊕G(l)}. Все остальные биты являются правой частью.
- Находим H(T)=H(m||0 (n-k) ⊕G(l))
- Зная H(T) получаем l, т.к. знаем l⊕H(T)-это правая часть блока.
- Вычислив l, находим m из T⊕G(l) т.к. T={m||0 (n-k) ⊕G(l)}
- Если m заканчивается (n-k)-нулями значит сообщение зашифровано правильно. Если нет то это значит, что шифротекст некорректен, а следовательно он скорее всего подделан злоумышленником.
Заключение
Т.е. RSA это не только возведение в степень по модулю большого числа. Это еще и добавление избыточных данных позволяющих реализовать дополнительную защиту вашей информации. Вы, возможно, спросите: а зачем это все нужно? Неужели в действительности может произойти такая ситуация, когда атакующий получит доступ к расшифровывающему алгоритму? Совсем по другому поводу как-то было сказано: если какая-либо неприятность может произойти, она обязательно произойдет. Только вот с использованием схем дополнений это уже не будет считаться неприятностью.Upd: перенес в блог криптография.
upd2:
Литература и ссылки:
1. Н. Фергюссон, Б. Шнайер «Практическая криптография»
2. Н. Смарт «Криптография»
Схема Райвеста - Шамира - Адлемана (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