Компьютерная безопасность. Криптографические методы защиты - Петров А.А.
ISBN 5-89818-064-8
Скачать (прямая ссылка):
• фальсификация времени отправления сообщения.
Противодействие данным нарушениям может основываться на использовании временных вставок и строгом учете входящих сообщений.
1.4.3. Алгоритм DSA
В 1991 году Национальный институт стандартизации и технологий (NIST) США опубликовал стандарт на ЭЦП (Digital Signature Standard, DSS), в основе которого - алгоритм DSA. Он является аналогом механизма, предложенного Эль Гамалем, но с некоторыми изменениями, в частности за счет уменьшения числового порядка одного из параметров схемы.
В данном стандарте подпись представляет собой два больших целых числа, полученных в соответствии с процедурами и параметрами, определенными в DSS.
Алгоритм DSA является «классическим» примером схемы ЭЦП на основе использования хэш-функции и асимметричного алгоритма шифрования.
Стойкость системы в целом основана на сложности нахождения дискретных логарифмов в конечных полях.
Генерация ЭЦП
Поскольку алгоритм Эль Гамаля является асимметричным алгоритмом шифрования, то параметры системы делятся на три группы:
Электронно-цифровая подпись
71
• общие параметры;
• секретный ключ;
• открытый ключ.
Общие параметры необходимы для функционирования системы в целом. Секретный ключ используется для формирования ЭЦП, а открытый - для проверки ЭЦП. Общими параметрами системы являются простые целые числа р, q и g, удовлетворяющие следующим условиям:
•р: 2511<р<2512;
• q: простой делитель числа (р - 1), который удовлетворяет условию 2159<q<2160;
• g: так называемый генератор, удовлетворяющий равенству g = hp/1/qmod р, где h - любое целое 0 < h < р, при котором hp"1/4mod р > 1.
Параметры р, q и g опубликовываются для всех пользователей системы обмена ЭД с ЭЦП.
Секретный ключ х случайно выбирается пользователем из диапазона [1, q] и держится в секрете.
Открытый ключ у вычисляется следующим образом: у = gxmodp.
Также при описании данной схемы будут использоваться следующие обозначения и дополнительные параметры: m - входное сообщение пользователя для схемы ЭЦП; к - случайное число, удовлетворяющее условию О < к < q, хранящееся в секрете и меняющееся от одной подписи к другой; H - хэш-функция; h - хэш-код сообщения.
Процесс генерации ЭЦП состоит из следующих этапов:
1. Вычисляется хэш-код сообщения m Ii = H(m).
2. Из диапазона [1, q] случайным образом выбирается значение к и вычисляется г = (gkmodp)modq.
3. Вычисляется s = (k'^h'+ xr))modq, где к'1 удовлетворяет условию (k"1k)modq = 1.
Значения г и s являются ЭЦП сообщения ш и передаются вместе с ним по открытым каналам связи.
Проверка ЭЦП
Пусть принято сообщение Hi1 и его подпись S1 и T1 при передаче (m, s, г). Проверка ЭЦП происходит следующим образом:
• проверяется выполнение условий 0 < T1 < q и 0 < S1 < q, и если хотя бы одно из них нарушено, подпись отвергается;
72
Общие сведения по классической криптографии
• вычисляются значения: w = S[1BiOd q
ul = (H(Hi1)W)TnOd q
u2 = ((F1Zw)HiOd q
v = ((gulyu2)mod p)mod q
• проверяется равенство v = T1.
Если последнее равенство выполняется, то подпись принимается. В данном стандарте также специфицируется процедура генерации основных параметров системы и проводится доказательство того, что если v - ти то In1 = m, T1 = THS1 = S.
Стойкость DSA
Криптографическая стойкость схемы DSA против атак методом «грубой силы» в первую очередь зависит от размера параметров р и q (в данном случае 512 и 160 бит). Соответственно криптостойкость против атаки методом «грубой силы» на параметр р будет равна 2160. А успешная атака на параметр q возможна только в том случае, если злоумышленник может вычислять дискретные логарифмы в полях Галуа GF(2512) с количеством предварительных вычислений пропорционально
L(p) = eVlnpln,np.
Одной из теоретически возможных атак на схему DSA является компрометация параметра к. При каждой подписи требуется новое значение к, которое должно быть выбрано случайным образом. Если злоумышленник найдет значение к, употреблявшееся при подписании сообщения (такое возможно, если будут обнаружены некоторые слабости в процедуре генерации к), секретный ключ х может быть воспроизведен. Другой возможный вариант - две подписи были сгенерированы на одном значений k. В этом случае злоумышленник тоже в состоянии восстановить х. Следовательно, одним из факторов, повышающих безопасность использования схем ЭЦП, является наличие «хорошего» генератора случайных чисел.
1.4.4. Стандарт на процедуры выработки и проверки ЭЦП
Отечественным стандартом на процедуры выработки и проверки ЭЦП является ГОСТ P 34.10-94. Схема ЭЦП, предложенная в данном стандарте, во многом напоминает подпись в DSA, поэтому большая часть рассуждений о предыдущем алгоритме справедлива и для данной схемы ЭЦП.
Электронно-цифровая подпись
73
Цифровая подпись представляет собой два больших целых числа. Общедоступные параметры схемы ЭЦП (р, q и а) должны удовлетворять следующим условиям:
• р: 2509< р < 2512 или 21020< р < 21024;
• q: простой делитель (р - 1) и удовлетворяет неравенству 2254 < q < 2256; •г:1<а<р-1и aq(mod р) = 1.
