Протоколы эцп протокол на основе rsa реферат

Обновлено: 06.07.2024

14. ПРОТОКОЛЫ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ

14.1. Общие сведения

Электронная цифровая подпись – реквизит электронного документа, предназначенный для защиты данного документа от подделки, полученный в результате криптографического преобразования информации с использованием закрытого ключа ЭЦП и позволяющий идентифицировать владельца сертификата ключа подписи, а также установить отсутствие искажения информации в электронном документе (Федеральный закон № 1-ФЗ "Об электронной цифровой подписи" от 10.01.2002г.).

Электронная цифровая подпись – информация в электронной форме, которая присоединена к другой информации в электронной форме (подписываемой информации) или иным образом связана с такой информацией и которая используется для определения лица, подписывающего информацию (Федеральный закон № 63-ФЗ "Об электронной подписи" от 06.04.2011г.).

Говоря о схеме электронной подписи, обычно имеют в виду следующую классическую ситуацию [8]:

- безопасность схемы подписи гарантируется.

При создании электронной подписи по классической схеме отправитель:

- вычисляет электронную подпись s по хеш-образу r с использованием своего закрытого ключа;

- расшифровывает хеш-образ r’ из электронной подписи s с использованием открытого ключа отправителя;

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

Таблица 14.1. Схемы ЭЦП

1 NIST - Национальный Институт стандартов и технологий, США (The National Institute of Standards and Technology).

2 ISO - Международная организация по стандартизации (International Organization for Standardization).

3 ANSI - Американский национальный институт стандартов (American National Standards Institute).

4 IEEE - Институт инженеров по электротехнике и электронике (Institute of Electrical and Electronics Engineers).

14.2. Протокол на базе алгоритма RSA

Этап 1. Отправитель А генерирует открытый и закрытый ключи, публикует открытый ключ.

14.3. Алгоритм цифровой подписи ГОСТ 34.10-94

Алгоритм цифровой подписи ГОСТ 34.10-94 похож на DSS-94 и является вариацией схемы Эль-Гамаля.

Этап 1. Выработка ключей (выполняет отправитель А).

Таблица 14.4. Выработка ключей для ЭПЦ по ГОСТ 34.10-94

№ п/п	Описание операции	Пример
1	Выбор простого числа р (по ГОСТ – 2 509 < p < 2 512 либо 2 1020 < p < 2 1024 ).	p = 79
2	Выбор простого числа q, являющегося делителем (р – 1) (по ГОСТ – 2 254 < q < 2 256 ).	q = 13 [(79 – 1) mod 13 = 0]
3	Выбор а (0 < a < р – 1), для которого a q mod р = 1.	a = 8 [8 13 mod 79 = 1]
4	Выбор закрытого ключа х (0 < x < q).	x = 4
5	Вычисление y = a x mod p.	y = 8 4 mod 79 = 67
6	Публикация открытого ключа р, q, а, y>. Первые три параметра р, q и а - открыты и могут совместно использоваться пользователями сети, y – персональный открытый ключ для одного пользователя (отправителя А).

14.4. Алгоритм цифровой подписи ГОСТ Р 34.10-2001 и ГОСТ Р 34.10-2012

Алгоритмы цифровой подписи ГОСТ Р 34.10-2001 и ГОСТ Р 34.10-2012 совпадают и похожи на ECDSA.

Этап 1. Отправитель А генерирует открытый p,y_p)=P(7,17), q=47, Q(x_q,y_q)=Q(36,20)> и закрытый ключи, публикует открытый ключ.

14.5. Разновидности ЭЦП

Кроме классической схемы ЭЦП различают еще несколько специальных [8]:

- схема "конфиденциальной" (неотвергаемой) подписи – подпись не может быть проверена без участия сгенерировавшего ее лица;

14.6. Юридические основания использования ЭЦП

10 января 2002 г. Президент Российской Федерации В.В. Путин подписал Федеральный закон № 1-ФЗ "Об электронной цифровой подписи". Цель Федерального закона № 1-ФЗ - обеспечение правовых условий использования ЭЦП в электронных документах, при соблюдении которых ЭЦП в электронном документе признается равнозначной собственноручной подписи в документе на бумажном носителе.

