Что такое rsa ключ. Криптографические алгоритмы с открытым ключом и их использование

Под катом описаны примеры выбора «плохих» параметров шифра 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 .

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

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

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

Алгоритм RSA

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

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

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

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

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

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

Название RSA состоит из начальных букв фамилий Ривест, Шамир и Адлеман, - ученых, которые впервые публично описали подобные в 1977 году. Клиффорд Кокс, английский математик, работавший на спецслужбы Великобритании, впервые разработал эквивалентную систему в 1973 году, но она не была рассекречена до 1997 г.

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

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

Когда появилась криптосистема в современном виде?

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

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

ЭЦП и открытый ключ

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

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

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

В чем суть алгоритма?

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

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

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

Шифрование файлов RSA и слабые места

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

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

Дополнительные алгоритмы шифрования и защиты

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

Безопасность криптосистемы RSA и шифрование информации основаны на двух математических задачах: проблемы разложения на множители больших чисел и собственно проблемы RSA. Полное раскрытие шифротекста и ЭЦП в RSA считается недопустимым на том предположении, что обе эти проблемы невозможно разрешить в совокупности.

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

Автоматизация

Инструмент, называемый Yafu, может быть использован для оптимизации этого процесса. Автоматизация в YAFU представляет собой современную функцию, сочетающую алгоритмы факторизации в интеллектуальной и адаптивной методологии, которая сводит к минимуму время, чтобы найти факторы произвольных входных чисел. Большинство реализаций алгоритма многопоточные, что позволяет Yafu в полной мере использовать мульти- или много (в том числе SNFS, SIQS и ECM). Прежде всего, это управляемый инструмент командной строки. Время, затраченное на поиск фактора шифрования с использованием Yafu на обычном компьютере, может быть уменьшено до 103.1746 секунд. Инструмент производит обработку емкостью 320 бит или больше. Это очень сложное программное обеспечение, которое требует определенного количества технических навыков для установки и настройки. Таким образом, RSA-шифрование C может оказаться уязвимым.

Попытки взлома в новейшее время

В 2009 году Бенджамин Муди с помощью битового ключа RSA-512 работал над расшифровкой криптотекста в течение 73 дней, используя только общеизвестное программное обеспечение (GGNFS) и среднестатистический настольный компьютер (двухъядерный Athlon64 при 1900 МГц). Как показал данный опыт, потребовалось чуть менее 5 гигабайт диска и около 2,5 гигабайт оперативной памяти для процесса «просеивания».

По состоянию на 2010 год, самый большой факторизованный номер RSA был 768 бит длиной (232 десятичные цифры, или RSA-768). Его раскрытие длилось два года на нескольких сотнях компьютеров одновременно.

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

Перспективы

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

Официально в 2003 году была поставлена под сомнение безопасность 1024-битных ключей. В настоящее время рекомендуется иметь длину не менее 2048 бит.

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

Общая схема

Схема электронной подписи обычно включает в себя:

• алгоритм генерации ключевых пар пользователя;
• функцию вычисления подписи;
• функцию проверки подписи.

Функция вычисления подписи на основе документа и секретного ключа пользователя вычисляет собственно подпись. В зависимости от алгоритма функция вычисления подписи может быть детерминированной или вероятностной. Детерминированные функции всегда вычисляют одинаковую подпись по одинаковым входным данным. Вероятностные функции вносят в подпись элемент случайности, что усиливает криптостойкость алгоритмов ЭЦП. Однако, для вероятностных схем необходим надёжный источник случайности (либо аппаратный генератор шума, либо криптографически надёжный генератор псевдослучайных бит), что усложняет реализацию.

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

Функция проверки подписи проверяет, соответствует ли данная подпись данному документу и открытому ключу пользователя. Открытый ключ пользователя доступен всем, так что любой может проверить подпись под данным документом.

Поскольку подписываемые документы — переменной (и достаточно большой) длины, в схемах ЭЦП зачастую подпись ставится не на сам документ, а на его хэш. Для вычисления хэша используются криптографические хэш-функции, что гарантирует выявление изменений документа при проверке подписи. Хэш-функции не являются частью алгоритма ЭЦП, поэтому в схеме может быть использована любая надёжная хэш-функция.

