Цифровые подписи

 

 

 

 

 

 

 

 

 

 

 

 

 

ЦИФРОВАЯ ПОДПИСЬ ЭЛЬ-ГАМАЛЯ

Схема цифровой подписи  Эль-Гамаля основана на сложности другой задачи — вычисления значения логарифма  в конечном поле.

Пусть р — простое число и α — примитивный элемент поля Z_p. Выберем случайное число а в интервале

1≤а≤ р-2 и вычислим значение β = α^а mod р . Число а является секретным ключом, а набор (р, α, β) — открытым ключом.

Подпись для сообщения М вычисляется с помощью следующего алгоритма:

1. Выбрать случайное целое число r, 1 < r < р - 2 .
2. Вычислить γ = α^r mod р .
3. Для х = М вычислить δ = (х - aγ)r^-1 mod (p - 1).
4. Подписью для сообщения М положить пару (γ,δ)

Алгоритм проверки подписи  заключается в проверке сравнения β^γγ^δ = α^х (mod р). Если оно верно, то подпись принимается, если нет, то отвергается.

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

Сделаем два замечания.

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

а = (х – rγ)δ^-1 mod(p – 1).

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

Второе замечание связано с  тем, что реально при вычислении подписи на шаге 3 алгоритма в  качестве х целесообразнее использовать свертку х = h(M), а не само сообщение М. Это защищает схему подписи от возможности подбора сообщений с известным значением подписи. Существует несколько способов такого подбора. Например, если выбрать случайно числа i, j, удовлетворяющие условиям 0 < i < р -1, 0 < j < р -1,

(j, р - 1) = 1, и положить

γ = αⁱβ^j mod p,

δ = – γj^-1 mod(p – 1),

x = – γij^-1 mod(p – 1),

то  легко убедиться в том, что  пара (γ,δ) является верной цифровой подписью для сообщения М = х.

Схема цифровой подписи Эль-Гамаля послужила  образцом для построения большого семейства во многом сходных по своим свойствам схем подписи. В их основе лежит проверка сравнения вида

α^Aβ^B =γ^C(mod p),

в котором  тройка (А,В,С) совпадает с одной из перестановок чисел ±х, ±δ и ±γ при некотором выборе знаков. Например, исходная схема Эль-Гамаля получается при А = х, В = -γ и С = δ. На базе схем подписи из этого семейства построены и стандарты цифровой подписи США и России. Так, в американском стандарте DSS (Digital Signature Standard) используются значения А = х, В = γ и С = δ, а в российском стандарте — значения А= -х, В = δ и С = γ.

Еще одним достоинством схемы Эль-Гамаля является возможность уменьшения длины  подписи путем замены пары чисел  (γ,δ) на пару чисел (γ mod q, δ mod q), где q является некоторым простым делителем числа р -1 . При этом проверочное равенство по модулю р следует заменить на модифицированное равенство по модулю q:

(α^Aβ^B mod p)mod q = γ^C mod q.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ОДНОРАЗОВЫЕ ЦИФРОВЫЕ ПОДПИСИ

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

Рассмотрим, например, схему цифровой подписи Диффи — Лампорта на основе симметричных систем шифрования.

Пусть требуется подписать сообщение М=m₁m₂...m_n, m_i {0,1}, i = 1,…,n. Согласно схеме Диффи — Лампорта подписывающий сначала выбирает 2n случайных секретных ключей

 

для используемой им симметричной шифристемы, затем n пар случайных чисел

 

где S_ij {0,1}, i = 1,…, n, j = 0,1, и вычисляет значения

 

Наборы S и R = [(R₁₀,R₁₁),...,(R_n0,_Rnl)] являются открытыми и помещаются в общедоступном месте так, чтобы каждый мог прочитать их, но записать их туда мог бы только автор подписи.

Подпись для сообщения М имеет вид

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

 

Недостатком этой схемы  является слишком большой размер подписи, который может превышать  размер самого подписываемого сообщения. Имеется несколько способов избавиться от этого недостатка. Рассмотрим некоторые из них.

Во-первых, можно хранить не 2n значений секретных ключей, а лишь один секретный ключ k. Для этого можно воспользоваться, например, одной из следующих схем формирования последовательности К:

 

 

 

 

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

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

 

 

 

 

ЗАКЛЮЧЕНИЕ

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СПИСОК  ЛИТЕРАТУРЫ

1. Алферов А.П, Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии // М.: Гелиос АРВ, 2001
2. Березин Б.В., Дорошкевич П.В. Цифровая подпись на основе традиционной криптографии // Защита информации. – 1992. – Вып. 2.
3. Цирлов В.Л. Основы информационной безопасности автоматизированных систем // Феникс, 2008
4. Ростовцев А., Маховейко Е. Введение в криптографию с открытым ключом. // СПб.: Мир и семья — Интерлайн, 2001.
5. Петров А. А. Компьютерная безопасность. Криптографические методы защиты. // М.: ДМК, 2000.