В настоящий момент действует Федеральный закон № 63-ФЗ "Об электронной подписи" от 06.04.2011 г. Сфера действия (цель) Федерального закона № 63-ФЗ - регулирует отношения в области использования электронных подписей при совершении гражданско-правовых сделок, оказании государственных и муниципальных услуг, исполнении государственных и муниципальных функций, при совершении иных юридически значимых действий, в том числе в случаях, установленных другими федеральными законами.

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

Сертификат ЭЦП – открытый ключ с некоторой дополнительной информацией о его владельце (регистрационный номер сертификата, ФИО владельца, срок действия и т.д.), подписанный ключом Центра сертификации (ЦС, Certificate Authority, CA, Удостоверяющий центр, УЦ).

В Федеральном законе "Об электронной подписи" даны следующие определения.

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

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

При получении документа, подписанного ЭЦП, вначале подается запрос в ЦС, который высылает сертификат ЭЦП, информацию об окончании срока его действия или информацию об отсутствии сертификата. Если ЦС выслал сертификат, то считается, что документ послал именно тот, кто указан в сертификате. Для автоматизации деятельности ЦС применяется системы, называемые системы поддержки инфраструктуры открытых ключей (Public Key Infrastructure, PKI).

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

Общая схема

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Описание RSA было опубликовано в 1977 году Рональдом Ривестом (Ronald Linn Rivest), Ади Шамиром (Adi Shamir) и Леонардом Адлеманом (Leonard Adleman) из Массачусетского Технологического Института (MIT).

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

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

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

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

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

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

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

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

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

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

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

Зашифрование и расшифрование

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

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

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

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

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

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

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

· значения и дадут при зашифровании шифртексты 0 и 1 при любых значениях и .

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

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

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

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

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

Длина ключа

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

Применение RSA

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

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

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

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

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

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

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

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

С использованием ЭП работа по схеме "разработка проекта в электронном виде - создание бумажной копии для подписи - пересылка бумажной копии с подписью - рассмотрение бумажной копии - перенос ее в электронном виде на компьютер" уходит в прошлое.

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

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

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

Усиленная квалицифированная подпись является разновидностью усиленных, она имеет сертификат от аккредитованного центра и создана с помощью подтвержденных ФСБ средств.

Иностранные электронные подписи приравниваются в России к тем видам подписей, которым они соответствуют.

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

Целям определения лица, подписавшего электронный документ, а также обнаружения факта внесения изменений в документ после его подписания служит усиленная электронная подпись. Именно эта подпись (в двух видах — неквалифицированная и квалифицированная) является аналогом прежней электронной цифровой подписи.

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

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

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

Криптосистема RSA является одной из в наибольшей мерешироко используемой асимметричной криптосистемой (криптосистемой открытого (public) ключа) и зачастую называется стандартом de facto. Вне зависимости от официальных стандартов, существование такого стандарта чрезвычайно важно для развития электронной коммерции и вообще экономики. Единая система открытого (public) ключа допускает обмен документами с электронно-цифровыми подписями между пользователями различных государств, использующими различное программное обеспечение на различных платформах; такая возможность насущно необходима для развития электронной коммерции. Распространение системы RSA дошло до такой степени, что ее учитывают при создании новых стандартов. При разработке стандартов цифровых подписей, в первую очередь в 1997 был разработан стандарт ANSI X9.30, поддерживающий Digital Signature Standard (стандарт Цифровой подписи). Годом позже был введен ANSI X9.31, в котором сделан акцент на цифровых подписях RSA, что отвечает фактически сложившейся ситуации, в частности – для финансовых учреждений.

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

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

Исходный текст M получается адресатом из зашифрованного F(M) путем преобразования: M = (F(M))e (mod pq). Здесь как исходный текст, так и зашифрованный рассматриваются как длинные двоичные числа. Аналогично (Md)e є qM, если dc є (q-1)1. e удовлетворяет этим двум условиям, если cd є (p-1) (q-1)1. Теорема 1 гласит, что мы можем позволить e=x, когда x является решением уравнения dx + (p-1)(q-1)y = 1.

