Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Ярославский государственный университет имени П.Г. Демидова

Математический факультет

Курсовая работа

Алгоритмы Цифровой Подписи

Выполнил студент группы КБ-5

Шишков Алексей

Научный руководитель

доцент кафедры КБ и ММОИ Белова Л.Ю.

Ярославль 2011 год



Содержание

Введение

1. Основные понятия связанные с ЭЦП

2. Назначение и применение ЭЦП

3. Использование хэш-функций

4. Схемы построения алгоритмов цифровой подписи

4.1 На основе алгоритмов симметричного шифрования

4.2 На основе алгоритмов асимметричного шифрования

5. Схема цифровой подписи RSA

6. Схема цифровой подписи ElGamal

7. Схема цифровой подписи Шнорра

8. Американский стандарт цифровой подписи DSS

9. Отечественный стандарт ЦП ГОСТ 34.10 (94г)

10. Кpиптосистемы на основе эллиптических уpавнений

11. Схема цифровой подписи ECDSA

12. Российский стандарт ГОСТ Р 34.10-2001

13. Симметричная схема цифровой подписи Диффи - Лампорта

14. Алгоритмы Слепой подписи

15. Управление открытыми ключами

16. Хранение закрытого ключа

Заключение

Список литературы



Введение

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

И рассмотреть некоторые из алгоритмов, которые, вероятно, будут активно использоваться в будущем.

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

электронный цифровой подпись шифрование



1. Основные понятия связанные с ЭЦП

(Федеральный закон Российской Федерации от 6 апреля 2011 г. N 63-ФЗ "Об электронной подписи")

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

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

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

4) владелец сертификата ключа проверки электронной подписи - лицо, которому в установленном настоящим Федеральным законом порядке выдан сертификат ключа проверки электронной подписи;

5) ключ электронной подписи - уникальная последовательность символов, предназначенная для создания электронной подписи;

6) ключ проверки электронной подписи - уникальная последовательность символов, однозначно связанная с ключом электронной подписи и предназначенная для проверки подлинности электронной подписи;

7) удостоверяющий центр - юридическое лицо или индивидуальный предприниматель, осуществляющие функции по созданию и выдаче сертификатов ключей проверки электронных подписей, а также иные функции, предусмотренные настоящим Федеральным законом;

8) аккредитация удостоверяющего центра - признание уполномоченным федеральным органом соответствия удостоверяющего центра требованиям настоящего Федерального закона;

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

10) средства удостоверяющего центра - программные и (или) аппаратные средства, используемые для реализации функций удостоверяющего центра;

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

12) корпоративная информационная система - информационная система, участники электронного взаимодействия в которой составляют определенный круг лиц;

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



2. Назначение и применение ЭЦП

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

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

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

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

Доказательное подтверждение авторства документа: Так как создать корректную подпись можно, лишь зная закрытый ключ, а он должен быть известен только владельцу, то владелец пары ключей может доказать своё авторство подписи под документом. В зависимости от деталей определения документа могут быть подписаны такие поля, как «автор», «внесённые изменения», «метка времени» и т. д.



3. Использование хэш-функций

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

Использование хэш-функций даёт следующие преимущества:

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

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

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

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



4. Схемы построения алгоритмов цифровой подписи

4.1 На основе алгоритмов симметричного шифрования

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

1. Стойкость симметричных схем ЭЦП вытекает из стойкости используемых блочных шифров, надежность которых хорошо изучена.

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

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

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

4.2 На основе алгоритмов асимметричного шифрования

На данный момент такие схемы ЭЦП наиболее распространены и находят широкое применение.

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

Общепризнанная схема цифровой подписи охватывает три процесса:

1. Генерация ключевой пары. При помощи алгоритма генерации ключа равновероятным образом из набора возможных закрытых ключей выбирается закрытый ключ, вычисляется соответствующий ему открытый ключ.

2. Формирование подписи. Для заданного электронного документа с помощью закрытого ключа вычисляется подпись.

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

