Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Основным механизмом решения этой проблемы является так называемая цифровая подпись.

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

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

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

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

Вопрос 15

Цифровая подпись Эль Гамаля

Схема основывается на трудности вычисления дискретного логарифма.

Параметры системы

Как и в схеме шифрования Эль Гамаля, вычисления делаются в какой-нибудь группе, в которой трудно вычислять дискретный логарифм, например в Z_p * , где р — простое число, p=2q + 1, q — простое число. Выбирается g — образующий элемент группы.

Ключи

• Закрытый ключ х N (фактически достаточно х Z_p-1).

• Открытый ключ у=g^x.

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

Пусть т — сообщение, h=H(m) — его хэш-сумма. Выбираем k Z_p-1^*(НОД(k,p-1)=1). Находим k^-1 в Z_p-1*. Прячем k: r=g^k. Вычисляем

s=k^-1 (h-xr)mod(p-1)

Пара (r,s) представляет собой цифровую подпись

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

Пусть получено сообщение m, h=H(m) с подписью (r,s). Проверяем

Значение h однозначно определяется парой (r,s).

Доказательство того, что данному h трудно без знания х подобрать такие r и s, чтобы соотношение было выполнено, не известно ни автору [88], ни автору данной работы, как неизвестны и способы решения этой задачи.

Утверждение. Имея цифровую подпись по Эль Гамалю, можно построить правильную подпись для другого значения h.

Доказательство. Если g^h=у^rr^s, выберем А,В,С такие, что

Положим

Пара (r',s') является правильной цифровой подписью для сообщения с хэш-суммой h'.

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

При специальном выборе параметров р и g становится возможным подделывать подписи. Например, в [90] доказывается следующая

Теорема. Если p-1=bw, где b имеет только малые простые делители, и известны образующий элемент d=cw (c<b) и t такое, что d^t=g в Z_p*, то можно построить правильную подпись по Эль Гамалю (r, s) для заданного значения h.

Эскиз доказательства. Подпись строится так:

где

Значение z можно найти, поскольку g^w —образующий элемент подгруппы, имеющей порядок b.

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

Стандарт DSS

Стандарт США DSS (Digital Signature Standard) [91] является развитием схемы Эль Гамаля, но при той же надежности в смысле дискретного логарифма требует возведения в меньшую степень. Кроме того, при разработке стандарта были учтены недостатки схемы Эль Гамаля, например упомянутый способ подбора ненадежных параметров системы. Еще одним побудительным мотивом при разработке DSS стало желание сократить время создания подписи за счет времени проверки (как раз наоборот по сравнению с цифровой подписью RSA).

Параметры системы:

• р — простое число 2^L-1<p<2^L, 512L1024, L делится на 64;

• q—простое, 2¹⁵⁹<q<2¹⁶⁰, p=qt+1;

• g — элемент порядка q в Z_p*, подбирается в виде так, чтобы g не равнялось 1;

• H — криптографически стойкая хэш-функция.

Ключи

• Закрытый ключ х, 0 < х < q.

• Открытый ключ у=g ^x mod p.

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

• m — сообщение, h=H(m) — его хэш-сумма.

• Выбираем. Находим k^-1 в Z_q.

• Прячем k: r=(g^k mod p) mod q.

• Вычисляем s=k^-1 (h + xr) mod q.

• Пара (r,s) представляет собой цифровую подпись.

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

Пусть получено сообщение с хэш-суммой h и подписью (r,s).

• Проверяем 0<r<q и 0<s<q.

• Полагаем и₁=s^-1h mod q, u₂=s^-1 r mod q.

• Проверяем r=(g^u1 y^u2 mod p) mod q.

В том что для правильной подписи проверка пройдет успешно, можно легко убедиться с использованием Малой теоремы Ферма.

Приведем несколько замечаний по поводу надежности схемы DSS.

Замечание. В отличие от схем RSA и Эль Гамаля, в схеме DSS одна и та же подпись может соответствовать сообщениям с различной хэш- суммой.

Доказательство. Отображение t | (g^t modp) modq не является взаимно однозначным, как показывает следующий пример (4 имеет порядок 5 в Z₁₁*):

Пусть известны два значения k₁ и k₂ такие, что

Тогда для любого h₁ можно найти h ₂ из уравнения

Подпись (r,s) окажется правильной как для h₁, так и для h ₂.

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

Замечание. Неизвестно, сводится ли задача подделки подписи DSS задаче вычисления дискретного логарифма.

Замечание. Зная k, можно вычислить r и x. Следовательно, если при построении подписи используется плохой генератор случайных чисел, существует риск раскрытия закрытого ключа.

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

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

Характеристики

Список файлов ответов (шпаргалок)