Так как (Md)e – M делимо на p и q, оно делимо и на pq, следовательно, мы можем определить M, зная Md, вычислив его значение в степени e и определив остаток от деления на pq. Для соблюдения секретности важно, чтобы, зная n, было нельзя вычислить p и q. Если n содержит 100 цифр, подбор шифра связан с перебором ~1050 комбинаций. Данная проблема изучается уже около 100 лет. RSA-алгоритм запатентован (20 сентября 1983, действовал до 2000 года).

Теоретически можно предположить, что возможно выполнение операции f-1, не вычисляя p и q. Но в любом случае задача эта не проста и разработчики считают ее трудно факторизуемой.

Предположим, что мы имеем зашифрованный текст f(M) и исходный текст M, и мы хотим найти значения p и q. Нетрудно показать, что таких исходных данных для решения задачи недостаточно – надо знать все возможные значения Mi.

Взлом ЭЦП фактически сводится ко взлому алгоритма шифрования. В данном случае возможные варианты взлома мы рассмотрим на примере алгоритма RSA.

Фактически, задача восстановления секретного ключа эквивалентна задаче разложения на множители (факторинга) модуля: можно использовать d для поиска сомножителей n и наоборот – можно использовать n для поиска d. Надо отметить, что усовершенствование вычислительного оборудования само по себе не уменьшит стойкость криптосистемы RSA, если ключи будут иметь достаточную длину. Фактически же совершенствование оборудования увеличивает стойкость криптосистемы.

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

1. Федеральный закон от 06.04.2011 N 63-ФЗ (ред. от 28.06.2014) "Об электронной подписи" // ИПС Консультант Плюс

2. Агапов, А. В. Обработка и обеспечение безопасности электронных данных [Электронный ресурс] : учеб. пособие / А. В. Агапов, Т. В. Алексеева, А. В. Васильев и др.; под ред. Д. В. Денисова. - М.: МФПУ Синергия, 2013. - 592 с.

3. Куняев, Н. Н. Конфиденциальное делопроизводство и защищенный электронный документооборот [Электронный ресурс] : учебник / Н. Н. Куняев, А. С. Дёмушкин, А. Г. Фабричнов; под общ. ред. Н. Н. Куняева. - М.: Логос, 2014. - 452 с.

4. Молдовян Н.А. Теоретический минимум и алгоритмы цифровой подписи. - СПб.: БХВ-Петербург, 2014. - 293 с.

5. Электронный документооборот. Термины и определения: Учебное пособие / С.Ю. Кабашов. - М.: НИЦ ИНФРА-М, 2013. - 320 с

Чтобы скачать работу бесплатно нужно вступить в нашу группу ВКонтакте. Просто кликните по кнопке ниже. Кстати, в нашей группе мы бесплатно помогаем с написанием учебных работ.

>>>>> Перейти к скачиванию файла с работой
Кстати! В нашей группе ВКонтакте мы бесплатно помогаем с поиском рефератов, курсовых и информации для их написания. Не спешите выходить из группы после загрузки работы, мы ещё можем Вам пригодиться ;)

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

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

Выясняем, как и откуда можно получить электронную подпись на примере криптосистемы RSA.

Содержание

Определения и обозначения

Описание криптосистемы RSA

Асимметричные криптографические системы

Шифрование и дешифрование

Электронная подпись документов

Введение

Наверняка вы сталкивались с таким понятием, как "электронная подпись". Если обратиться к федеральному закону, то можно найти следующее её определение:

Задача ЭП ясна, теперь хотелось бы увидеть и прочувствовать, что именно скрывается за этими двумя словами. Копаясь дальше в гугле, можно найти довольно много различных алгоритмов создания цифровой подписи (DSA, ГОСТ Р 34.10-2012, RSA-PSS и т.д.), разбираться в которых неподготовленному пользователю сложно.

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

Теорминимум

Сформируем небольшой словарик терминов, которые нам пригодятся далее:

Открытый текст – данные, подлежащие шифрованию или полученные в результате расшифрования

Шифртекст – данные, полученные в результате применения шифра к открытому тексту

Шифр – совокупность обратимых преобразований, зависящая от некоторого параметра (ключа)

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

Факторизация – процесс разложения числа на простые множители.

НОД – наибольший общий делитель.

