страница №1
Технология использования цифровой подписи
З А Щ И Т А И Н Ф О Р М А Ц И И
__________________________________
"ЛАН КРИПТО"
ТЕХНОЛОГИЯ
использования цифровой подписи,
открытого распределения ключей и шифрования
в банковских расчетах
Москва 1993
СОДЕРЖАНИЕ.
-----------
1.Что такое электронная подпись................................
2.Алгоритмы электронной подписи................................
3.Что такое шифрование с открытым распределением ключей........
4.Технология применения шифрования с открытыми
ключами и электронной подписи в банковских
расчетах.....................................................
1.ЧТО ТАКОЕ "ЭЛЕКТРОННАЯ ПОДПИСЬ"
---------------------------------
Отсутствие электронного эквивалента подписи в 60-70 годы
являлось фактором, сдерживающим широкое внедрение безбумажной
технологии обработки документов. Общепризнанные приемы установ-
ления подлинности физической подписи под документами абсолютно
непригодны при обработке документов в электронной форме. Необхо-
димо было другое решение.
Такое решение впервые было предложено в 1977 году в виде
так называемой системы "электронного подписывания документов"
или, короче, "электронной подписи".
Процедура электронной подписи включает в себя пару алго-
ритмов, один из которых (подписывание) хранится в секрете, а
второй (проверка) выдается всем, кому будут адресоваться под-
писанные документы.
"Подписывание"документа - файла состоит в вычислении с по-
мощью программы "Подпись" по содержимому файла некоторого боль-
шого числа, которое и называется его электронной подписью.
Программа проверки по содержимому документа-файла и его
числу-подписи быстро и надежно удостоверяет, что подпись вы-
числена именно из этого документа-файла и именно данной конкрет-
ной программой подписывания. Принципиальным моментом в электрон-
ной подписи является невозможность ее подделывания без секретной
программы подписывания.
2. АЛГОРИТМЫ ЭЛЕКТРОННОЙ ПОДПИСИ
--------------------------------
Первой и наиболее известной во всем мире системой элект-
ронной подписи стала система RSA, разработанная в 1977 году в
Массачусетском технологическом институте и названная так по пер-
вым буквам фамилий авторов: R.Rivest, A.Shamir, L.Adleman. Алго-
ритмы подписывания и проверки подписи в этой системе устроены
следующим образом.
Подписываемый документ-файл при помощи некоторой процедуры
"сжимается" в целое число M. Такая процедура ("хэш-функция") мо-
жет быть построена многими хорошо известными способами.Например,
путем вычисления "контрольной суммы" этого файла.
"Подписывание" числа М состоит в возведении его в заданную
степень d и вычислении остатка от деления результата возведения
на заданное целое число n, т.е.,:
d
S = М mod n
Подпись документа-файла составляет пара чисел [M,S]. В
секрете должен храниться только показатель степени d.
Для проверки подлинности подписи выдается другой показа-
тель степени e, который используется при проверке соотношения
e ?
S = M mod n
.
Криптографами доказано, что вычислить подпись S для сооб-
щения М может только обладатель числа d, а по числу e определить
d не легче, чем разложить на множители число n. Чтобы разложить
целое число n было практически невозможно, оно должно состоять
не менее чем из 150-170 десятичных знаков.
Фирма "ЛАН-КРИПТО" использует более совершенные методы
электронного подписывания, чем RSA.
Эти методы прошли практическую проверку в коммерческих и
государственных учреждениях США.
С их основными идеями можно познакомиться по статье El
Gamal T., A public-key cryptosysems and signature schеme based
on discret logarithms,IEEE Trans.Inform Theory, v.31 N4, pp.
469-472 (1985).
Оригинальные алгоритмические и программные решения позво-
лили нам сократить время подписывания сообщение в 4 раза по
сравнению с лучшими известными образцами, одновременно повысив
надежность подписи в 1000 раз.
3.ЧТО ТАКОЕ ОТКРЫТОЕ РАСПРЕДЕЛЕНИЕ КЛЮЧЕЙ
-----------------------------------------
В системе используется открытое распределение ключей шиф-
рования. Это устраняет необходимость предварительного снабжения
пользователей секретными ключами.
В основу системы положены работы стенфордских ученых У.Диф-
фи и М.Е.Хеллмана, опубликованные в 1976 г. Ими было предложено
использование односторонней криптографической функции
x
f(x) = a (mod p)
где а, р - целые числа, обладающие рядом свойств. Матема-
тиками доказано, что при известном а, р и значении f(x), нахож-
дение х является трудновыполнимой задачей.
Все операции возведения в степень осуществляются по модулю
X X
р, поэтому в дальнейшем вместо a (mod p) будем писать просто а .
Всем пользователям известны а и р. Рассмотрим двух пользо-
вателей А и В. Пользователь А случайным способом выбирает число
Х и держит его в тайне. Пользователь В - число Y и также держит
его в тайне. Числа Х и Y являются секретными ключами пользовате-
лей А и В. X Y
Затем пользователь А вычисляет а , а пользователь В - а .
X Y
Числа а и а являются открытыми ключами пользователей и могут
X Y
рассылаться по открытым каналам. Злоумышленник, зная а и а не
сможет найти секретные ключи Х и У.
Пользователь А, зная свой секретный ключ Х и открытый ключ
Y YX
пользователя В а , может найти число а . Аналогично В находит
XY
a ,которое можно использовать как секретный ключ в классической
системе шифрования.
.
Пользователь А Пользователь В
ИМММММММММММММММ» ИМММММММММММММММ»
є ЗДї X є є X є
є |X|->a -------------------------------------> a є
є ЮДЫ є є є
є Y є є Y ЗДї є
є a <------------------------------------- a <-|Y| є
є є є ЮДЫ є
є ЗДДДї є є ЗДДДї є
є ЗДї Y | YX| є є ЗДї X | XY| є
є |X|+a ->|a | є є |Y|+a ->|a | є
є ЮДЫ ЮДДДЫ є є ЮДЫ ЮДДДЫ є
ХМММММММММММММММј ХМММММММММММММММј
Система открытого распределения ключей Диффи и Хеллмана
позволяет обойтись без защищенного канала для передачи ключей,
но не устраняет необходимость гарантии того, что А получил от-
крытый ключ именно от В и наоборот. Эта проблема решается с по-
мощью электронной подписи, которой подписываются сообщения об
открытом ключе.
Иногда шифрование с открытым распределением ключей строят
на системе RSA.
Преимущество используемой фирмой "ЛАН Крипто" технологии
по сравнению с методом RSA заключается в том, что формирование
общего секретного ключа происходит в сотни раз быстрее. Генера-
ция новых секретных и открытых ключей в системе RSA основана на
генерации новых простых чисел, а проверка простоты чисел занима-
ет очень много машинного времени. Более того, при использовании
метода RSA у Вас никогда не будет уверенности, что полученные
Вами числа не удовлетворяют ряду свойств, наличие которых приво-
дит к легкому вскрытию Ваших секретных ключей.
Предлагаемая нашей фирмой технология дает возможность шиф-
ровать данные при каждом сеансе связи на новых ключах. Это изба-
вит Вас от необходимости обременять себя хранением секретов на
дискетах или других носителях. Помните, что любое хранение сек-
ретов повышает вероятность попадания их в руки ваших врагов или
конкурентов!
Долгое вырабатывание открытых ключей методом RSA делает
непригодным использование системы RSA для получения новых ключей
при каждом сеансе связи.
Использование RSA приведет Вас к обязательному хранению
секретов на каких-либо носителях. Используя нашу технологию, Вы
быстро и надежно защитите свою связь!
Надежность используемых фирмой "ЛАН-КРИПТО" открытых клю-
чей в 1000 раз превосходит надежность открытых ключей RSA.
Скорость программы шифрования (расшифрования) фирмы
"ЛАН-КРИПТО" 200Кбайт/сек. на АТ-286,их надежность значительно
превосходит стандарт шифрования США DES.
.
4.ТЕХНОЛОГИЯ ПРИМЕНЕНИЯ ШИФРОВАНИЯ С ОТКРЫТЫМИ КЛЮЧАМИ
------------------------------------------------------
И ЭЛЕКТРОННОЙ ПОДПИСИ В БАНКОВСКИХ РАСЧЕТАХ
-------------------------------------------
Система состоит из N+1 точек обслуживания: центра и N або-
нентов. Номера абонентов i = 1, 2,..., N. Абоненты передают друг
другу данные через Центр. В этих данных часть информации Центр
использует для обработки (регистрация, взаимозачеты и т.д.). К
этой части информации Центр должен иметь доступ. Остальная ин-
формация должна быть закрыта для Центра. При передаче данных в
Центр вся информация должна быть подписана и зашифрована.
ПЕРЕДАЧА ДАННЫХ АБОНЕНТ - ЦЕНТР.
I этап. Абонент подписывает документ электронной подписью.
II этап. Центр и Абонент генерируют свои сеансовые (разовые) сек-
ретные ключи Х и У. X
Затем происходит обмен сеансовыми открытыми ключами а и
Y
а . XY
III этап.Абонент шифрует документ на сеансовом общем ключе а и
передает Центру. XY
IV этап. Центр расшифровывает документ на ключе а и проверяет
электронную подпись.
V этап. Все ключи уничтожаются.
Абонент Центр
+====================+ +========================+
II этап. +-+ +-+ I I I
I | |->| | I I I
I +-+ +sign I I I
I I I I
III этап. X I I X II этап.I
I X->a ------------------------> a I
I Y I I Y I
I a <------------------------ a <-Y I
IIII этап. I I III этап.I
I +-----+ I I +-----+ I
I+-+ |+-+ | I I |+-+ | I
I| |----->|| | |------ ---------------->|| | | I
I+sign | |+sign| I I |+sign| I
I | +-----+ I I +-----+ I
I зашифровка XY I I | IV этап.I
I на ключе a I I | - расшифровка XYI
I I I | на ключе a I
I I I | I
I I I | проверка подписиI
I I I +-+ | +-+ I
I I I | |------>| | I
I I I +sign +-+ I
+====================+ +========================+
Аналогично происходит передача документов от Центра к Або-
ненту.
.
ПЕРЕДАЧА ДАННЫХ, ЗАКРЫТЫХ ОТ ЦЕНТРА
Каждый Абонент i генерирует свой секретный ключ x и хранит
Xi
его в секрете. Затем он вычисляет свой открытый ключ а и посыла-
ет его в Центр, подписывая сообщение электронной подписью. Центр
помещает открытые ключи всех абонентов в открытый справочник и,
подписав электронной подписью, рассылает его всем абонентам.
Абонент i Центр
+---+ +---+ +---+-+
Xi | Xi| | Xi| Xi | X1| |
Xi->a ->|a |---------------------------->|a |--->a -->|a |1|
| +-sign +-sign | | X2| |
| | |a |2|
подпись проверка |: |:|
подписи |: |:|
| XN| |
|a |N|
+---+-+
|
подпись----->|
|
+-------+
----------------------|+---+-+|
----------------------|| X1| ||
----------------------||a |1||
----------------------|| X2| ||
----------------------||a |2||
----------------------||: |:||
----------------------||: |:||
----------------------|| XN| ||
----------------------||a |N||
----------------------|+---+-+|
----------------------+--sign-+
|||||||||
рассылается |||||||||
всем абонентам |||||||||
|||||||||
Для закрытия от Центра определенной части данных, предназ-
наченных для Абонента j, Абонент i берет из открытого справочни-
Xj
ка открытый ключ Абонента j а и на основе своего секретного клю-
Xj XiXj
ча Xi и а формирует общий долговременный ключ а . Затем Абонент i
генерирует разовый несекретный ключ К. На разовом ключе К и дол-
XiXj
говременном общем ключе а Абонент i шифрует предназначенные для
Абонента j данные. Несекретный разовый ключ К используется для
того, чтобы каждый сеанс шифрования происходил на новом ключе,
что повышает надежность шифрования. Ключ К посылается Абоненту j
вместе с зашифрованными данными.
Зашифрованные данные, предназначенные для Абонента j, объ-
единяются с открытыми данными, предназначенными для Центра. Пе-
ред отправкой в Центр эти объединенные данные шифруются на разо-
XY
вом общем ключе а (см. раздел "Передача данных Абонент -
Центр"). Таким образом, данные для Абонента j шифруются дважды.
.
Поэтому, если противнику стал известен долговременный секретный
ключ Абонента i, то противник не сможет воспользоваться им, не
зная разовых секретных ключей Х или У, используемых для закрытия
канала Абонент - Центр. Но если ключ Хj попадет в Центр,то Центр
сможет прочитать сообщения для Абонента j. При такой технологии
абоненты хранят только свои долговременные секретные ключи Хi,
но тратится время на формирование общего долговременного ключа
XiXj XiXj
a .Общий ключ а Абонент i может вычислить заранее и хранить
XiX1 XiX2 XiXN
N-1 секретных общих долговременных ключей а , а , ... ,a .
В этом случае не нужно для каждой платежки тратить время на фор-
мирование общего ключа, но необходимо хранить большее количество
секретов.
Для наглядности вышеизложенного рассмотрим пример. Пусть
Абонент i передает через Центр платежку Абоненту j в следующем
виде:
ЗДДДДДДДБДДДБДДДДДДДБДДДБДДДДДДДБДДДБДДДДДДДДДДї
| * * * | i | * * * | s | * * * | j | Клиент j |
ЮДДДДДДДАДДДАДДДДДДДАДДДАДДДДДДДАДДДАДДДДДДДДДДЫ
i - банк, который посылает (Абонент i)
j - банк, которому посылают (Абонент j)
Клиент j - фамилия клиента банка j
S - сумма денег,которую банк i переводит в банк j для клиента
банка j
* - информация для обработки в Центре.
Центр знает, какую сумму S банк i переводит в банк j, но
Центру необязательно знать,фамилию клиента банка j,которому
предназначалась эта сумма. Поле "Клиент j" надо закрыть от Цент-
ра.
ЗДДДДДДДБДДДБДДДДДДДБДДДБДДДДДДДБДДДБДДДДДДДДДДї
| * * * | i | * * * | s | * * * | j | Клиент j |
ЮДДДДДДДАДДДАДДДДДДДАДДДАДДДДДДДАДДДАДДДДДДДДДДЫ
| Абонент i зашифровывает поле
| "Клиент j" на общем долговремен-
| ном ключе а и разовом ключе К
| ЗББББББББББї
ЗДДДДДДДБДДДБДДДДДДДБДДДБДДДДДДДБДДДЕДДДДДДДДДДЕДДДї
| * * * | i | * * * | s | * * * | j | Клиент j | k |
ЮДДДДДДДАДДДАДДДДДДДАДДДАДДДДДДДАДДДЕДДДДДДДДДДЕДДДЫ
| ЮААААААААААЫ
|
| Абонент i подписывает платежку и
| зашифровывает на сеансовом общем
| XY
| ключе а (см.раздел "Передача дан-
| ных Абонент-Центр.")
|
| XY
ЗБББББББББББББББББББББББББ a ББББББББББББББББББББББББББББББББї
Ц ЗББББББББББї Є
Ц ЗДДДДДДДБДДДБДДДДДДДБДДДБДДДДДДДБДДДЕДДДДДДДДДДЕДДДБДДДДДДї Є
Ц | * * * | i | * * * | s | * * * | j | Клиент j | k | sign | Є
Ц ЮДДДДДДДАДДДАДДДДДДДАДДДАДДДДДДДАДДДЕДДДДДДДДДДЕДДДАДДДДДДЫ Є
Ц ЮААААААААААЫ Є
ЮАААААААААААААААААААААААААААААААААААААААААААААААААААААААААААААЫ
| Центр расшифровывает данные на
| XY
| ключе а , проверяет подпись и
| обрабатывает платежку.
|
| ЗББББББББББї
ЗДДДДДДДБДДДБДДДДДДДБДДДБДДДДДДДБДДДЕДДДДДДДДДДЕДДДї
| * * * | i | * * * | s | * * * | j | Клиент j | k |
ЮДДДДДДДАДДДАДДДДДДДАДДДАДДДДДДДАДДДЕДДДДДДДДДДЕДДДЫ
| ЮААААААААААЫ
|
| Абонент i и Центр генерируют ра-
| зовые секретные ключи Z и W, об-
| мениваются разовыми открытыми
| Z W
| ключами а и а . Формируют разо-
| ZW
| вый общий секретный ключ а .
| Центр шифрует платежку на ключе
| ZW
| а , подписывает и передает Або-
| ненту j.
|
ZW
ЗБББББББББББББББББББББББББ a ББББББББББББББББББББББББББББББББї
Ц ЗББББББББББї Є
Ц ЗДДДДДДДБДДДБДДДДДДДБДДДБДДДДДДДБДДДЕДДДДДДДДДДЕДДДБДДДДДДї Є
Ц | * * * | i | * * * | s | * * * | j | Клиент j | k | sign | Є
Ц ЮДДДДДДДАДДДАДДДДДДДАДДДАДДДДДДДАДДДЕДДДДДДДДДДЕДДДАДДДДДДЫ Є
Ц ЮААААААААААЫ Є
ЮАААААААААААААААААААААААААААААААААААААААААААААААААААААААААААААЫ
|
| Абонент j расшифровывает на клю-
| ZW
| че а , проверяет подпись, смот-
| рит в поле i, кто посылал сооб-
| щение, формирует долговременный
| XiXj
| ключ а , берет разовый несек-
| ретный ключ К и расшифровывает
| поле "Клиент j"
|
+---------------------+------------------------+
| * * * | i | * * * | s | * * * | j | Клиент j |
+----------------------------------------------+
Абонент i может не хранить долговременный секретный ключ
Xi,если у него есть возможность в любое время быстро связаться с
Абонентом j. В этом случае абоненты i и j генерируют разовые
секретные ключи, обмениваются разовыми открытыми ключами и фор-
мируют общий сеансовый ключ. Быстрота формирования общего сек-
ретного ключа определяется быстротой передачи данных между або-
нентами i и j.
Программы фирмы "ЛАН Крипто", реализующие описанные техно-
логии, успешно используются в ГВЦ ГУ ЦБ по г.Москве, в 37 круп-
ных коммерческих банках России и Казахстана, в МИД РФ и ФАПСИ.
.
"ЛАН Крипто"
Данные материалы предназначены для пользователей средств
защиты информации фирмы "ЛАН Крипто".
Это не руководство по их практическому применению. Наша
цель - дать возможность пользователю [при желании] самому оцени-
вать степень надежности приобретаемых у нас средств защиты или
подвергнуть их детальной дополнительной экспертизе специалистов,
которым он более всего доверяет.
При этом, как и во всей своей деятельности, мы исходим из
того, что средства защиты информации должны прежде всего давать
возможность пользователю на всех этапах ее хранения, обработки
или передачи оставаться полным и исключительным ее хозяином.
Наши средства защиты гарантируют пользователю , что если он
сохранит в секрете ключи , им самим изготовленные с помощью на-
ших программ , то его " криптографический сейф " не может быть
вскрыт никем, в том числе и самими разработчиками системы защи-
ты.
Мы будем благодарны всем за конструктивные замечания и по-
желания по дальнейшему совершенствованию нашей продукции.
С уважением
А.Лебедев
президент
"ЛАН Крипто"
Содержание
1. АЛГОРИТМЫ ЭЛЕКТРОННОЙ (ЦИФРОВОЙ) ПОДПИСИ............. 4
1.1. Метод RSA....................................... 5
1.2. Метод Эль Гамаля................................ 7
1.3. Цифровая подпись "ЛАН Крипто"................... 9
1.4. Оценка надежности цифровой подписи..............11
2. АЛГОРИТМЫ ШИФРОВАНИЯ................................13
2.1. Алгоритм DES....................................14
2.2. Алгоритм ГОСТ 28147-89.........................15
2.3. Алгоритм шифрования "Веста".....................16
2.4. Оценка стойкости шифрования.....................17
3. АЛГОРИТМЫ ФОРМИРОВАНИЯ КЛЮЧЕЙ........................19
3.1. Метод Диффи - Хеллмана.........................20
3.2. Идентификация абонентов.........................21
3.3. Алгоритм формирования ключей "Афина"............22
3.4. Оценка стойкости................................23
ЗАКЛЮЧЕНИЕ..............................................24
ЛИТЕРАТУРА..............................................25
Приложение А.
Цифровая подпись "ЛАН Крипто"...........................26
Приложение Б.
Алгоритм криптографической защиты данных "ЛАH Крипто"...29
Приложение В.
Протокол формирования общего секретного ключа...........35
Приложение Г.
Генерация больших простых чисел заданного вида..........40
Приложение Д.
Реализация датчиков случайных чисел.....................47
1. АЛГОРИТМЫ ЭЛЕКТРОННОЙ (ЦИФРОВОЙ) ПОДПИСИ.
Впервые идея цифровой подписи была предложена в статье
У.Диффи и М.Хеллмана [ 1 ] в 1976 году. Это был ответ на остро
ощущаемую пользователями телекоммуникационных систем потребность
замены обычных документов на бумаге их электронными аналогами ,
столь же полноценными с юридической точки зрения.
Смысл предложения Диффи и Хеллмана сводился к тому, чтобы
идентификацию автора документа производить не по особенностям
его почерка, как это происходит с обычной физической подписью, а
по наличию у него некоторой индивидуальной информации (ключа
подписывания), сохранение которой в секрете дает возможность га-
рантировать, что никто другой, обрабатывая содержимое электрон-
ного документа, не сможет получить то же число-подпись, что и
законный обладатель ключа.
При этом необходимо было обеспечить возможность абсолютно
надежно убедиться, что вычислил данное число-подпись под данным
блоком информации (файлом, документом, ...) именно обладатель
того ключа, соответствие которому мы проверяем.
Сложность задачи состоит в том, что ключ подписывания не
может быть предъявлен непосредственно при проверке подписи, т.к.
при этом теряется его секретность.
Поэтому, при проверке должен использоваться некий несекрет-
ный " образец цифровой подписи ", который позволял бы надежно
удостовериться, что ее сформировал именно владелец данного сек-
ретного ключа, и именно под этим документом, не позволяя опреде-
лить сам секретный ключ.
Этот "образец цифровой подписи" в специальной литературе
получил в дальнейшем название открытого ключа для проверки под-
писи.
Кроме того , процедура проверки авторства документа и соот-
ветствия его содержания индивидуальному секретному ключу под-
писывания(на основании несекретного "образца цифровой подписи")
должна давать возможность третьей стороне - арбитру совершенно
четко и однозначно принимать решение о подлинности цифровой под-
писи и документа в случае возникновения конфликта.
1.1. Метод RSA.
Первым практическим решением задачи была так называемая
"цифровая подпись RSA", разработанная в 1977 году в Масса-
чусетском Технологическом Институте (США) и получившая свое наз-
вание от первых букв фамилий авторов: R.Rivest, A.Shamir,
L.Adleman [ 4 ].
Их идея состояла в том, что, оперируя с большим целым
числом n, которое является произведением двух различных больших
простых чисел, скажем n = P*Q, можно легко подбирать пары целых
чисел e, d, 1
В математике же с древних времен известно, что разлагать на
множители целые числа из большого числа цифр (скажем, 100 или
200), это очень сложная вычислительная задача. И хотя она в
принципе разрешима за конечное время, но время на ее решение,
даже при использованиии самых мощных суперЭВМ, может оказаться
таким большим, что практически эта задача может считаться нераз-
решимой.
Например, по последним оценкам для разложения целого числа
n из 200 десятичных цифр потребуется не менее 100 лет непрерыв-
ной работы одновременно 100 суперЭВМ типа CRAY, считающихся наи-
более производительными в этом классе задач.
Поэтому авторами RSA решение задачи цифровой подписи было
предложено в следующем виде.
Отправитель сообщений вычисляет два больших простых числа,
100
скажем, P Q 10 , вычисляет их произведение n = P*Q и пару
целых чисел e, d , 1
Числа n и e он передает своим партнерам, а число d держит
в секрете как ключ для подписывания сообщений.
Сообщение М (блок информации, файл, таблица, ...) некоторым
образом сжимается в целое число
m = h(M) , 1
хэш-функцией) и вычисляется цифровая подпись под M с помощью
ключа d в виде
d
s = m mod n,
т.е. целое число m возводится в секретную степень d и делится с
остатком на число n.
Пара [M, s] передается как подписанное сообщение.
Проверка цифровой подписи s под сообщением M производится
сравнением
e ?
s mod n = h(M),
т.е. цифровая подпись s возводится в степень е и остаток от де-
ления этого числа на n сравнивается с результатом хэширования
сообщения М с помощью той же функции h, которая должна быть из-
вестна получателям подписанных сообщений.
Можно строго математически доказать, что результат проверки
цифровой подписи s будет положительным только в том случае, ког-
да при ее формировании был использован секретный ключ d, соот-
ветствующий открытому ключу е ("образцу подписи"). А также дока-
зать, что для восстановления по числам n и e ключа d потребуется
проделать работу не менее, чем для разложения n на множители P и
Q. О сложности последней задачи мы уже говорили.
Рассматривая вопрос о возможности практической реализации
метода RSA в программных разработках фирмы "ЛАН Крипто" мы выде-
лили для себя следующие аргументы против:
- метод RSA защищен патентом США # 4 405 829 и для его ис-
пользования в коммерческих продуктах необходимо(если быть до кон-
ца честным) лицензионное соглашение с держателем патента - фир-
мой "RSA Data Security Inc." (США);
- для обеспечения защиты цифровой подписи от фальсификации
на уровне, скажем, национального стандарта на шифрование инфор-
мации США (алгоритм DES), необходимо использовать при вычислени-
ях целые числа n, e, d не менее, чем из 360 бит (или 108 деся-
тичных знаков) каждое, что требует достаточно больших вычисли-
тельных затрат;
- при вычислении модуля n и ключей e, d необходимо прове-
рять, вообще говоря, бесконечное множество условий (что сделать
практически невозможно), невыполнение каждого из которых может
привести к фальсификации цифровой подписи;
- метод RSA позволяет без знания секретных ключей легко по-
лучать подписи под сообщениями, результат хэширования которых
может быть вычислен как произведение результатов хэширования уже
подписанных сообщений,
например, если
2 = h(М ) и s - подпись под М ,
1 1 1
3 = h(М ) и s - подпись под М , и
2 2 2
6 = h(М ), то s *s - подпись под М ,
3 1 2 3
которую легко получить, даже не зная секретного ключа.
Поэтому, мы в своих программах использовали более надежный
и удобный для реализации на персональных компьютерах метод циф-
ровой подписи.
1.2. Метод Эль Гамаля.
Этот метод цифровой подписи предложил впервые в своей рабо-
те американский ученый T.ElGamal в 1985 г. [ 5 ].
Его идея состояла в том, что для обоснования практической
невозможности фальсификации цифровой подписи может быть исполь-
зована более сложная вычислительная задача, чем разложение на
множители большого целого числа - задача ДИСКРЕТНОГО ЛОГАРИФМИ-
РОВАНИЯ.
В математике известно, что если взять большое простое число
P, (скажем, из 100 или 150 знаков), то по заданным целым числам
g, x, 1
b = g (mod P),
х
т.е. остаток от деления числа g на P, но определить показатель
степени х по b и P (при надлежащем выборе последнего), даже при
известном основании g, практически невозможно, т.к. это примерно
в 1 000 раз сложнее, чем разлагать на множители целые числа по-
рядка P (о сложности этой задачи мы уже говорили выше).
Кроме того, ему удалось избежать явной слабости метода RSA,
связанной с возможностью подделки цифровой подписи под некоторы-
ми сообщениями без определения секретного ключа.
Процедура подписывания электронных документов выглядит сле-
дующим образом.
Отправитель и получатель сообщений используют при вычисле-
154
ниях некоторые большие целые числа g, P,скажем, g P 10 ,
которые не являются секретными.
Отправитель сообщений выбирает случайно любое (!!!) целое
число х, 1
индивидуальный ключ для подписывания, и вычисляет b = g (mod P).
Число b - "открытый ключ для проверки его подписи," он
передает своим партнерам.
Для подписывания сообщение М "хэшируется" в целое число
m = h(M) , 1
генерируется случайное целое число
r, 1 < r < P-1,
вычисляется число u,
r
u = g mod P,
и с помощью секретного ключа х вычисляется число v
v = (m-ux)/r (mod P-1),
которое вместе с u и составляет цифровую подпись (u , v) под
сообщением М.
По получении подписанного сообщения [M, u, v] абонент вы-
числяет m = h(M), а затем с помощью открытого ключа b для про-
верки подлинности подписи обладателя секрета х проверяет соотно-
шение
m ? u v
g mod P = b * u mod P.
Можно строго математически доказать, что последнее ра-
венство будет выполняться тогда и только тогда, когда подпись
(u, v) получена под сообщением М помощью именно того секретного
ключа х, из которого был получен открытый ключ b.
Таким образом удается надежно удостовериться, что отправи-
телем сообщения был обладатель именно данного секретного ключа
х, не раскрывая при этом сам ключ, и что он подписал именно это
конкретное сообщение М.
По сравнению с методом RSA данный метод имеет целый ряд
преимуществ:
- во-первых, при заданном уровне стойкости алгоритма цифро-
вой подписи целые числа, с которыми приходится проводить вы-
числения, имеют запись на 30% короче, что уменьшает сложность
вычислений примерно в 2 раза и позволяет заметно сократить объем
используемой памяти;
- во-вторых, при выборе модуля P достаточно проверить,что
это число простое, и что у числа P-1 есть большой простой мно-
житель;
- в-третьих, процедура подписывания по этому методу не поз-
воляет вычислять как в RSA цифровые подписи под новыми сообщени-
ями без знания секретного ключа.
Эти преимущества метода, а также ряд соображений, связанных
с его патентной "чистотой" и возможностью более свободного
экспорта такой технологии из США послужили главным мотивом для
принятия в 1991 году Национальным институтом стандартов и техно-
логий США проекта национального стандарта цифровой подписи(DSS)
на его основе.
Тем самым, оценки наших специалистов получили весомое
косвенное подтверждение государственных служб США, которые зат-
ратили на анализ и оценку различных методов цифровой подписи за
последние 10 лет довольно значительные средства.
1.3. Цифровая подпись "ЛАН Крипто".
В основу наших разработок были положены исходные идеи мето-
да ЭльГамаля [ 5 ] как наиболее эффективного по соотношению
стойкость/сложность реализации среди всех достаточно изученных
аналитиками алгоритмов цифровой подписи.
Для ускорения процесса подписывания электронных документов
на персональных компьютерах были разработаны специальные алго-
ритмические приемы (являющиеся know-how фирмы "ЛАН Крипто"), ко-
торые позволяют сократить время вычислений на РС-АТ/286 примерно
в 1,5 раза по сравнению с обычными способами вычислений, не тре-
буя при этом дополнительной памяти.
Другие приемы позволяют без потери стойкости цифровой под-
писи по отношению к попыткам фальсификации сократить ее длину до
300 или даже до 200 бит, работая с простыми числами из 500 или
1 000 бит.
Все это дало нам возможность сделать единый пакет программ
"НОТАРИУС," включающий процедуры:
- генерации пользователем своих индивидуальных ключей для
подписывания и проверки подписи,
- регистрации открытых ключей всех пользователей,
- сжатия (хэширования) подписываемых документов,
- вычисления и проверки цифровой подписи
компактным и быстро и надежно работающим.
Здесь мы приведем только скоростные характеристики основных
версий пакета "НОТАРИУС".
Термин "подпись Эль Гамаля" обозначает алгоритм цифровой
подписи в котором используется простое число P такое, что число
P-1 имеет вид 2*Q, где число Q также простое , "стандарт США"
использует простое число P такое, что P-1 имеет простой делитель
160
Q( Q 2 ), случайный показатель x выбирается из интервала
1< x < Q.
Термин "подпись Шнорра" означает , что при хэшировании
сообщения М в него уже включено число u , а результат хэширова-
ния имеет длину записи в половину длины записи числа Q ( эти
приемы предложил впервые R.Shnorr).
Данные для PC/AT-286 , 16MHz , время - в секундах.
Модуль P - из 512 бит.
+----------------------------------------------------------------------------+
| | Подпись ЭльГамаля | Стандарт США | Подпись Шнорра |
| +-----------------------------------------------------------+
| | обычная | сетевая | обычная | сетевая | обычная | сетевая |
+----------------------------------------------------------------------------+
| Подписывание | 1.0101 | 0.9885 | 0.3223 | 0.2975 | 0.2966 | 0.2899 |
+----------------------------------------------------------------------------+
| Проверка | | | | | | |
| подписи | 2.2286 | 2.7520 | 0.8153 | 1.0166 | 0.5065 | 0.7050 |
| абонента | | | | | | |
+----------------------------------------------------------------------------+
| Проверка | нет | | нет | | нет | |
| подписи нового | этой | 4.9641 | этой | 1.6883 | этой | 0.9643 |
| абонента | функции | | функции | | функции | |
+----------------------------------------------------------------------------+
| Регистрация | 2.2973 | нет | 0.7076 | нет | 0.2832 | нет |
| подписи | | функции | | функции | | функции |
+----------------------------------------------------------------------------+
| Размер подписи | 128 | 192 или | 40 | 104 или | 27 | 91 или |
| в байтах | | 128 | | 40 | | 27 |
+----------------------------------------------------------------------------+
| Генерация | | | | | | |
| программы | 0.9013 | 4.5693 | 0.2777 | 2.1599 | 0.2903 | 1.6585 |
| подписи | | | | | | |
+----------------------------------------------------------------------------+
| Генерация | нет | | нет | | нет | |
| программы | этой | 4.0532 | этой | 1.4292 | этой | 1.6388 |
| подписи ценра | функции | | функции | | функции | |
+----------------------------------------------------------------------------+
Термин "сетевая подпись" означает использование протокола с
повышенной ролью центра , но без необходимости хранения пользо-
вателями открытых ключей партнеров.
Кроме того,сетевая подпись позволяет обойтись без предвари-
тельного этапа регистрации всех пользователей системы, сбора их
открытых ключей в каталог и рассылки каталога каждому пользова-
телю. В некоторых случаях это оказывается гораздо удобней.
Формальное описание процедуры цифровой подписи "ЛАН Крипто"
приведено в Приложении А.
1.4. Оценка надежности цифровой подписи.
Стойкость цифровой подписи "ЛАН Крипто" по отношению к по-
пыткам фальсификации без нарушения правильности работы программ
или кражи индивидуального ключа x определяется минимумом из
x
сложности восстановления x по открытому ключу b = g mod P
для проверки подписи, т.е. сложности "дискретного логарифмирова-
ния" числа b по основанию g при модуле P, и сложности фаль-
сификации результатов хэширования сообщения М.
Оценки сложности задачи ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ в за-
висимости от длины двоичной записи простого числа P (при пра-
вильном его выборе) приведены в таблице
+-------------------------------------------------------------------------+
| Длина P | Сложность | Память | Время решения задачи |
| ( в битах) | определения | используемая | на суперкомпьюре |
| | ключа x | алгоритмом | типа CRAY (10**9 оп/c) |
| | | ( в битах) | |
+-------------------------------------------------------------------------+
| | 12 | 6 | |
| 128 | 2*10 | 7*10 | Несколько минут |
| | 16 | 8 | |
| 200 | 10 | 10 | Несколько месяцев |
| | 17 | 9 | |
| 256 | 9*10 | 10 | Несколько десятков лет |
| | 24 | 12 | |
| 512 | 4*10 | 3*10 | ї |
| | 34 | 17 | | |
| 1024 | 10 | 10 | | |
| | 41 | 20 | | Более 100 лет |
| 1500 | 10 | 8*10 | Ц непрерывной |
| | 47 | 24 | | работы |
| 2000 | 7*10 | 10 | | |
| | 50 | 25 | | |
| 2200 | 10 | 10 | Ы |
| | | | |
+-------------------------------------------------------------------------+
Эти оценки получены в результате анализа последних достиже-
ний в области теории сложности вычислительных задач и основы-
ваются не столько на заключениях специалистов "ЛАН Крипто" , но
на всех результатах по данной задаче , опубликованных в научно-
технических журналах и трудах специальных конференций и семина-
ров по вычислительной математике и криптографии за последние 10
лет ( CRYPTO`82-92, EUROCRYPT`84-92, и т.д.).
Таким образом , для "цифрового подписывания" абсолютного
большинства документов вполне достаточным является простое число
P из 200 - 250 двоичных знаков , а для наиболее серьезных доку-
ментов или документов , подлинность цифровой подписи под которы-
ми может проверяться и через 30 - 50 лет, следует, видимо, реко-
мендовать использовать простое число P из 500 бит. Простые числа
Р из 1000 (или даже 1500) бит можно использовать для наиболее
"экзотических" применений в стратегических военных системах
подтверждения подлинности.
Оценки сложности фальсификации результатов хэширования М,
то есть целенаправленного изменения его содержимого при сохране-
нии длины , контрольной суммы и хэш - значения показывают , что
это или вообще невозможно или требует гораздо больше усилий,
чем определение x .
В то же время мы считаем, что реализованная в пакете "НОТА-
РИУС" функция "хэширования" излишне усложнена.
Для следующих версий цифровой подписи мы считаем разумным
использовать более компактные и быстро работающие процедуры хэ-
ширования , одна из которых предложена специалистам через ТК-22
в качестве первого проекта стандарта России для применения при
подписывании сообщений, не имеющих грифа секретности.
2. АЛГОРИТМЫ ШИФРОВАНИЯ.
В отличие от цифровой подписи, которая является от-
носистельно "недавней" (1976 года), теоретической разработкой,
методы защиты информации путем шифрования известны с глубокой
древности.
Правда, в ХХ веке до 70-х годов их использование оставалось
в основном прерогативой государственных служб ( военных, дипло-
матических и т.п.) и было облечено завесой особой секретности.
В секрете держались не только конкретные методы шифрования, но
и сами научные основы их разработки.
Для применения в коммерческих целях предлагались устройства
или отдельные специальные блоки, в которых информация обрабаты-
валась по принципу "черного ящика". Утверждалось, что при подаче
на вход открытой информации на выхо...
