Что такое цифровая подпись? | Binance Academy

Научная основа

Начало асимметричным шифрам было положено в работе «Новые направления в современной криптографии» Уитфилда Диффи и Мартина Хеллмана, опубликованной в 1976 году. Находясь под влиянием работы Ральфа Меркла о распространении открытого ключа, они предложили метод получения секретных ключей, используя открытый канал.

Этот метод экспоненциального обмена ключей, который стал известен как обмен ключами Диффи — Хеллмана, был первым опубликованным практичным методом для установления разделения секретного ключа между заверенными пользователями канала. В 2002 году Хеллман предложил называть данный алгоритм «Диффи — Хеллмана — Меркле», признавая вклад Меркле в изобретение криптографии с открытым ключом.

Эта же схема была разработана Малькольмом Вильямсоном (англ. Malcolm J.

Williamson) в 1970-х, но держалась в секрете до 1997 года. Метод Меркле по распространению открытого ключа был изобретён в 1974 и опубликован в 1978 году, его также называют загадкой Меркле.

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

Система была названа по первым буквам их фамилий (RSA — Rivest, Shamir, Adleman). Эта же система была изобретена в 1973 годуКлиффордом Коксом (англ. Clifford Cocks), работавшим в центре правительственной связи (GCHQ), но эта работа хранилась лишь во внутренних документах центра, поэтому о её существовании не было известно до 1977 года. RSA стал первым алгоритмом, пригодным и для шифрования, и для цифровой подписи.

Вообще, в основу известных асимметричных криптосистем кладётся одна из сложных математических проблем, которая позволяет строить односторонние функции и функции-лазейки. Например, криптосистемы Меркля — Хеллмана и Хора — Ривеста опираются на так называемую задачу об укладке рюкзака.

Основные принципы построения криптосистем с открытым ключом

1. Начинаем с трудной задачи P{displaystyle P}. Она должна решаться сложно в смысле теории: не должно быть алгоритма, с помощью которого можно было бы перебрать все варианты решения задачи P{displaystyle P} за полиномиальное время относительно размера задачи. Более правильно сказать: не должно быть известного полиномиального алгоритма, решающего данную задачу — так как ни для одной задачи ещё пока не доказано, что для неё подходящего алгоритма нет в принципе.
2. Можно выделить легкую подзадачу P′{displaystyle P’} из P{displaystyle P}. Она должна решаться за полиномиальное время и лучше, если за линейное.
3. «Перетасовываем и взбалтываем» P′{displaystyle P’}, чтобы получить задачу P″{displaystyle P”}, совершенно не похожую на первоначальную. Задача P″{displaystyle P”} должна по крайней мере выглядеть как оригинальная труднорешаемая задача P{displaystyle P}.
4. P″{displaystyle P”} открывается с описанием, как она может быть использована в роли ключа зашифрования. Как из P″{displaystyle P”} получить P′{displaystyle P’}, держится в секрете как секретная лазейка.
5. Криптосистема организована так, что алгоритмы расшифрования для легального пользователя и криптоаналитика существенно различны. В то время как второй решает P″{displaystyle P”}-задачу, первый использует секретную лазейку и решает P′{displaystyle P’}-задачу.

Ключевые термины

DSS (Digital Signature Standard) – стандарт США на цифровую подпись. В основе стандарта лежит алгоритм, называемый DSA (Digital Signature Algorithm) и являющийся вариацией подписи Эль-Гамаля.

ГОСТ Р34.10-2001 – новый российский стандарт на алгоритм формирования и проверки ЭЦП. Основан на сложности взятия дискретного логарифма в группе точек эллиптической кривой, а также на стойкости хэш-функции по ГОСТ Р34.11-94. Размер формируемой цифровой подписи – 512 бит.

ГОСТ Р34.10-94 – российский стандарт на алгоритм формирования и проверки ЭЦП, действующий с 1995 года. В стандарте используется модификация схемы шифрования с открытым ключом Эль-Гамаля и алгоритм выработки хэш-функции по ГОСТ Р34.11-94.

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

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

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

Криптоанализ алгоритмов с открытым ключом

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