Числа a и b называются взаимно простыми, если НОД этих чисел равен 1.

Функция Эйлера φ(n) – функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним.

Хочу отметить, что на данном этапе подразумевается, что вы знакомы с арифметическими операциями по модулю. Если нет, то здесь можно о них почитать.

Как оно устроено

Прежде, чем ~~окунуться в необъятный мир математики~~ рассмотреть, как именно устроена RSA, обратимся к тому, как работают

Асимметричные криптосистемы

Рассмотрим задачу сохранности содержимого посылки при передаче от отправителя к адресату. Вот картинка с многим полюбившимся Алисой и Бобом:

Теперь к математике

Асимметричные криптографические системы основаны на так называемых односторонних функциях с секретом. Под односторонней понимается такая функция я y=f(x), которая легко вычисляется при имеющемся x, но аргумент x при заданном значении функции вычислить сложно. Аналогично, односторонней функцией с секретом называется функция y=f(x, k), которая легко вычисляется при заданном x, причём при заданном секрете k аргумент x по заданному y восстановить просто, а при неизвестном k – сложно.

Подобным свойством обладает операция возведения числа в степень по модулю:

Что есть что разобрались, теперь перейдём к конкретике, а именно – генерации ключей Боба. Давайте выберем число n такое, что:

где p и q – некоторые разные простые числа. Для такого n функция Эйлера имеет вид:

Такой выбор n обусловлен следующим. Как вы могли заметить ранее, закрытый ключ d можно получить, зная открытый e. Зная числа p и q, вычислить функцию Эйлера не является вычислительно сложной задачей, ровно как и нахождение обратного элемента по модулю. Однако в открытом ключе указано именно число n. Таким образом, чтобы вычислить значение функции Эйлера от n (а затем получить закрытый ключ), необходимо решить задачу факторизации, которая является вычислительно сложной задачей для больших n (в современных системах, основанных на RSA, n имеет длину 2048 бит).

Возвращаемся к генерации ключей. Выберем целое число e:

Для него вычислим число d:

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

Мы завершили с этапом генерации ключей. Теперь Боб публикует свой открытый ключ (e, n), прячет закрытый d, а мы переходим к Алисе.

Шифруем, дешифруем.

Здесь за с обозначен шифртекст, который Алиса будет должна передать Бобу. Отметим также, что c ∈ [1, n − 1], как и m. Расшифруем шифртекст, возведя его в степень закрытого ключа Боба d:

А теперь ответим на вопрос, почему m ≡ m′ . Ниже я приведу доказательство данного утверждения, но если оно (доказательство) вам не сильно интересно, то можете его пропустить и просто поверить, что это так.

Здесь нам понадобится теорема Эйлера:

Также полезной будет китайская теорема об остатках:

Ещё раз напишем две ключевые формулы шифрования и расшифрования соответственно:

Если Алиса получила, что m ≡ m′, то подпись считается правильной.

Дочитавших до этого места хочу поздравить с получением первой цифровой подписи "на бумаге"!

Подпись документов

Рассмотренный алгоритм получения подписи изящен и прост в осознании, однако операция возведения в степень несколько "мешается". Наша текущая задача – подписать объёмный документ. Чтобы сэкономить время, мы не будем подписывать содержимое документа, а прибегнем к помощи хэш-функций (если вы не знаете, что такое хэш-функция, рекомендую почитать википедию). Скажу лишь то, что выходная последовательность хэш-функции имеет небольшую (по сравнению с размером ключей) длину, а также по имеющемуся хэшу нельзя однозначно восстановить исходные данные.

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

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

Заключение

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

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

Спасибо за внимание!

Источники

Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone

Криптографические методы защиты информации: учеб. пособие / С. М. Владимиров, Э. М. Габидулин, А. И. Колыбельников, А. С. Кшевецкий; под ред. А. В. Уривского. – М.: МФТИ, 2016

Маховенко Е. Б. Теоретико-числовые методы в криптографии — М.: Гелиос АРВ, 2006.

NIST Special Publication 800-57 Part 3 Revision 1

Молдовян Н.А. Теоретический минимум и алгоритмы цифровой подписи. – СПб.: БХВ-Петербург, 2010. - Учебное пособие

Читайте также: