Электронная подпись

Можно организовать собственный контроль CRC для идентификации файлов; для этого потребуется переписать через службу PC Magazine Online файл CRC.COM. CRC.COM - это утилита DOS, которой в качестве входного параметра указывается имя файла. Исходя из содержащейся в нем информации, она рассчитывает 32-разрядное значение контроля CRC. В программе использован известный алгоритм расчета параметра CRC-32, применяемый PKZIP и сетевых адаптерах Token-Ring фирмы IBM. Этот алгоритм отличается высоким быстродействием (исходный текст полностью написан на языке ассемблера; производится буферизация при чтении/записи с диска; прекрасно реализован алгоритм расчета CRC-32 - все это позволяет сократить до минимума объем производимых вычислений) и обработает файлы любого размера.

Теперь при пересылке файлов через модем утилита CRC.COM сможет оказать вам неоценимую услугу - дать уверенность, что информация передана без искажений. Получив по сети файл CRC.COM, первым делом проверьте сам этот файл, набрав в строке DOS команду: CRC CRC.COM. Если полученное значение параметра CRC не равно 86C23FA, значит файл следует загрузить снова [2].

 

2.3 АЛГОРИТМ RSA

 

Первой и наиболее известной во всем мире системой электронной подписи стала система RSA, разработанная в 1977 году в Массачусетском технологическом институте (MIT) и названая так по первым буквам фамилий авторов: R. Rivest, A. Shamir, L. Adleman [5]