В этой модели Ева перехватывает открытый ключ e{displaystyle e}, посланный Бобом Алисе. Затем создает пару ключей e′{displaystyle e’} и d′{displaystyle d’}, «маскируется» под Боба, посылая Алисе открытый ключ e′{displaystyle e’}, который, как думает Алиса, открытый ключ, посланный ей Бобом. Ева перехватывает зашифрованные сообщения от Алисы к Бобу, расшифровывает их с помощью секретного ключа d′{displaystyle d’}, заново зашифровывает открытым ключом e{displaystyle e} Боба и отправляет сообщение Бобу. Таким образом, никто из участников не догадывается, что есть третье лицо, которое может как просто перехватить сообщение m{displaystyle m}, так и подменить его на ложное сообщение m′{displaystyle m’}. Это подчеркивает необходимость аутентификации открытых ключей. Для этого обычно используют сертификаты. Распределённое управление ключами в PGP решает возникшую проблему с помощью поручителей^{[5][неавторитетный источник?][источник не указан 2860 дней]}.
Ещё одна форма атаки — вычисление закрытого ключа, зная открытый (рисунок ниже). Криптоаналитик знает алгоритм шифрования Ee{displaystyle E_{e}}, анализируя его, пытается найти Dd{displaystyle D_{d}}. Этот процесс упрощается, если криптоаналитик перехватил несколько криптотекстов с, посланных лицом A лицу B.

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

Также задачу разложения потенциально можно решить с помощью алгоритма Шора при использовании достаточно мощного квантового компьютера.

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

В частности, в России к использованию в государственных и коммерческих организациях разрешены только те программные средства шифрования данных, которые прошли государственную сертификацию в административных органах, в частности, в ФСБ, ФСТЭК[6].

Криптография с несколькими открытыми ключами

Пусть есть 3 ключа KA{displaystyle K_{A}}, KB{displaystyle K_{B}}, KC{displaystyle K_{C}}, распределенные так, как показано в таблице.
Тогда Алиса может зашифровать сообщение ключом KA{displaystyle K_{A}}, а Эллен расшифровать ключами KB{displaystyle K_{B}}, KC{displaystyle K_{C}}, Кэрол — зашифровать ключом KC{displaystyle K_{C}}, а Дэйв расшифровать ключами KA{displaystyle K_{A}}, KB{displaystyle K_{B}}. Если Дэйв зашифрует сообщение ключом KA{displaystyle K_{A}}, то сообщение сможет прочитать Эллен, если ключом KB{displaystyle K_{B}}, то его сможет прочитать Франк, если же обоими ключами KA{displaystyle K_{A}} и KB{displaystyle K_{B}}, то сообщение прочитает Кэрол. По аналогии действуют и другие участники.
Таким образом, если используется одно подмножество ключей для шифрования, то для расшифрования требуются оставшиеся ключи множества. Такую схему можно использовать для n ключей.
Рассмотрим для начала множество, состоящее из трех агентов: Алисы, Боба и Кэрол. Алисе выдаются ключи KA{displaystyle K_{A}} и KB{displaystyle K_{B}}, Бобу — KB{displaystyle K_{B}} и KC{displaystyle K_{C}}, Кэрол — KA{displaystyle K_{A}} и KC{displaystyle K_{C}}. Теперь, если отправляемое сообщение зашифровано ключом KC{displaystyle K_{C}}, то его сможет прочитать только Алиса, последовательно применяя ключи KA{displaystyle K_{A}} и KB{displaystyle K_{B}}. Если нужно отправить сообщение Бобу, сообщение шифруется ключом KA{displaystyle K_{A}}, Кэрол — ключом KB{displaystyle K_{B}}. Если нужно отправить сообщение и Алисе и Кэрол, то для шифрования используются ключи KB{displaystyle K_{B}} и KC{displaystyle K_{C}}.
Преимущество этой схемы заключается в том, что для её реализации нужно только одно сообщение и n ключей (в схеме с n агентами). Если передаются индивидуальные сообщения, то есть используются отдельные ключи для каждого агента (всего n ключей) и каждого сообщения, то для передачи сообщений всем различным подмножествам требуется 2n−2{displaystyle 2^{n}-2} ключей.

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

Новый отечественный стандарт эцп

В 2001 г. был принят новый отечественный стандарт на алгоритм формирования и проверки ЭЦП. Его полное название следующее: “ГОСТ Р34.10-2001. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи”.

Данный алгоритм был разработан главным управлением безопасности связи Федерального агентства правительственной связи и информации при Президенте Российской Федерации при участии Всероссийского научно-исследовательского института стандартизации. Новый стандарт разрабатывался с целью обеспечения большей стойкости алгоритма генерации ЭЦП.

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

В целом алгоритм вычислений по алгоритму ГОСТ Р34.10-2001 аналогичен применяемому в предыдущем стандарте ГОСТ Р34.10-94. Сначала генерируется случайное число k, с его помощью вычисляется компонента r подписи.

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

Старый ГОСТ Р34.10-94 не отменен, и в настоящее время параллельно действуют два отечественных стандарта на ЭЦП. Однако необходимо отметить, что для прежнего ГОСТа принято ограничение: при реализации ЭЦП по стандарту ГОСТ Р34.10-94 разрешено использовать только 1024-битные значения параметра p.