Для того, чтобы использование цифровой подписи имело смысл, необходимо выполнение двух условий:

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

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

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

1. Задачу дискретного логарифмирования

2. Задачу факторизации, то есть разложения числа на простые множители

Вычисления тоже могут производиться двумя способами:

1. на базе математического аппарата эллиптических кривых

2. на базе полей Галуа

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

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

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



5. Схема цифровой подписи RSA

История: Описание RSA было опубликовано в 1977 году Рональдом Райвестом (Ronald Linn Rivest), Ади Шамиром (Adi Shamir) и Леонардом Адлеманом (Leonard Adleman) из Массачусетского Технологического Института (MIT).Британский математик Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал аналогичную систему в 1973 году во внутренних документах центра, но эта работа не была раскрыта до 1977 года и Райвест, Шамир и Адлеман разработали RSA независимо от работы Кокса.

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

Генерация ключей: Генерация ключей в схеме цифровой подписи RSА точно такая же, как и генерация ключей в криптографической системе RSА. Алиса выбирает два простых числа p и q и вычисляет n = p * q. Алиса вычисляет ц(n) = (p - 1) (q - 1). Затем она выбирает e, для общедоступного ключа и вычисляет d для частного ключа, такое, что e * d = 1 mod ц(n). Алиса сохраняет d и публично объявляет n и e.



Подписание:

1. Алиса на основе сообщения M создает подпись S, используя секретный ключ (d, n): S = M^d mod n.

2. Передает сообщение и подпись Бобу (M, S).

Проверка:

1. Боб получает М и S.

2. Применяет общедоступный ключ Алисы (n, e) к подписи, чтобы создать копию сообщения М' = S^e mod n.

3. Боб сравнивает значение М' со значением М. Если два значения совпадают, Боб принимает сообщение.



6. Схема цифровой подписи ElGamal

История: Схема была предложена Тахером Эль - Гамалем в 1984 году.

Эль - Гамаль разработал один из вариантов алгоритма Диффи - Хеллмана. Он усовершенствовал систему Диффи - Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличии от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию.

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

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

1. Генерируется случайное простое число P длины n битов.

2. Выбирается произвольное целое число g, являющееся первообразным корнем по модулю P.

3. Выбирается случайное целое число x такое, что 1 < x < P.

4. Вычисляется y = g^x mod p.

5. Открытым ключом является тройка (p, g, y), закрытым ключом - x.

Подписание:

1. Вычисляется хэш сообщения M: m = h(M).

2. Выбирается случайное число 1 < k < p - 1 взаимно простое с p - 1 и вычисляется r = g^k mod p.

3. С помощью расширенного алгоритма Евклида вычисляется число s, удовлетворяющее сравнению: m ? xr + ks (mod p - 1).

4. Подписью сообщения M является пара (r, s).

Проверка: Зная открытый ключ (p, g, y), подпись (r, s) сообщения M проверяется следующим образом:

1. Проверяется выполнимость условий: 0 < r < p и 0 < s < p - 1. Если хотя бы одно из них не выполняется,то подпись считается неверной.

2. Вычисляется хэш m = h(M).

3. Подпись считается верной, если выполняется сравнение: g^r r^s mod p? g^m mod p.



7. Схема цифровой подписи Шнорра

Проблема схемы цифровой подписи Эль - Гамаля в том, что p должно быть очень большим, чтобы сделать трудной проблему дискретного логарифма Zp*. Рекомендуется длина p по крайней мере 1024 битов. Можно сделать подпись размером 2048 бит. Чтобы уменьшить размер подписи, Шнорр предложил новую схему, основанную на схеме Эль-Гамаля , но с уменьшенным размером подписи.

Генерация ключей: Перед подписанием сообщения Алиса должна генерировать ключи и объявить всем общедоступные ключи.

1. Алиса выбирает простое число p, которое обычно равно по длине 1024 битам.