Защищённость

Цифровая подпись обеспечивает:

• Удостоверение источника документа. В зависимости от деталей определения документа могут быть подписаны такие поля, как «автор», «внесённые изменения», «метка времени» и т. д.
• Защиту от изменений документа. При любом случайном или преднамеренном изменении документа (или подписи) изменится хэш, следовательно, подпись станет недействительной.
• Невозможность отказа от авторства. Так как создать корректную подпись можно лишь, зная закрытый ключ, а он известен только владельцу, то владелец не может отказаться от своей подписи под документом.

Возможны следующие угрозы цифровой подписи:

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

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

Тем не менее, возможны ещё такие угрозы системам цифровой подписи:

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

Алгоритмы ЭЦП

• Американские стандарты электронной цифровой подписи: DSA, ECDSA

• Российские стандарты электронной цифровой подписи: ГОСТ Р 34.10-94 (в настоящее время не действует), ГОСТ Р 34.10-2001
• Украинский стандарт электронной цифровой подписи: ДСТУ 4145-2002
• Стандарт PKCS#1 описывает, в частности, схему электронной цифровой подписи на основе алгоритма RSA

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

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

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

Управлением ключами занимаются центры распространения сертификатов. Обратившись к такому центру пользователь может получить сертификат какого-либо пользователя, а также проверить, не отозван ли ещё тот или иной открытый ключ.

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

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

История

Британский математик Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал аналогичную систему в 1973 году во внутренних документах центра, но эта работа не была раскрыта до 1977 года и Райвест, Шамир и Адлеман разработали RSA независимо от работы Кокса.

В 1983 году MIT был выдан патент 4405829 США, срок действия которого истёк 21 сентября 2000 года.

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

Безопасность алгоритма RSA основана на трудности задачи разложения на множители. Алгоритм использует два ключа — открытый (public) и секретный (private), вместе открытый и соответствующий ему секретный ключи образуют пару ключей (keypair). Открытый ключ не требуется сохранять в тайне, он используется для зашифрования данных. Если сообщение было зашифровано открытым ключом, то расшифровать его можно только соответствующим секретным ключом.

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

Для того, чтобы сгенерировать пару ключей выполняются следующие действия:

1. Выбираются два больших простых числа и

2. Вычисляется их произведение

3. Вычисляется Функция Эйлера

4. Выбирается целое такое, что и взаимно простое с

5. С помощью расширенного алгоритма Евклида находится число такое, что

Число и используется в качестве шифртекста. Для расшифрования нужно вычислить

Нетрудно убедиться, что при расшифровании мы восстановим исходное сообщение:

Из условия

следует, что

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

Согласно теореме Эйлера:

Некоторые особенности алгоритма

Генерация простых чисел

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

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

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

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

Выбор значения открытого показателя

RSA работает значительно медленнее симметричных алгоритмов. Для повышения скорости шифрования открытый показатель выбирается небольшим, обычно 3, 17 или 65537. Эти числа в двоичном виде содержат только по две единицы, что уменьшает число необходимых операций умножения при возведении в степень. Например, для возведения числа в степень 17 нужно выполнить только 5 операций умножения:

должно быть достаточно большим. В 1990 году Михаэль Винер (Michael J. Wiener) показал, что если выбирается небольшим, то оказывается достаточно большим и проблемы не возникает.

Длина ключа

Число n должно иметь размер не меньше 512 бит. В настоящий момент система шифрования на основе RSA считается надёжной, начиная с размера N в 1024 бита.

Применение RSA

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