RSA использует операцию возведения в степень (в дальнейшем будет обозначена символом ^) по модулю для шифровки и дешифровки сообщения, которое получается путем перевода текста в цифровую форму (если речь идет о компьютерах, то текст и так имеет цифровую форм.

Функция шифровки, используемая в RSA выглядит так: C = T^E mod N, где T представляет собой шифруемый текст, C - зашифрованный текст, а E представляет собой открытый ключ. Другими словами, T возводится в степень E по модулю N. Для примера, 2 в степени 3 дает 8, а 2 в степени3 по модулю 7 есть 8 mod 7, что равно 1. Функция дешифрования выглядит так: T = C^D mod N где D представляет собой секретный ключ. Пара ключей E и D должна быть выбрана так, что E является обратным к D по отношению к операции возведения в степень по модулю N. Иными словами, (T^E mod N)^D mod N = T^ED mod N = T.

Для того, чтобы найти подходящую пару, для которой это равенство верно, надо знать функцию Эйлера переноса, J(N) для данного значения модуля N. Функция Эйлера представляет собой количество чисел в интервале от 1 до N-1, которые являются простыми относительно N. Для нахождения функции J(N) , в свою очередь, найти простые факторы N.

Фундаментальная теорема арифметики: Любое не простое число может быть представлено как произведение уникального набора простых чисел.

Относительно простые числа: Два числа называются относительно простыми, если среди их простых факторов нет одинаковых.

Итак, необходимо найти набор простых факторов числа N для того, чтобы вычислить функцию Эйлера. J(N). Нахождение этих факторов является задачей чрезвычайно сложной - практически абсолютно невозможно для достаточно больших N. И именно этот факт и делает PGP таким надежным методом шифрования. Для заданных N и E вы не можете найти D (и, таким образом, расшифровать сообщение) не зная простых факторов числа N, что настолько трудно, что PGP является виртуально невскрываемой при достаточно больших N.

Практический способ сгенерировать пару ключей - это сначала сгенерировать само N путем умножения двух больших простых чисел P и Q, так что простые факторы N мы уже знаем. Для числа, которое имеет только два простых фактора (как в нашем случае), функция Эйлера равна:

 

J(N) = (P-1)(Q-1)

 

Теперь выбирается некоторое число E, которое является простым относительно J(N) (почему именно простым, будет показано ниже). Задача - найти D, которое является обратным к E по отношению к операции возведения в степень по модулю N. Это можно сделать, зная J(N).

Имеется правило в модульной арифметике, гласящее, что если операция возведения в степень использует модуль N, то показатели экспонент должны использовать модуль J(N). Например:

 

(T^E mod N)^D mod N = T^ED mod N

 

Оказывается, что умножать показатели степени E и D нужно с использованием mod J(N), а не mod N. Для того, чтобы для заданного показателя шифровки E найти подходящее обратное число D, нам следует удовлетворить равенство:

 

T^ED mod N = T

 

Для этого достаточно, чтобы ED mod J(N) = 1, так как T^1 mod N = T. Так что проблема нахождения D сводится к проблеме нахождения числа, обратного E по модулю J(N), что с вычислительной точки зрения тривиально. Следует отметить, что в модульной арифметике есть закон, гласящий, что для заданного модуля M число может иметь обратное относительно операции умножения по модулю M только если оно является относительно простым по отношению к M. Вот почему E выбиралось как не имеющее общих простых факторов с J(N), так, чтобы у него имелось обратное D по модулю J(N). Тривиальные комбинации E и D (например E = D) отбрасываются как неподходящие с точки зрения секретности, и тогда берется новое E.

Когда значение N выбрано, а ключи E и D сгенерированы, можно забыть о P, Q и J(N) так как они «сделали свое дело». Теперь есть в наличии подходящие ключи шифровки и дешифровки E и D

 

C = T^E mod N and T = C^D mod N

 

(на самом деле совершенно не важно, какой из ключей D или E считается ключом шифровки). Не зная чисел P и Q практически невозможно вычислить J(N) и, следовательно, найти D по заданному E при больших значениях N, так что шифрование является надежным.

Итоговый список шагов, необходимых для генерации ключа:

•Выбираем пару произвольных больших простых чисел P и Q и находим N путем умножения

•Вычисляем функцию Эйлера числа

 

N, J(N) = (P-1)(Q-1)

 

•Выбираем число E так, чтобы оно было относительно простым по отношению к J(N)

•Находим D, обратное число к E по отношению к операции умножения по модулю J(N), и тривиальные значения отбраковываем как несекретные (E=D)

•Найдя подходящую пару ключей, ключ E объявляем открытым и его можно использовать для шифровки сообщений, адресованных владельцу пары E и D:

 

C = T^E mod N

 

•Ключ D держится в секрете и используется для дешифровки полученных сообщений:

 

T = C^D mod N

 

Надежность RSA

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

Важно отметить, что не было доказано, что безопасность RSA целиком зависит от проблемы нахождения простых факторов большого числа. Однако все другие способы нахождения D по заданному E оказались эквивалентны по затратам задаче факторизации N.

Есть вероятность, что будет найден алгоритм для нахождения E-того корня по модулю N более простым путем, чем факторизация N. Тем не менее, до сих пор не был найден такой алгоритм и RSA выдержал огромное число попыток вскрытия [6].

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.4 АЛГОРИТМ DSA

 

Национальный институт стандартов и технологии США (NIST) разработал федеральный стандарт цифровой подписи DSS. Для создания цифровой подписи используется алгоритм DSA (Digital Signature Algorithm). В качестве хэш-алгоритма стандарт предусматривает использование алгоритма SHA-1 (Secure Hash Algorithm). DSS первоначально был предложен в 1991 году и пересмотрен в 1993 году в ответ на публикации, касающиеся безопасности его схемы.

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

Рассмотрим отличия подхода, используемого в DSS для создания цифровых подписей, от применения таких алгоритмов как RSA.

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

Подход DSS также использует сильную хэш-функцию. Хэш-код является входом функции подписи вместе со случайным числом k, созданным для этой конкретной подписи. Функция подписи также зависит от закрытого ключа отправителя KRa и множества параметров, известных всем участникам. Можно считать, что это множество состоит из глобального открытого ключа KUG. Результатом является подпись, состоящая из двух компонент, обозначенных как s и r.

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

DSS основан на трудности вычисления дискретных логарифмов и базируется на схеме, первоначально представленной ElGamal и Schnorr [1].

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.5 ОТЕЧЕСТВЕННЫЙ СТАНДАРТ ЦИФРОВОЙ ПОДПИСИ ПО ГОСТ 3410

 

В отечественном стандарте ГОСТ 3410, принятом в 1994 году, используется алгоритм, аналогичный алгоритму, реализованному в стандарте DSS. Оба алгоритма относятся к семейству алгоритмов ElGamal.

В стандарте ГОСТ 3410 используется хэш-функция ГОСТ 3411, которая создает хэш-код длиной 256 бит. Это во многом обуславливает требования к выбираемым простым числам p и q:

1. р должно быть простым числом в диапазоне:2509 < p < 2512, либо 21020 < p < 21024

2. q должно быть простым числом в диапазоне: 2254 < q < 2256

q также должно быть делителем (р-1).

Аналогично выбирается и параметр g. При этом требуется, чтобы gq (mod p) = 1.

В соответствии с теоремой Ферма это эквивалентно условию в DSS, что

 

 

g = h(p-1)/q mod p.

 

Закрытым ключом является произвольное число х:

 

0 < x < q

 

Открытым ключом является число y:

 

y = gx mod p

 

Для создания подписи выбирается случайное число k:

 

0 < k < q

 

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

 

r = (gk mod p) mod q

 

s = (k H(M) + xr) mod q

 

Конкретные отличия DSS и ГОСТ 3410:

Используются разные хэш-функции: в ГОСТ 3410 применяется отечественный стандарт на хэш-функции ГОСТ 3411, в DSS используется SHA-1, которые имеют разную длину хэш-кода. Отсюда и разные требования на длину простого числа q: в ГОСТ 3410 длина q должна быть от 254 бит до 256 бит, а в DSS длина q должна быть от 159 бит до 160 бит.

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

 

s = (k H(M) + xr) mod q

 

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

 

s = [k-1 (H(M) + xr)] mod

 

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

Получатель вычисляет:

 

w = H(M)-1 mod q

 

u1 = w s mod q

 

u2 = (q-r) w mod q

 

v = [(gu1 yu2) mod p] mod q

 

Подпись корректна, если v = r.

Структура обоих алгоритмов довольно интересна. Заметим, что значение r совсем не зависит от сообщения. Вместо этого r есть функция от k и трех общих компонент открытого ключа. Мультипликативная инверсия k (mod p) (в случае DSS) или само значение k (в случае ГОСТ 3410) подается в функцию, которая, кроме того, в качестве входа имеет хэш-код сообщения и закрытый ключ пользователя. Эта функция такова, что получатель может вычислить r, используя входное сообщение, подпись, открытый ключ пользователя и общий открытый ключ.

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

Другое важное замечание заключается в том, что экспоненциальные вычисления при создании подписи необходимы только для gk mod p. Так как это значение от подписываемого сообщения не зависит, оно может быть вычислено заранее. Пользователь может заранее просчитать некоторое количество значений r и использовать их по мере необходимости для подписи документов. Еще одна задача состоит в определении мультипликативной инверсии k-1 (в случае DSS). Эти значения также могут быть вычислены заранее.

Подписи, созданные с использованием стандартов ГОСТ 3410 или DSS, называются рандомизированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будут создаваться разные подписи (r,s), поскольку каждый раз будет использоваться новое значение k. Подписи, созданные с применением алгоритма RSA, называются детерминированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будет создаваться одна и та же подпись [1].