2. Алиса выбирает другое простое число q, которое имеет тот же самый размер, что и хэш, созданный функцией криптографического хэширования (?160). q | (p - 1), другими словами, (p - 1) = 0 mod q.

3. Алиса выбирает e₁, q-тый корень которого был бы равен 1 mod p. Чтобы сделать это, Алиса выбирает примитивный элемент в Zp, e₀ и вычисляет e₁ = e₀^(p-1)/q mod p.

4. Алиса выбирает целое число d, как свой секретный ключ.

5. Алиса вычисляет e₂ = e₁^d mod p.

Общедоступный ключ Алисы - (e_1, e₂, p, q), ее секретный ключ - (d).

Подписание:

1. Алиса выбирает случайное число r. (меняется каждый раз при новом сообщении) такое что 1 < r < q.

2. Алиса вычисляет первую подпись S₁ = h(M | e₁^r mod p) . Сообщение присоединяется спереди к значению e₁^r mod p, затем применяется хэш-функция, чтобы создать хэш. хэш-функция непосредственно не применяется к сообщению, но вместо этого она получается из последовательного соединения М и e₁^r mod p.

3. Алиса вычисляет вторую подпись S₂ = r + d * S₁ mod q.

4. Алиса передает М, S₁ и S₂.

Проверка: Приемник, например Боб, получает М, S₁ и S₂.

1. Боб вычисляет V = h (М | e₁^S2 * e₂^-S1 mod p).

2. Если S₂ сравнимо с V по модулю p, сообщение принято; иначе оно отклоняется.



8. Американский стандарт цифровой подписи DSS

История: Стандарт цифровой подписи (DSS - Digital Signature Standard) был принят национальным Институтом Стандартов и Технологии (NIST) в 1994 г. NIST издал DSS как FIPS-186 (FEDERAL INFORMATION PROCESSING STANDARD 186). DSS применяет алгоритм цифровой подписи (DSA), основанный на схеме Эль - Гамаля, с использованием некоторых идей из схемы Шнорра.

Параметры схемы цифровой подписи: Для построения системы цифровой подписи желающий должен произвести следующие действия:

1. Выбор криптографической хеш-функции h(x).

2. Выбор большого простого числа q, размерность которого N в битах совпадает с размерностью в битах значений хэш-функции h(x). (изначально значение N было равно 160)

3. Выбор простого числа p, такого, что q | (p - 1). Битовая длина p обозначается L (2^{L ? 1} < p < 2^L).

4. Выбор числа g такого, что его мультипликативный порядок по модулю p равен q. Для его вычисления можно воспользоваться формулой g = h^(p-1)/q mod p , где h -- некоторое произвольное число, 1 < h < p - 1такое, что g ? 1.

Первоочередным параметром схемы цифровой подписи является используемая криптографическая хэш-функция. Важной характеристикой этой функции является битовая длина выходной последовательности. Стойкость криптосистемы на основе DSA не превосходит стойкость используемой хэш-функции и стойкость пары (L, N), чья стойкость не больше стойкости каждого из чисел по отдельности. Ранее рекомендовалась длина p L = 1024 бита.

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

1. Секретный ключ представляет собой число x: 0 < x < q.

2. Открытый ключ вычисляется по формуле y = g^x mod p.

Открытыми параметрами являются числа (p, q, g, y). Закрытый параметр только один -- число x. При этом числа (p, q, g) могут быть общими для группы пользователей, а числа x и y являются соответственно закрытым и открытым ключами конкретного пользователя. При подписании сообщения используются секретные числа x и k, причем число k должно выбираться случайным образом (на практике псевдослучайным) при подписывании каждого следующего сообщения.

Подписание:

1. Выбор случайного числа k: 0 < k < q.

2. Вычисление r = (g^k mod p) mod q.

3. Вычисление s = k^-1 (h(M) + x * r) mod q.

4. Выбор другого k, если оказалось, что r = 0 или s = 0.

Подписью является пара чисел (r, s), общая длина подписи 2*N.