Из-за низкой скорости шифрования (около 30 кбит/с при 512 битном ключе на процессоре 2 ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным ключом (сеансовый ключ ), а с помощью RSA шифруют лишь этот ключ.

II. Реализация

Для примера была реализована программа для цифрового подписания файлов и проверки подписей. Использовался алгоритм RSA и сертификаты X.509. Сертификат пользователя выбирается из хранилища сертификатов windows.

Цифровые подписи сохраняются в xml файле с именем <имя исходного файла>.sig.xml

Фрагменты кода

public class Signature

private X509Certificate2 certificate;

private DateTime date;

private byte signedHash;

public X509Certificate2 Certificate

get { return certificate; }

set { certificate = value; }

public DateTime Date

get { return date; }

set { date = value; }

public void Sign(string input, X509Certificate2 cert)

this.certificate = new X509Certificate2(cert);

date = DateTime.Now;

signedHash = ((RSACryptoServiceProvider)cert.PrivateKey).SignData(Utils.StringToBytes(stringToEncrypt),new MD5CryptoServiceProvider());

public bool IsValid(string input)

string stringToEncrypt = input + date.Ticks;

return ((RSACryptoServiceProvider)certificate.PublicKey.Key).VerifyData(Utils.StringToBytes(stringToEncrypt),new MD5CryptoServiceProvider(), signedHash);

public byte SignedHash

get { return signedHash; }

set { signedHash = value; }

void DisplaySignatureList()

FileSignatures fileSignatures = ReadSignatures(GetSignaturesFileName(fileNameTextBox.Text));

signatureListTextBox.Text = "";

foreach (Signature signaure in fileSignatures.Signaures)

string row = "";

row+= signaure.Certificate.Subject;

row+=" "+signaure.Date.ToString();

string hash = GetFileHash(fileNameTextBox.Text);

bool valid = signaure.IsValid(hash);

row = "v " + row;

row = "x " + row;

signatureListTextBox.Text += row+"\r\n";

III. Литература

1. С.Бернет, С. Пейн: Криптография. Официальное руководство RSA Security – М. «Бином», 2002
2. В. Зима: Безопасность глобальных сетевых технологий – «БХВ-Петербург», 2003
3. Венбо Мао Современная криптография: теория и практика = Modern Cryptography: Theory and Practice. — М.: «Вильямс», 2005. — С. 768. ISBN 0-13-066943-1
4. Нильс Фергюсон, Брюс Шнайер Практическая криптография: Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М.: «Диалектика», 2004. — С. 432. ISBN 0-471-22357-3
5. Шнайер, Брюс. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си — М.: Издательство ТРИУМФ, 2002 — 816с.:ил. ISBN 5-89392-055-4

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

1. Выбираются две хеш-функции G(x) и H(x) таким образом, чтобы суммарная длина результатов хеш-функций не превышала длины ключа RSA.
2. Генерируется случайная строка битов l. Длина строки должна быть равна длине результата хеш-функции H(x).
3. Сообщение M разбивают на блоки по k-бит. Затем к каждому полученному блоку m дописывают (n-k) нулей. Где n-длина хеш-функции G(x).
4. Определяют следующий набор бит: {m||0 (n-k) ⊕G(l)}||{l⊕H(m||0 (n-k) ⊕G(l))}
5. Полученные биты представляют в виде целого числа M 1
6. Криптотекст получают по формуле: C=M 1 E (mod N )

Процесс дешифрования выглядит следующим образом:

1. Находят M 1 по формуле M 1 =C D (mod N )
2. В полученном наборе бит отсекают левую часть. В смысле: левой частью служат n левых бит числа M 1 где n-длина хеш-функции G(x). Обозначим эти биты условно T. И заметим, что T={m||0 (n-k) ⊕G(l)}. Все остальные биты являются правой частью.
3. Находим H(T)=H(m||0 (n-k) ⊕G(l))
4. Зная H(T) получаем l, т.к. знаем l⊕H(T)-это правая часть блока.
5. Вычислив l, находим m из T⊕G(l) т.к. T={m||0 (n-k) ⊕G(l)}
6. Если m заканчивается (n-k)-нулями значит сообщение зашифровано правильно. Если нет то это значит, что шифротекст некорректен, а следовательно он скорее всего подделан злоумышленником.

Заключение

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

Upd: перенес в блог криптография.
upd2:
Литература и ссылки:
1. Н. Фергюссон, Б. Шнайер «Практическая криптография»
2. Н. Смарт «Криптография»