RSA, а так ли все просто? Выбор параметров шифра RSA и возможные последствия Шифрование с использованием алгоритма rsa

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

RSA-шифрование работает по принципу факторинга. Как это? А это факторинговое
воспроизведение двух больших числовых данных.

Кто создал систему RSA-шифрования?

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

Как работает RSA-шифрование?

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

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

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

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

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

Цифровая подпись и связь с открытыми ключами

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

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

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

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

Давайте разберемся, в чем суть придуманного алгоритма?

RSA-шифрование работает по принципу четырех этапов:
генерация ключей;
распределение ключей;
шифрование ключей;
дешифрование ключей.

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

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

Слабые стороны методики RSA-шифрования

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

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

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

Дополнительные составляющие, обеспечивающие безопасность использования RSA-шифрования

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

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

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

Автоматизированный процесс шифрования электронных данных

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

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

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

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

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

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

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

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

Заключение

Исходя из выше сказанного RSA-шифрование – это безопасный метод сохранения конфиденциальности электронных данных при условии создания длинных и информационно объемных ключей.

Вручную их сложно подбирать, поэтому используется автоматизированный программный продукт Yafu. Его установкой и настройкой занимаются ИТ-специалисты. Самостоятельная работа может привести к поломке операционной системы компьютера.
Это программное обеспечение рассчитано на работу в тандеме с многоядерными компьютерными процессорами современного поколения.

Основными объектами мошеннических атак являются крупные промышленные и финансовые компании, поэтому без 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 бит.

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

§ 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 мы сформулировали стратегию, предназначенную для доказательства простоты данного нечетного числа Она состоит из трех шагов.