Проверка:

1. Вычисление w = s^-1 mod q.

2. Вычисление u₁ = h(M) * w mod q.

3. Вычисление u₂ = r * w mod q.

4. Вычисление v = (g^u1 * y^u2 mod p) mod q.

Подпись верна, если v = r.

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



9. Отечественный стандарт цифровой подписи ГОСТ 34.10 (94г)

История: В отечественном стандарте ГОСТ 34.10, принятом в 1994 году (сейчас используется ГОСТ 34.10 принятый в 2001 году), используется алгоритм, аналогичный алгоритму, реализованному в стандарте DSS. Оба алгоритма относятся к семейству алгоритмов ElGamal.

Параметры схемы цифровой подписи: В стандарте ГОСТ 34.10 используется хэш-функция ГОСТ 3411, которая создает хэш-код длиной 256 бит. Это во многом обуславливает требования к выбираемым простым числам p и q:

1. р должно быть простым числом в диапазоне 2⁵⁰⁹ < p < 2⁵¹² либо 2¹⁰²⁰ < p < 2¹⁰²⁴

2. q должно быть простым числом в диапазоне 2²⁵⁴ < q < 2²⁵⁶ также q должно быть делителем (р - 1).

3. Аналогично выбирается и параметр g. При этом требуется, чтобы g^q (mod p) = 1. В соответствии с теоремой Ферма это эквивалентно условию в DSS, что g = h^(p-1)/q mod p.

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

1. ключом является произвольное число х: 0 < x < q.

2. Закрытым Открытым ключом является число y: y = g^x mod p.

Подписывание: Для создания подписи выбирается случайное число k такое что, 0 < k < q. Подпись состоит из двух чисел (r, s), вычисляемых по следующим формулам:

1. r = (g^k mod p) mod q.

2. s = k (h(M) + x*r) mod q.

Отличия DSS и ГОСТ 34.10:

1. Используются разные хэш-функции: в ГОСТ 34.10 применяется отечественный стандарт на хэш-функции ГОСТ 34.11, в DSS используется SHA-1, которые имеют разную длину хэш-кода. Отсюда и разные требования на длину простого числа q: в ГОСТ 34.10 длина q должна быть от 254 бит до 256 бит, а в DSS длина q должна быть от 159 бит до 160 бит.

2. По-разному вычисляется компонента s подписи. В ГОСТ 34.10 компонента s вычисляется по формуле s = k (h(M) + x*r) mod q В DSS - по формуле s = [k^-1 (h(M) + x*r)] mod q

3. Последнее отличие приводит к соответствующим отличиям в формулах для проверки подписи.

Проверка:

1. Вычисление w = h(M)^-1 mod q.

2. Вычисление u₁ = w*s mod q.

3. Вычисление u₂ = (q - r) * w mod q.

4. Вычисление v = [(g^u1 * y^u2) mod p] mod q.

Подпись верна, если v = r.



10. Кpиптосистемы на основе эллиптических уpавнений

Эллиптические кpивые - математический объект, котоpый может опpеделен над любым полем (конечным, действительным, pациональным или комплексным). В кpиптогpафии обычно используются конечные поля. Эллиптическая кpивая есть множество точек (x,y), удовлетвоpяющее следующему уpавнению:

y² = x³ + ax + b,

а также бесконечно удаленная точка. Для точек на кpивой довольно легко вводится опеpация сложения, котоpая игpает ту же pоль, что и опеpация умножения в кpиптосистемах RSA и Эль-Гамаля. В pеальных кpиптосистемах на базе эллиптических уpавнений используется уpавнение

y² = x³ + ax + b mod p,

где p - пpостое.

Пpоблема дискpетного логаpифма на эллиптической кpивой состоит в следующем: дана точка G на эллиптической кpивой поpядка r (количество точек на кpивой) и дpугая точка Y на этой же кpивой. Нужно найти единственную точку x такую, что Y = xG, то есть Y есть х-я степень G.