Использование математического аппарата группы точек эллиптической кривой в новом ГОСТ Р34.10-2001 позволяет существенно сократить порядок модуля p без потери криптостойкости. Так, в стандарте указано, что длина числа р может быть 256 или больше бит.

Пример создания и проверки подписи по стандарту гост р34.10-94

Пусть p = 23, q = 11, a =6 (проверяем: 611 mod 23 = 1 )

Создание подписи.

Предположим, пользователь А выбрал в качестве закрытого ключа число х=8. После этого он вычисляет открытый ключ по формуле y = аx mod p. То есть y = 68 mod 23 = 18.

Для создания подписи пользователь А выбирает случайное число k = 5.

Пусть результат вычисления хеш-функции для сообщения H(m) = 9.

Подпись сообщения состоит из двух чисел (r, s):

Таким образом, подпись сообщения состоит из пары чисел (2, 6).

Проверка подписи.

Получив сообщение вместе с подписью (2, 6), получатель вычисляет

Так как v = r, то подпись считается верной.

Подписи, созданные с использованием стандартов ГОСТ Р34.10 или DSS, так же, как и подписи, полученные по алгоритму Эль-Гамаля, являются рандомизированными, так как для одинаковых сообщений с использованием одного и того же закрытого ключа х каждый раз будут создаваться разные подписи (r,s) благодаря использованию разных случайных значений k.

Реализация через одностороннюю функцию

Идея криптографии с открытым ключом очень тесно связана с идеей односторонних функций, то есть таких функций f(x){displaystyle f(x)}, что по известному x{displaystyle x} довольно просто найти значение f(x){displaystyle f(x)}, тогда как определение x{displaystyle x} из f(x){displaystyle f(x)} невозможно за разумный срок.
Но сама односторонняя функция бесполезна в применении: ею можно зашифровать сообщение, но расшифровать нельзя. Поэтому криптография с открытым ключом использует односторонние функции с лазейкой. Лазейка — это некий секрет, который помогает расшифровать. То есть существует такой y{displaystyle y}, что, зная f(x){displaystyle f(x)} и y{displaystyle y}, можно вычислить x{displaystyle x}. Например, если разобрать часы на множество составных частей, то очень сложно собрать вновь работающие часы. Но если есть инструкция по сборке (лазейка), то можно легко решить эту проблему.
Получатель информации формирует открытый ключ и «лазейку» (другими словами, открытую и закрытую часть ключа), затем передает открытый ключ отправителю, а «лазейку» оставляет у себя. Отправитель шифрует информацию на основе открытого ключа: такую зашифрованную информацию просто расшифровать, лишь имея одновременно и открытый ключ, и «лазейку». В терминах функции, получатель формирует f(){displaystyle f()} с лазейкой y{displaystyle y}, затем передает информацию о параметрах функции f(){displaystyle f()} отправителю (при этом, даже зная параметры функции f(){displaystyle f()}, невозможно обнаружить «лазейку» за разумный срок). После этого отправитель формирует шифрованное сообщение f(x){displaystyle f(x)}, а получатель извлекает x{displaystyle x} из f(x){displaystyle f(x)}, зная y{displaystyle y}.

Стандарт цифровой подписи dss

Во многих странах сегодня существуют стандарты на электронную (цифровую) подпись. Стандарт цифровой подписи DSS (Digital Signature Standard – DSS) был принят в США в 1991 году и пересмотрен в 1994 году.

В основе стандарта лежит алгоритм, называемый DSA (Digital Signature Algorithm) и являющийся вариацией подписи Эль-Гамаля. В алгоритме используется однонаправленная хеш-функция H(m). В качестве хэш-алгоритма стандарт DSS предусматривает использование алгоритма SHA-1.

Рассмотрим сам алгоритм генерации ЭЦП. Вначале для группы абонентов выбираются три общих (несекретных) параметра р, q и a:

Зная эти числа, каждый абонент системы случайно выбирает число х, удовлетворяющее неравенству 0 < х < q, и вычисляет

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

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

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

1. Вычислить значение хеш-функции h = H(m) для сообщения m. Значение хеш-функции должно лежать в пределах 0 < h < q.
2. Затем сгенерировать случайное число k, 0 < k < q.
3. Вычислить r = (a^k mod p) mod q.
4. Определить s = [k^-1}(H(m) x * r)] mod q

В результате пользователь получит для сообщения m подпись, состоящую из пары чисел (r,s). Сообщение вместе с подписью может быть послано любому другому абоненту системы. Проверить подпись можно следующим образом:

1. Вычислить значение хеш-функции h = H(m) для сообщения m.
2. Проверить выполнение неравенств 0 < r < q, 0 < s < q.
3. Вычислить w = s^-1 mod q ;
4. Проверить выполнение равенства v = r. Если v = r, то подпись считается подлинной, иначе подпись считается недействительной.

В силу сложности вычисления дискретных логарифмов злоумышленник не может восстановить k из r или х из s, а следовательно, не может подделать подпись.

Стандарт цифровой подписи гост р34.10-94

В России принят стандарт ГОСТ Р34.10-94 “Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма”. В этом стандарте используется алгоритм, аналогичный алгоритму, реализованному в стандарте DSS.

Вначале, так же как и по стандарту DSS, для группы абонентов выбираются три общих (несекретных) параметра р, q и a:

Подпись сообщения m состоит из двух чисел (r, s), вычисляемых по следующим формулам:

где H(m) – результат вычисления хеш-функции для сообщения m.

На этом формирование подписи закончено, и сообщение m вместе с ЭЦП (r,s) может быть отправлено получателю. Теперь отметим отличия алгоритма формирования ЭЦП по ГОСТ Р34.10-94 от алгоритма DSS.

1. Перед вычислением подписи исходное сообщение обрабатывается разными функциями хеширования: в ГОСТ Р34.10-94 применяется отечественный стандарт на хеш-функцию ГОСТ Р34.11-94, в DSS используется SHA-1, которые имеют разную длину хеш-кода. Отсюда и разные требования на длину простого числа q: в ГОСТ Р34.

2. По-разному вычисляется компонента s подписи. В ГОСТ Р34.10-94 компонента s
вычисляется по формуле

а в DSS компонента s вычисляется по формуле

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

В результате процедура проверки подписи по ГОСТ Р34.10-94 заключается в следующем. Получив [m, (r, s)], получатель вычисляет

Затем проверяется равенство вычисленного значения v и полученного в составе ЭЦП параметра r. Подпись считается корректной, если v = r.

В алгоритме создания ЭЦП по ГОСТ Р34.10-94, так же как и в алгоритме DSS, производятся достаточно сложные вычисления, требующие затрат вычислительных ресурсов. Для ускорения процесса генерации подписей по этим алгоритмам можно заранее вычислять некоторое количество значений параметра r, не зависящего от подписываемого сообщения.

Схема шифрования с открытым ключом

Пусть K{displaystyle K} — пространство ключей, а e{displaystyle e} и d{displaystyle d} — ключи шифрования и расшифрования соответственно. Ee{displaystyle E_{e}} — функция шифрования для произвольного ключа e∈K{displaystyle ein K} такая, что Ee(m)=c{displaystyle E_{e}(m)=c}. Здесь c∈C{displaystyle cin C}, где C{displaystyle C} — пространство шифротекстов, а m∈M{displaystyle min M}, где M{displaystyle M} — пространство сообщений.
Dd{displaystyle D_{d}} — функция расшифрования, с помощью которой можно найти исходное сообщение m{displaystyle m}, зная шифротекст c{displaystyle c}: Dd(c)=m{displaystyle D_{d}(c)=m},
{Ee:e∈K}{displaystyle {E_{e}:ein K}} — набор шифрования, а {Dd:d∈K}{displaystyle {D_{d}:din K}} — соответствующий набор для расшифрования. Каждая пара (E,D){displaystyle (E,D)} имеет свойство: зная Ee{displaystyle E_{e}}, невозможно решить уравнение Ee(m)=c{displaystyle E_{e}(m)=c}, то есть для данного произвольного шифротекста c∈C{displaystyle cin C} невозможно найти сообщение m∈M{displaystyle min M}. Это значит, что по данному e{displaystyle e} невозможно определить соответствующий ключ расшифрования d{displaystyle d}. Ee{displaystyle E_{e}} является односторонней функцией, а d{displaystyle d} — лазейкой^[3].

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

1. Боб выбирает пару (e,d){displaystyle (e,d)} и шлёт ключ шифрования e{displaystyle e} (открытый ключ) Алисе по открытому каналу, а ключ расшифрования d{displaystyle d} (закрытый ключ) защищён и секретен (он не должен передаваться по открытому каналу).
2. Чтобы послать сообщение m{displaystyle m} Бобу, Алиса применяет функцию шифрования, определённую открытым ключом e{displaystyle e}: Ee(m)=c{displaystyle E_{e}(m)=c}, c{displaystyle c} — полученный шифротекст.
3. Боб расшифровывает шифротекст c{displaystyle c}, применяя обратное преобразование Dd{displaystyle D_{d}}, однозначно определённое значением d{displaystyle d}.