Страница:
<!-- ----------------------------------------------------------
From: Владимир Казеннов (kvn@win.wplus.net)
--------------------------------------------------------------- -->
З А Щ И Т А И Н Ф О Р М А Ц И И
__________________________________
"ЛАН КРИПТО"
ТЕХНОЛОГИЯ
использования цифровой подписи,
открытого распределения ключей и шифрования
в банковских расчетах
Москва 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, считающихся наи-
более производительными в этом классе задач.
From: Владимир Казеннов (kvn@win.wplus.net)
--------------------------------------------------------------- -->
З А Щ И Т А И Н Ф О Р М А Ц И И
__________________________________
"ЛАН КРИПТО"
ТЕХНОЛОГИЯ
использования цифровой подписи,
открытого распределения ключей и шифрования
в банковских расчетах
Москва 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, считающихся наи-
более производительными в этом классе задач.