11. Схема цифровой подписи ECDSA

История: ECDSA (Elliptic Curve Digital Signature Algorithm) - алгоритм с открытым ключом для создания цифровой подписи, аналогичный по своему строению DSA, но определённый в отличие от него не над полем целых чисел, а в группе точек эллиптической кривой.

Алгоритм ECDSA в 1999 г. был принят, как стандарт ANSI, в 2000 г. - как стандарт IEEE и NIST. Также в 1998 г. алгоритм был принят стандартом ISO.

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

Параметры алгоритма:

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

2. Выбор большого простого числа q - порядок одной из циклических подгрупп группы точек эллиптической кривой. Если размерность этого числа в битах меньше размерности в битах значений хэш-функции h(x) то используются только левые биты значения хэш-функции.

3. Простым числом p обозначается характеристика поля координат F_p.

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

1. Алиса выбирает эллиптическую кривую Ep (a, b) с простым числом p.

2. Алиса выбирает другое простое число q, чтобы использовать для вычисления.

3. Алиса выбирает секретный ключ d, целое число.

4. Алиса выбирает точку на кривой e₁(.,….).

5. Алиса вычисляет e₂ (..,....) = d * e₁ (......), другую точку на кривой.

Общедоступный ключ Алисы - (a, b, p, q, e₁, e₂), ее секретный ключ - d.

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

1. Алиса выбирает секретное случайное число r, между 1 и q - 1.

2. Алиса выбирает третью точку на кривой P (u, v) = r * e₁ (......).

3. Алиса использует первые координаты P (u, v), чтобы вычислить первую подпись S_1.: S₁ = u mod q.

4. Алиса использует хэш сообщения, свой секретный ключ d, секретное случайное число r и S₁, чтобы вычислить вторую подпись S₂ = (h(M) + d * S₁) r ^-1 mod q,

5. Алиса передает М, S₁ и S₂.

Проверка: Процесс проверки состоит главным образом из восстановления третьей точки и подтверждения, что первая координата эквивалентна S₁ по модулю q. Так как третья точка была создана подписывающим лицом, использующим секретное случайное число r. А верификатор не имеет этого значения. Ему нужно создать третью точку из хэша сообщения, S_1, и S₂.

1. Боб применяет М, S₁ и S₂ для создания двух промежуточных результатов A и B:

2. A = h(M)S₂^-1 mod q.

3. B = S₂^-1 S₁ mod q.

4. Затем Боб восстанавливает третью точку T(x, y) = A * e₁( … , …) + B * e₂( … , …)

5. Боб использует первую координату из T(x, y), чтобы проверить сообщение. Если x = S₁ mod q, подпись принимается, иначе - отклоняется.



12. Российский стандарт ГОСТ Р 34.10-2001

История: полное название: «ГОСТ Р 34.10-2001. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи» - российский стандарт, описывающий алгоритмы формирования и проверки электронной цифровой подписи. Принят и введён в действие Постановлением Госстандарта России от 12 сентября 2001 года.

Данный алгоритм разработан главным управлением безопасности связи Федерального агентства правительственной связи и информации при Президенте Российской Федерации при участии Всероссийского научно-исследовательского института стандартизации. Разрабатывался взамен ГОСТ Р 34.10-94 для обеспечения большей стойкости алгоритма.

Описание алгоритма: ГОСТ Р 34.10-2001 основан на эллиптических кривых. Его стойкость основывается на сложности вычисления дискретного логарифма в группе точек эллиптической кривой, а также на стойкости хэш-функции по ГОСТ Р 34.11-94.

После подписывания сообщения М к нему дописывается цифровая подпись размером 512 бит и текстовое поле. В текстовом поле могут содержаться, например, дата и время отправки или различные данные об отправителе.

Параметры схемы цифровой подписи:

1. Простое число p -- модуль эллиптической кривой такой, что p > 2²⁵⁵

