Алгоритм шифрования rsa 3072. Электронная цифровая подпись, алгоритм RSA

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

Общая схема

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Американские стандарты электронной цифровой подписи: 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-шифрование и при звучании этого термина удивляются. Но ничего сложного в этом понятии не таится. 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 (числа n ) для каждого из корреспондентов сети. В связи с этим можно сказать следующее. Читатель может самостоятельно убедиться в том, что зная одну из трех величин p , q или φ(n) , можно легко найти секретный ключ RSA…».

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

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

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

Пример

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 (е=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 .

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

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

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

Две алгебраические структуры

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 ; если размер исходного текста больше, то он должен быть разделен на блоки.