Страница:
Поэтому авторами 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-х годов их использование оставалось
в основном прерогативой государственных служб ( военных, дипло-
матических и т.п.) и было облечено завесой особой секретности.
В секрете держались не только конкретные методы шифрования, но
и сами научные основы их разработки.
Для применения в коммерческих целях предлагались устройства
или отдельные специальные блоки, в которых информация обрабаты-
валась по принципу "черного ящика". Утверждалось, что при подаче
на вход открытой информации на выходе будет надежно зашифрован-
ная информация, а как это делается пользователь знать не должен,
- это дело специалистов особых государственных организаций.
Однако, такой подход совсем не устраивал коммерческие
структуры, которые желали надежно защищать свою конфиденциальную
информацию, в том числе, и от государственных служб.
Острая потребность биржевых и банковских структур в надеж-
ной и удобной системе обеспечения конфиденциальности информации
при обмене ею по сетям телекоммуникаций привела к тому, что в
1973 году в США был впервые принят открытый национальный стан-
дарт на шифрование и данных (DES).
С тех пор он получил очень широкое распространение во всем
мире, как надежный метод криптографической защиты информации.
"Движение идеи в массы" началось, и в 1989 году в СССР был
также принят стандарт на шифрование данных в компьютерных сетях,
который получил обозначение ГОСТ 28147-89.
Правда, до распада СССР он оставался "полуоткрытым", т.к.
имел гриф "для служебного пользования". Его гораздо меньшая из-
вестность связана , впрочем, не столько с этим грифом, сколько
с отсутствием в СССР компьютерных сетей как таковых.
В том же 1989 году в Японии принимаются два варианта стан-
дарта на шифрование данных FEAL-4 и FEAL-8.
В европейских странах работы по созданию такого рода стан-
дартов в это время только начинают разворачиваться.
2.1. Алгоритм DES.
Алгоритм шифрования данных DES предполагает их обработку
блоками по 64 бита. Каждый блок зашифровывается отдельно. В раз-
личных режимах шифрование последовательно идущих блоков информа-
ции может быть независимым или учитывать результаты обработки
предыдущих блоков.
Мы не будем приводить здесь подробного описания алгоритма
DES, т.к. с ним можно познакомится в большом количестве книг по
криптографии (см., например, [ 7 ] ) или по официальному изданию
Национального бюро стандартов США [ 2,3 ].
В целом, алгоритм DES прошел с 1973 года достаточно серьез-
ную проверку со стороны прфессионалов и огромного числа любите-
лей и показал себя весьма надежным методом шифрования. Несмотря
на то, что в первоначальном варианте в алгоритме DES использу-
ется ключ всего из 56 бит, до настоящего времени не известно ни
одного случая его "вскрытия".
В комплекте программ шифрования "ЛАН Крипто" есть програм-
ма, реализующая шифрование по алгоритму DES.
Однако, DES при всех его достоинствах имеет два существен-
ных недостатка:
- он слишком громоздок для реализации в виде программы на
персональном компьютере (ни одна из известных нам программ реа-
лизаций алгоритма DES не позволяет добиваться на PC-AT/286 ско-
рости обработки информации более 50 Кбайт/сек.);
- при шифровании по алгоритму DES происходит заметное
"размножение ошибки" (искажение в канале связи одного бита ин-
формации, при расшифровании приводит к искажению как минимум
блока из 64 бит), что при недостаточном качестве канала связи
практически лишает возможности обмена информацией в зашифрован-
ном виде).
2.2. Алгоритм ГОСТ 28147-89.
Алгоритм шифрования данных в сетях ЭВМ (ГОСТ 28147-89) был
разработан в СССР в 1989 году. Его разработчики явно находились
под влиянием идей, заложенных в основу национального стандарта
США на шифрование данных (DES). Алгоритм ГОСТ 28147-89 также
предусматривает обработку информации блоками по 64 бита. Каждый
из этих блоков зашифровывается путем многократного повторения
элементарного цикла преобразования информации как заполнения ре-
гистра сдвига длины 2, каждая ячейка которого состоит из 32 бит.
Обратная связь регистра определяется на каждом цикле своей
частью ключа шифрования. Все эти приемы в точности повторяют
схему построения алгоритма DES и наследуют тем самым все его не-
достатки.
Точного описания алгоритма ГОСТ 28147-89 нельзя получить
даже из офицального текста стандарта, т.к. не для всех парамет-
ров указаны конкретные значения. Поэтому у разработчиков с одной
стороны есть определенная свобода при программной или аппаратной
реализации алгоритма шифрования, но с другой стороны нет никакой
гарантии, что реализованный алгоритм действительно обеспечивает
шифровние, т.к. в криптографических преобразованиях даже неболь-
шие на первый взгляд изменения могут привести к полному краху
всего алгоритма.
Кроме того, свобода в выборе параметров ведет к несовмести-
мости различных вариантов конкретных реализаций алгоритмов шиф-
рования, выполненных в соответствии со стандартом, что означает
наличие не одного стандарта, а целого семейства.
Впрочем, специалисты "ЛАН Крипто" на основе своего анализа
выбрали надлежащим образом параметры алгоритма, реализовали
программным способом алгоритм шифрования ГОСТ 28147-89 на
РС-АТ/286 и убедились, что он позволяет достичь несколько боль-
шей скорости шифрования при одновременным сокращении объема
используемой памяти по сравнению с аналогичной реализацией алго-
ритма DES, но эти улучшения не носят принципиального характера.
Поэтому мы продолжали работы по созданию собственного алго-
ритма шифрования информации, который не уступал бы по стойкости
упомянутым выше стандартам, но был бы более приспособлен для
программной реализации на персональных компьютерах.
2.3. Алгоритм шифрования "Веста".
В основу алгоритма шифрования информации, разработанного
специалистами "ЛАН Крипто" положены как идеи, использованные при
создании алгоритма DES, так и заложенные в стандарт ГОСТ
28147-89.
Но в отличие от обоих этих алгоритмов, мы для удобства реа-
лизации шифрования на персональных компьютерах используем обра-
ботку информации блоками по 2 байта в ходе генерации псевдослу-
чайной последовательности из исходного ключа, а собственно за-
шифрование/расшифрование информации осуществляется путем побито-
вого ее сложения по модулю 2 с этой последовательностью.
Такой принцип шифрования обладает целым рядом существенных
преимуществ:
- он не размножает ошибку (искажение в канале любого бита
информации приводит к неправильному расшифрованию только этого
бита: можно использовать практически любой канал);
- процедуры зашифрования и расшифрования одинаковы и пре-
дельно просты ( что позволяет реализовать их компактно и достичь
большой скорости обработки информации: скоростные версии прог-
раммы "Веста" позволяют шифровать/расшифровывать информацию на
PC/AT-286 со скоростью ее считывания с диска - 200-220
Кбайт/сек);
- он наименее чувствителен к дополнительным свойствам
исходного ключа: кроме случайности и равновероятности ничего не
требуется.
В то же время у этого принципа есть один( крайне существен-
ный для традиционных систем обмена шифрованной информацией) не-
достаток: при зашифровании каждого нового сообщения должен быть
использован новый исходный ключ.
О том, почему этот недостаток становится несущественным в
технологии защиты информации "ЛАН Крипто" будет сказано подроб-
ней в разделе 3.
Формальное описание процедур зашифрования/расшифрования ал-
горитма "Веста" приведено в Приложении В.
2.4. Оценка стойкости шифрования.
Стойкость алгоритмов шифрования, т.е. их надежность по от-
ношению к попыткам получить открытую информацию из шифрованной
без знания ключа шифрования ("взломать шифр") определяется до
настоящего времени во всем мире и по отношению ко всем алгорит-
мам шифрования единственным способом - методом экспертных оце-
нок.
Поэтому сам факт, что стандарт США (DES) был открыто опуб-
ликован 20 лет назад и с тех пор доступен для анализа любому
эксперту говорит очень сильно в пользу обоснованности оценок его
18
стойкости на уровне 10 , которые до настоящего времени так и не
были поколеблены.
Практически это означает, что для дешифрования алгоритма
DES с помощью суперЭВМ типа CRAY, которая выполняет в
9
секунду до миллиарда (10 ) операций, потребуется около 30 лет
7
непрерывной работы (в году - около 3*10 секунд).
Гипотетически рассуждая о возможности создания специализи-
рованной суперЭВМ, обладающей возможностью выполнять в секунду в
12
тысячу раз больше операций, чем CRAY, т.е. до 10 оп./сек.,
можно предположить, что время "взламывания" алгоритма DES может
быть сокращено до нескольких недель. Однако все такого рода
рассуждения, начиная с 1973 года и по настоящее время остаются
всего лишь абстрактно-гипотетическими, хотя они и привели в
последних версиях алгоритма DES к увеличению длины ключа.
Стандарт СССР на шифрование данных в сетях ЭВМ (ГОСТ
28147-89) был разработан в 1989 году и до его появления в
предложено в следующем виде.
Отправитель сообщений вычисляет два больших простых числа,
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-х годов их использование оставалось
в основном прерогативой государственных служб ( военных, дипло-
матических и т.п.) и было облечено завесой особой секретности.
В секрете держались не только конкретные методы шифрования, но
и сами научные основы их разработки.
Для применения в коммерческих целях предлагались устройства
или отдельные специальные блоки, в которых информация обрабаты-
валась по принципу "черного ящика". Утверждалось, что при подаче
на вход открытой информации на выходе будет надежно зашифрован-
ная информация, а как это делается пользователь знать не должен,
- это дело специалистов особых государственных организаций.
Однако, такой подход совсем не устраивал коммерческие
структуры, которые желали надежно защищать свою конфиденциальную
информацию, в том числе, и от государственных служб.
Острая потребность биржевых и банковских структур в надеж-
ной и удобной системе обеспечения конфиденциальности информации
при обмене ею по сетям телекоммуникаций привела к тому, что в
1973 году в США был впервые принят открытый национальный стан-
дарт на шифрование и данных (DES).
С тех пор он получил очень широкое распространение во всем
мире, как надежный метод криптографической защиты информации.
"Движение идеи в массы" началось, и в 1989 году в СССР был
также принят стандарт на шифрование данных в компьютерных сетях,
который получил обозначение ГОСТ 28147-89.
Правда, до распада СССР он оставался "полуоткрытым", т.к.
имел гриф "для служебного пользования". Его гораздо меньшая из-
вестность связана , впрочем, не столько с этим грифом, сколько
с отсутствием в СССР компьютерных сетей как таковых.
В том же 1989 году в Японии принимаются два варианта стан-
дарта на шифрование данных FEAL-4 и FEAL-8.
В европейских странах работы по созданию такого рода стан-
дартов в это время только начинают разворачиваться.
2.1. Алгоритм DES.
Алгоритм шифрования данных DES предполагает их обработку
блоками по 64 бита. Каждый блок зашифровывается отдельно. В раз-
личных режимах шифрование последовательно идущих блоков информа-
ции может быть независимым или учитывать результаты обработки
предыдущих блоков.
Мы не будем приводить здесь подробного описания алгоритма
DES, т.к. с ним можно познакомится в большом количестве книг по
криптографии (см., например, [ 7 ] ) или по официальному изданию
Национального бюро стандартов США [ 2,3 ].
В целом, алгоритм DES прошел с 1973 года достаточно серьез-
ную проверку со стороны прфессионалов и огромного числа любите-
лей и показал себя весьма надежным методом шифрования. Несмотря
на то, что в первоначальном варианте в алгоритме DES использу-
ется ключ всего из 56 бит, до настоящего времени не известно ни
одного случая его "вскрытия".
В комплекте программ шифрования "ЛАН Крипто" есть програм-
ма, реализующая шифрование по алгоритму DES.
Однако, DES при всех его достоинствах имеет два существен-
ных недостатка:
- он слишком громоздок для реализации в виде программы на
персональном компьютере (ни одна из известных нам программ реа-
лизаций алгоритма DES не позволяет добиваться на PC-AT/286 ско-
рости обработки информации более 50 Кбайт/сек.);
- при шифровании по алгоритму DES происходит заметное
"размножение ошибки" (искажение в канале связи одного бита ин-
формации, при расшифровании приводит к искажению как минимум
блока из 64 бит), что при недостаточном качестве канала связи
практически лишает возможности обмена информацией в зашифрован-
ном виде).
2.2. Алгоритм ГОСТ 28147-89.
Алгоритм шифрования данных в сетях ЭВМ (ГОСТ 28147-89) был
разработан в СССР в 1989 году. Его разработчики явно находились
под влиянием идей, заложенных в основу национального стандарта
США на шифрование данных (DES). Алгоритм ГОСТ 28147-89 также
предусматривает обработку информации блоками по 64 бита. Каждый
из этих блоков зашифровывается путем многократного повторения
элементарного цикла преобразования информации как заполнения ре-
гистра сдвига длины 2, каждая ячейка которого состоит из 32 бит.
Обратная связь регистра определяется на каждом цикле своей
частью ключа шифрования. Все эти приемы в точности повторяют
схему построения алгоритма DES и наследуют тем самым все его не-
достатки.
Точного описания алгоритма ГОСТ 28147-89 нельзя получить
даже из офицального текста стандарта, т.к. не для всех парамет-
ров указаны конкретные значения. Поэтому у разработчиков с одной
стороны есть определенная свобода при программной или аппаратной
реализации алгоритма шифрования, но с другой стороны нет никакой
гарантии, что реализованный алгоритм действительно обеспечивает
шифровние, т.к. в криптографических преобразованиях даже неболь-
шие на первый взгляд изменения могут привести к полному краху
всего алгоритма.
Кроме того, свобода в выборе параметров ведет к несовмести-
мости различных вариантов конкретных реализаций алгоритмов шиф-
рования, выполненных в соответствии со стандартом, что означает
наличие не одного стандарта, а целого семейства.
Впрочем, специалисты "ЛАН Крипто" на основе своего анализа
выбрали надлежащим образом параметры алгоритма, реализовали
программным способом алгоритм шифрования ГОСТ 28147-89 на
РС-АТ/286 и убедились, что он позволяет достичь несколько боль-
шей скорости шифрования при одновременным сокращении объема
используемой памяти по сравнению с аналогичной реализацией алго-
ритма DES, но эти улучшения не носят принципиального характера.
Поэтому мы продолжали работы по созданию собственного алго-
ритма шифрования информации, который не уступал бы по стойкости
упомянутым выше стандартам, но был бы более приспособлен для
программной реализации на персональных компьютерах.
2.3. Алгоритм шифрования "Веста".
В основу алгоритма шифрования информации, разработанного
специалистами "ЛАН Крипто" положены как идеи, использованные при
создании алгоритма DES, так и заложенные в стандарт ГОСТ
28147-89.
Но в отличие от обоих этих алгоритмов, мы для удобства реа-
лизации шифрования на персональных компьютерах используем обра-
ботку информации блоками по 2 байта в ходе генерации псевдослу-
чайной последовательности из исходного ключа, а собственно за-
шифрование/расшифрование информации осуществляется путем побито-
вого ее сложения по модулю 2 с этой последовательностью.
Такой принцип шифрования обладает целым рядом существенных
преимуществ:
- он не размножает ошибку (искажение в канале любого бита
информации приводит к неправильному расшифрованию только этого
бита: можно использовать практически любой канал);
- процедуры зашифрования и расшифрования одинаковы и пре-
дельно просты ( что позволяет реализовать их компактно и достичь
большой скорости обработки информации: скоростные версии прог-
раммы "Веста" позволяют шифровать/расшифровывать информацию на
PC/AT-286 со скоростью ее считывания с диска - 200-220
Кбайт/сек);
- он наименее чувствителен к дополнительным свойствам
исходного ключа: кроме случайности и равновероятности ничего не
требуется.
В то же время у этого принципа есть один( крайне существен-
ный для традиционных систем обмена шифрованной информацией) не-
достаток: при зашифровании каждого нового сообщения должен быть
использован новый исходный ключ.
О том, почему этот недостаток становится несущественным в
технологии защиты информации "ЛАН Крипто" будет сказано подроб-
ней в разделе 3.
Формальное описание процедур зашифрования/расшифрования ал-
горитма "Веста" приведено в Приложении В.
2.4. Оценка стойкости шифрования.
Стойкость алгоритмов шифрования, т.е. их надежность по от-
ношению к попыткам получить открытую информацию из шифрованной
без знания ключа шифрования ("взломать шифр") определяется до
настоящего времени во всем мире и по отношению ко всем алгорит-
мам шифрования единственным способом - методом экспертных оце-
нок.
Поэтому сам факт, что стандарт США (DES) был открыто опуб-
ликован 20 лет назад и с тех пор доступен для анализа любому
эксперту говорит очень сильно в пользу обоснованности оценок его
18
стойкости на уровне 10 , которые до настоящего времени так и не
были поколеблены.
Практически это означает, что для дешифрования алгоритма
DES с помощью суперЭВМ типа CRAY, которая выполняет в
9
секунду до миллиарда (10 ) операций, потребуется около 30 лет
7
непрерывной работы (в году - около 3*10 секунд).
Гипотетически рассуждая о возможности создания специализи-
рованной суперЭВМ, обладающей возможностью выполнять в секунду в
12
тысячу раз больше операций, чем CRAY, т.е. до 10 оп./сек.,
можно предположить, что время "взламывания" алгоритма DES может
быть сокращено до нескольких недель. Однако все такого рода
рассуждения, начиная с 1973 года и по настоящее время остаются
всего лишь абстрактно-гипотетическими, хотя они и привели в
последних версиях алгоритма DES к увеличению длины ключа.
Стандарт СССР на шифрование данных в сетях ЭВМ (ГОСТ
28147-89) был разработан в 1989 году и до его появления в