2. Эллиптическая кривая E задается своим инвариантом J(E) или коэффициентами a, b Є F_p где F_p --конечное простое поле. J(E) связан с коэффициентами a и b следующим образом

,

при этом 4a³ + 27b² ? 0 (mod p).

3. Целое число m -- порядок группы точек эллиптической кривой (то есть число элементов группы). m не должно совпадать с p.

4. Простое число q, порядок одной из циклических подгрупп группы точек эллиптической кривой, то есть выполняется m = nq, для некоторого n - натурального. Так же q лежит в пределах 2²⁵⁴ < q < 2²⁵⁶.

5. Точка P(x_p, y_p) ? 0 эллиптической кривой E, являющаяся генератором подгруппы порядка q, или другими словами qP = 0. Здесь qP = P + P + ...(q раз). А 0 - нулевой элемент группы точек эллиптической кривой.

6. h(M) -- хэш-функция (ГОСТ Р 34.11-94) длина хэша - 256 бит.

7. Каждый пользователь цифровой подписи имеет личные ключи: 1) ключ шифрования d - целое число, лежащее в пределах 0 < d < q. 2) ключ расшифрования Q (x_q, y_q ) - точка эллиптич. кривой, dP = Q.

8. При этом должны выполняться: 1) p^t ? 1 (mod q) , где B ? 31. 2) J(E) ? 0 и J (E) ? 1728.

Подписывание:

1. Вычисление хэш-функции от сообщения М: m = h(M)

2. Вычисление e = z (mod q), и если e = 0, положить e = 1. Где z -- целое число соответствующее m

3. Генерация случайного числа k, такого что 0 < k < q

4. Вычисление точки эллиптической кривой C = kP, и по ней нахождение r = x_c (mod q) (x_c -- координата x точки C). Если r = 0, возвращаемся к предыдущему шагу.

5. Нахождение s = rd + ke (mod q). Если s = 0, возвращаемся к шагу 3.

6. Формирование цифровой подписи (r, s)

Проверка:

1. Если хотя бы одно из неравенств r < q и s < q неверно, то подпись неправильная.

2. Вычисление хэш-функции от сообщения М: m = h(M)

3. Вычисление e = z (mod q), и если e = 0, положить e = 1. Где z - целое число соотвествующее

4. Вычисление v = e - ¹ (mod q)

5. Вычисление z₁ = sv (mod q) и z₂ = - rv (mod q)

6. Вычисление точки эллиптической кривой C = z₁P + z₂Q. И определение R = x_c(mod q), где x_c -- координата x кривой C. В случае равенства R = r подпись правильная, иначе -- неправильная.



13. Симметричная схема цифровой подписи Диффи - Лампорта

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

Пусть требуется подписать сообщение М = m₁ m_2… m_n m_i Є {0, 1} i = 1,..n

Согласно схеме Диффи Лампорта подписывающий сначала выбирает 2n случайных секретных ключей K = [(k_10, k_11),…, (k_n0, k_n1 )] для используемой им симметричной шифросистемы, затем n пар случайных чисел S: S = [(S_10, S_11),…, (S_n0, S_n1 )], где S_ij Є {0, 1} i = 1,..n; j = 0, 1

и вычисляет значения

R_ij = E_kij(S_ij), i = 1,..n; j = 0, 1

Наборы S и R являются открытыми и помещаются в общедоступном месте так, чтобы каждый мог прочитать их, но записать туда мог бы только автор подписи. Подпись для сообщения М имеет вид (k_1,m1,…, k_n,mn )

Чтобы убедиться в её правильности, следует проверить равенства

R_ij = E_kij(S_ij), j= m_i , i = 1,..n



