Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
112
ГЛ. IV. ОТКРЫТЫЙ ключ
предложил стандарт цифровой подписи (Digital Signature Standard, сокращенно, DSS). Как ожидается, роль DSS будет аналогична роли принятого много раньше стандарта шифрования данных (DES), т. е. он будет стандартом цифровой подписи для использования как государственными, так и коммерческими организациями. В отличие от DES, который является классической криптосистемой с секретным ключом, при построении цифровой подписи необходимо использовать криптосистему с открытым ключом. НИСТ заложил в основу своей схемы подписи задачу дискретного логарифмирования в простом конечном поле. DSS очень похож на схему подписи, предложенную первоначально Шнорром (см. ссылки ниже). Он похож также на схему подписи Эль-Гамаля (см. упражнение 9 ниже). Теперь расскажем, как работает DSS.
Чтобы получить возможность подписывать сообщения, каждым пользователем (Алисой) осуществляется следующая последовательность действий: 1) выбирается простое число q приблизительно в 160 бит (для этого используются генератор случайных чисел и тест на простоту); 2) выбирается другое простое число р, сравнимое с 1 по модулю q размером приблизительно в 512 бит; 3) выбирается порождающий элемент д единственной циклической подгруппы в Fp порядка q
(т. е. вычисляется д = д$р 1^4 (mod р) для случайного целого ; если д ф 1, то он и будет порождающим элементом); 4) выбирается секретный ключ как случайное целое число х из диапазона 0 < х < q. В качестве открытого ключа берется у = дх (mod р).
Пусть Алиса хочет подписать сообщение. Сначала она применяет к своему открытому тексту хеш-функцию (см. § 1) и получает целое число h из диапазона 0 < h < q. Затем она выбирает случайное целое к из того же диапазона и вычисляет дк (mod р). Пусть г — наименьший неотрицательный вычет по модулю q последнего выражения , к
(значит, д сначала вычисляется по модулю р, а результат приводится по меньшему простому модулю q). Наконец, Алиса находит такое целое s, что sk = h 4- xr (mod q). Пара (г, s) вычетов по модулю q является ее подписью.
Чтобы проверить подпись, получатель Боб вычисляет щ = s 1Zi (mod q) и U2 = s г (mod q). Потом он вычисляет д гу 2 (mod р). Если результат сравним с г по модулю q, то подпись считается подлинной. (Заметим, что gUlyU2 = д" ^h+xr^ = ^(niod р).)
Достоинством этой схемы является сравнительно малый размер подписи, состоящей из двух чисел по 160 бит (размер q). С другой стороны, надежность системы зависит, очевидно, от сложности решения задачи дискретного логарифмирования в большом конечном поле Fp.
ij 3. ДИСКРЕТНОЕ ЛОГАРИФМИРОВАНИЕ
113
Хотя для вскрытия рассмотренной системы достаточно решения этой задачи в меньшей подгруппе, порожденной д, представляется маловероятным, что эта задача намного проще задачи дискретного логарифмирования для всей группы Fp. Таким образом, DSS, по-видимому, имеет очень высокий уровень надежности при небольшом размере подписи и малом времени на вычисления.
Алгоритмы дискретного логарифмирования в конечных полях. Сначала мы рассмотрим случай, когда все простые делители числа q — 1 малы. Такие числа q — 1 будем называть «гладкими». Для них существует быстрый алгоритм вычисления дискретного логарифма по основанию b элемента из F^. Для простоты будем считать, что b является порождающим элементом группы F*q. Теперь опишем этот алгоритм, предложенный Силвером, Полигом и Хеллманом.
Сначала для каждого простого р, делящего q — 1, вычисляются корни р-й степени из единицы: rpj = b^q при j = 0,1,... ,р — 1. (Как обычно, при возведении b в большую степень используется метод последовательного возведения в квадрат.) Эта таблица значений {fpj} является основой для вычисления дискретного логарифма любого у Є Fg. (Заметим, что при фиксированном b эти вычисления производятся лишь один раз, и одна и та же таблица используется при любом у.)
Наша цель — найти такой элемент х, 0 ^ х < q — 1, что bx = у. Пусть q—l= Y[pр° есть разложение числа q — 1 на простые множители. Достаточно найти х (mod ра) для каждого р, делящего q—l; после этого X однозначно определяется применением алгоритма из доказательства китайской теоремы об остатках (предложение 1.3.3). Итак, мы зафиксируем простое р, делящее q — 1, и покажем, как найти х (mod р ).
Предположим, что X = X0 + X1P + •¦• + xa_ipa 1 (mod ра) с О ^ X1 < р. Для того чтобы найти X0, мы вычисляем т/? 1^. Это корень р-й степени из единицы, так как уч~1 = 1. Из равенства у = Ьх
(q — \)Ip lx(q-1)Ip lxo(q~1)/p ґ~і
следует, что уу = Ь = о = гр^0. Сравниваем
(?-i)/p її ' ¦
y\i с {rpj\0^j<p и полагаем X0 равным тому значению j, при
(<?-1)/р ^
котором у = Гр j.
Далее, чтобы найти X1, мы заменяем у на у1 = у/Ьх°. Тогда ух имеет дискретный логарифм X-X0 = X1P + ¦ ¦ ¦ + 1 (mod ра).
(<?-1)/Р 1 (<?-1)/р2
1ак как у1 — это р-я степень, то получаем у\ = 1 и у\ =
6(.-.о)(?-1)/р2 = ь(*1+ъг+~Кя-1)1р = ь*Ля-1)/р = Грх^ 3начиХ5 мы
(<?-1)/р2 г -і '
можем сравнить у\ с \rpj\ и положить Zi равным тому J, при
(<?-1)/р2 котором у\ " = rpj.