Недостатком этой схемы является слишком большой размер подписи, который может превышать размер самого подписываемого сообщения. Имеется несколько способов избавиться от этого недостатка. Во - первых, хранить не 2n значений секретных ключей, а лишь один секретный ключ k. Для этого можно воспользоваться, например, одной из следующих схем формирования последовательности K: k_{ij =} E_k (i, j), j = 0, 1, i = 1,..n; Во - вторых можно аналогичным образом свернуть набор открытых значений S. В - третьих можно подписывать не само сообщение, а его хэш. Вместе с тем подобные модификации не устраняют главного недостатка рассматриваемых подписей, состоящего в том что после проверки подписи либо весь секретный ключ, либо его часть становятся известными проверяющему. Поэтому рассмотренная схема цифровой подписи является по существу одноразовой.



14. Алгоритмы Слепой подписи

История: Слепая подпись (Blind Signature) - разновидность ЭЦП, особенностью которой является то, что подписывающая сторона не может точно знать содержимое подписываемого документа. Понятие слепой подписи придумано Дэвидом Чаумом (David Chaum), им же предложена первая реализация через алгоритм RSA.

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

Эту схему можно сравнить с конвертом, в котором размещён документ и копировальный лист. Если подписать конверт, то подпись отпечатается на документе, и при вскрытии конверта документ уже будет подписан.

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

Полностью слепая подпись: Дана ситуация: Боб - нотариус. Алисе нужно, чтобы он подписал документ не имея никакого представления о его содержании. Боб только заверяет, что документ нотариально засвидетельствован в указанное время. Тогда они действуют по следующему алгоритму:

1. Алиса берёт документ и умножает его на случайное число. Оно называется маскирующим множителем.

2. Алиса отсылает документ Бобу.

3. Боб подписывает документ и отсылает обратно.

4. Алиса удаляет маскирующий множитель и получает свой документ с подписью.

Этот протокол работает только если функции подписи и умножения коммутативны.

Слепая подпись:

1. Боб готовит n документов на каждом из которых написано некоторое уникальное слово (чем больше n, тем меньше у Боба шансов смошенничать).

2. Боб маскирует каждый документ уникальным маскирующим множителем и отправляет их Алисе.

3. Алиса получает все документы и случайным образом выбирает n-1 из них.

4. Алиса просит Боба выслать маскирующие множители для выбранных документов.

5. Боб делает это.

6. Алиса вскрывает n-1 документов и убеждается что они корректны.

7. Алиса подписывает оставшийся документ и отсылает Бобу.

8. Теперь у Боба есть подписанный Алисой документ с уникальным словом, которое Алиса не знает.

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

1. Алиса выбирает случайным образом число из диапазона от 1 до n. Затем она маскирует m, вычисляя: t = m k^e mod n

2. Боб подписывает t: t^d= ( m k^e )^d mod n

3. Алиса снимает маскировку с t^d, вычисляя s = t^d / k mod n

4. Результатом является s = t^d / k mod n

Применение: Наиболее широкое применение протокол слепых подписей нашёл в сфере цифровых денег. Например, чтобы вкладчик не обманул банк, может использоваться такой протокол: вкладчик пишет одинаковый номинал купюр на ста документах с разными номерами и депонирует в зашифрованном виде у банка. Банк выбирает случайным образом и требует раскрыть 99 (или n-1) конвертов, убеждается, что везде написано $10, а не $1000, тогда подписывает оставшийся конверт вслепую, не видя номера купюры.



15. Управление открытыми ключами

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

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

1. Закрытый ключ известен только его владельцу;

2. Удостоверяющий центр создает сертификат открытого ключа, таким образом удостоверяя этот ключ;

3. Никто не доверяет друг другу, но все доверяют удостоверяющему центру;

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

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



16. Хранение закрытого ключа

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

В настоящее время существуют следующие устройства хранения закрытого ключа:

1. Дискеты

2. Смарт-карты

3. USB-брелоки

4. Таблетки Touch-Memory

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

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



Заключение

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



Список литературы

1. Федеральный закон Российской Федерации от 6 апреля 2011 г. N 63-ФЗ "Об электронной подписи"

2. ГОСТ Р 34.10-2001. Информационные технологии. Криптографическая защита информации. Процессы формирования и проверки цифровой подписи.

...