Криптографические протоколы

шаге 3 Антон не в состоянии отличить произвольную битовую последовательность от подлинного ключа DES-алгоритма, сгенерированного Борисом. Протокол также обеспечивает защиту от атаки со стороны Бориса, так как у того нет тайных ключей Антона, чтобы определить битовую последовательность, использованную Антоном в качестве ключа DES-алгоритма для шифрования второго сообщения.

Конечно, протокол неосознанной передачи информации отнюдь не гарантирует, что Антон не пошлет Борису какие-нибудь бессмысленные послания (типа "Борис - лох" или "Мяу-мяу") вместо битов одного из семи простых множителей, на которые раскладывается исходное 700-битовое число. Или что Борис вообще захочет с ними ознакомиться и примет участие в выполнении шагов этого протокола.

На практике протокол неосознанной передачи информации используется довольно редко. Обычно он служит в качестве одного из строительных блоков для построения других протоколов.

Анонимные совместные вычисления

Иногда бывает так, что группе людей требуется совместно вычислить некоторую функцию от многих переменных. Каждый участник вычислительного процесса является источником значений одной или нескольких переменных этой функции. Результат вычислений становится известен всем членам группы, однако ни один из них не в состоянии выяснить что-либо о значениях, поданных на вход функции другим членом группы.

Вычисление средней зарплаты

Допустим, что начальник отдела приказал своим подчиненным подсчитать среднюю зарплату в отделе. Начальник осведомлен о зарплате любого сотрудника, но слишком занят более важными делами, чтобы отвлекаться на подобные пустяки. Каждый сотрудник прекрасно знает собственную зарплату, но категорически не желает сообщать о ней сослуживцам. Чтобы сотрудники отдела могли просуммировать свои оклады, сохранив их в тайне от других, им следует воспользоваться следующим протоколом:

1. Антон генерирует случайное число, прибавляет его к своей зарплате, шифрует полученную сумму при помощи открытого ключа Бориса и затем передает то, что у него получилось, Борису.

2. На своем тайном ключе Борис расшифровывает результат, вычисленный Антоном, прибавляет к нему свою зарплату, шифрует полученную сумму при помощи открытого ключа Владимира и затем передает то, что у него получилось, Владимиру.

3. На своем тайном ключе Владимир расшифровывает результат, вычисленный Борисом, прибавляет к нему свою зарплату, шифрует полученную сумму при помощи открытого ключа Георгия и затем передает то, что у него получилось, Георгию.

4. На своем тайном ключе Георгий расшифровывает результат, вычисленный Владимиром, прибавляет к нему свою зарплату, шифрует полученную сумму при помощи открытого ключа Антона и затем передает то, что у него получилось, Антону.

5. На своем тайном ключе Антон расшифровывает результат, вычисленный Георгием, вычитает из него случайное число, сгенерированное на шаге 1, делит на количество сотрудников отдела и получает искомую среднюю зарплату в отделе.

Точность вычисления средней зарплаты зависит от честности каждого сотрудника. Если хотя бы один из участников протокола соврет относительно своего жалованья, итоговое значение будет неверным. Особенно большими потенциальными возможностями для злоупотреблений обладает Антон. На шаге 5 он может вычесть любое число, какое только придет ему в голову, и никто не заметит подделки. Поэтому необходимо обязать Антона воспользоваться какой-либо из схем предсказания бита. Однако если от Антона потребуется раскрыть перед всеми случайное число, сгенерированное им на шаге 1, зарплату Антона узнает Борис. Это значит, что начальнику отдела все же придется отвлечься и выполнить вычисления, предусмотренные шагом 2 протокола, самому. Ведь он и так в курсе размера оплаты труда Антона.

Как найти себе подобного

Антон любит играть с резиновыми куклами, изготовители которых потрудились на славу, тщательно скопировав в натуральную величину определенные особенности анатомического строения женщины. А Борису нравится во всех красочных подробностях наблюдать за жизнью соседей из многоквартирного дома напротив при помощи современных оптических приспособлений. Оба тщательно скрывают свои пристрастия от родственников, друзей и коллег по работе, но очень хотели бы найти людей, которые разделяют их интересы.

Фирма "Совместные анонимные вычисления" готова оказать необходимую помощь Антону, Борису и им подобным в подборе таких же чудаков, как они сами. Сотрудники фирмы составили всеобъемлющий список всех человеческих чудачеств, каждое из которых снабжено уникальным идентификатором из семи цифр. Обратившись в фирму, Антон и Борис принимают участие в выполнении шагов некоторого протокола, после чего узнают, испытывают ли они склонность к одним и тем же чудачествам. При положительном ответе они смогут связаться друг с другом и слиться во взаимном экстазе. Если ответ будет отрицательным, об их необычных пристрастиях не узнает никто, включая сотрудников фирмы.

Протокол выглядит так:

1. Используя однонаправленную функцию, Антон преобразует 7-значный идентификатор своего чудачества в другое 7-значное число.

2. Трактуя полученное на шаге 1 число как телефонный номер, Борис набирает этот номер и оставляет его абоненту свои координаты. Если на вызов никто не отвечает или такого телефонного номера не существует, Антон применяет к нему однонаправленную функцию и получает новое семизначное число. Так продолжается до тех пор, пока кто-нибудь не ответит на телефонный звонок Антона.

3. Антон сообщает в фирму, сколько раз Борис должен применять однонаправленную функцию, чтобы получить искомый телефонный номер.

4. С помощью однонаправленной функции Борис преобразует 7-значный идентификатор своего чудачества столько раз, сколько это делал Антон, и получает 7-значное число, которое трактует как телефонный номер. Борис звонит по полученному им номеру и спрашивает, нет ли для него какой-либо информации.

Следует отметить, что Борис может предпринять атаку с выбранным открытым текстом. Узнав идентификаторы распространенных человеческих чудачеств, Борис будет по очереди перебирать их, применять к ним однонаправленную функцию и звонить по получающимся у него телефонным номерам. Поэтому необходимо сделать так, чтобы количество возможных чудачеств было достаточно велико и подобного рода атака стала в результате неосуществимой.

Депонирование ключей

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

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

В самом общем случае Стандарт шифрования данных с депонированием ключа реализуется с помощью следующего криптографического протокола:

1. Антон генерирует пару ключей, состоящую из открытого и тайного ключа, и делит их на n частей.

2. Антон посылает каждую часть тайного ключа и соответствующую ей часть открытого ключа отдельному доверенному лицу.

3. Каждое доверенное лицо проверяет полученные от Антона части открытого и тайного ключа и помещает их на хранение в надежное место.

4. Если правоохранительные органы добиваются разрешения ознакомиться с перепиской Антона, они обращаются к его доверенным лицам и реконструируют соответствующий тайный ключ.

Существуют различные варианты протокола шифрования данных с депонированием ключа. Например, в него можно встроить пороговую схему с тем, чтобы для восстановления тайного ключа нужно было собрать не все n, а лишь не менее m (m

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

В настоящее время любой специалист в области технологий банковских расчетов хорошо знает о такой возможности авторизации электронных документов и банковских транзакций как цифровые подписи. Многие банки широко используют цифровую подпись при межбанковских и внутрибанковских расчетах, а также при работе с клиентами. Однако, наш пятилетний практический опыт работы с очень большим числом банков России, других стран СНГ и некоторыми банками стран "дальнего зарубежья" показал, что далеко не все вопросы технологии оформления и использования официально юридически значимых электронных документов с цифровыми подписями достаточно ясны даже специалистам по автоматизации банковских расчетов. Поэтому, я попытаюсь в данной публикации дать вразумительные ответы хотя бы на небольшую часть вопросов, наиболее часто задаваемых банковскими специалистами, в ходе практической реализации технологии цифровой подписи.

1. ПРИНЦИПЫ.

Идея цифровой подписи, как законного средства подтверждения подлинности и авторства документа в электронной форме, впервые была сформулирована явно в 1976 году в статье двух молодых американских специалистов по вычислительным наукам из Стэндфордского университета Уитфилда Диффи и Мартина Хеллмана.

Суть ее состоит в том, что для гарантированного подтверждения подлинности информации, содержащейся в электронном документе, а также для возможности неопровержимо доказать третьей стороне (партнеру, арбитру, суду и т.п.), что электронный документ был составлен именно конкретным лицом, или по его поручению, и именно в том виде, в которм он предъявлен, автору документа предлагается выбрать свое индивидуальное число ( называемое обычно индивидуальным ключом, паролем, кодом, и т.д.) и каждый раз для "цифрового подписывания" сворачивать (замешивать) этот свой индивидуальный ключ, хранимый в секрете от всех, с содержимым конкретного электронного документа. Результат такого "сворачивания" - другое число, и может быть назван цифровой подписью данного автора под данным конкретным документом.

Для практического воплощения этой идеи требовалось найти конкретные и конструктивные ответы на следующие вопросы:

Как "замешивать" содержание документа с индивидуальным ключом пользователя, чтобы они стали неразделимы ?

Как проверять, что содержание подписываемого документа и индивидуальный ключ пользователя были подлинными, не зная заранее ни того, ни другого ?

Как обеспечить возможность многократного использования автором одного и того же индивидуального ключа для цифрового подписывания большого числа электронных документов ?

Как гарантировать невозможность восстановления индивидуального ключа пользователя по любому количеству подписанных с его помощью электронных документов ?

Как гарантировать, что положительным результат проверки подлинности цифровой подписи и содержимого электронного документа будет в том и только в том случае, когда подписывался именно данный документ и именно с помощью данного индивидуального ключа ?

Как обеспечить юридическую полноправность электронного документа с цифровыми подписями, существующего только в электронном виде без бумажного дубликата или заменителей ?

Для полноценных удовлетворительных ответов на все эти вопросы потребовалось около 20 лет. Сейчас мы можем точно и определенно сказать, что практические ответы на все эти вопросы получены. Мы располагаем полноценным арсеналом технических средств авторизации электронных документов, называемым цифровой подписью.

Рассмотрим эти ответы подробнее. Основная идея Диффи и Хеллмана состояла в том, чтобы искать ответы на первые четыре из списка вопросов (математические) по следующей схеме:

пользователи располагают средствами выбирать случайно свои индивидуальные ключи для подписывания из очень большого множества всех возможных ключей,

по каждому конкретно выбранному индивидуальному ключу для подписывания легко вычислить парный к нему ключ для проверки подписей,

процедура вычисления ключа проверки из ключа подписывания широко известна, практически реализуема и гарантирует невозможность восстановления ключа подписывания,

процедуры подписывания и проверки подписи широко известны, в каждой из них используется только один из пары ключей, и гарантируется невозможность получения неверного ответа, а также невозможность восстановления ключа подписывания по ключу проверки.

Самым сложным из этих условий является, конечно же, гарантирование невозможности восстановления ключа подписывания по ключу проверки и любому количеству подписанных электронных документов.

Лучший из предложенных на сегодня учеными способов его выполнения состоит в том, чтобы использовать такие процедуры подписывания и проверки, что практическое восстановление ключей подписи по ключам проверки требует решения известной сложной вычислительной задачи. Поскольку задача является общеизвестно сложной, то если ее не научились решать за обозримое время все математики мира во все предыдущие столетия, то есть некоторая надежда, что ее не сумеют решить быстро и в ближайшем будущем.

Практический результат последующих 20 лет научных поисков таких задач оказался до некоторой степени парадоксальным: при всем многообразии известных сложных вычислительных задач, практически применимой оказалась одна. Это так называемая задача дискретного логарифмирования.

В простейшем варианте ее можно сформулировать так. Если заданы три больших целых положительных числа

a, n, x,

то располагая даже несложными арифметическими устройствами типа карманного калькулятора, или просто карандашом и бумагой, можно довольно быстро вычислить число

a**x

как результат умножения числа

a

на себя

x

раз,

а затем и остаток от деления этого числа нацело на n, записываемый как

b = a**x mod n

задача же дискретного логарифмирования состоит в том, чтобы по заданным числам

a, b, n

связанным таким соотношением, найти то число

x

из которого по этой формуле было вычислено число b.

Оказывается, что задача дискретного логарифмирования при правильном выборе целых чисел настолько сложна, что позволяет надеяться на практическую невозможность восстановления числа x, - индивидуального ключа подписывания, по числу b, применяемому в качестве ключа проверки.

Чтобы говорить более определенно о практической невозможности решить ту или иную вычислительную задачу, следует предварительно договориться о том, какие вычислительные мощности и мозговые ресурсы доступны тому, кто предположительно будет эту задачу решать. Поскольку давать конкретные оценки возможностей потенциальных мозговых ресурсов будущего "взломщика" системы цифровой подписи дело весьма сложное и неблагодарное, мы будем просто исходить из предположения, что он располагает полной информацией о наилучших известных мировой науке методах решения данной задачи.

Далее, если он располагает вычислительной системой общей мощностью, скажем, 1 миллиард (10**9 = 1 000 000 000) операций в секунду, а это мощность современного суперкомпьютера типа CRAY-3, то

- за сутки непрерывной работы такой системы может быть решена задача сложностью около 100 000 миллиардов (или 10**14) операций

- за месяц - около 3*(10**15),

- за год - около 3*(10**16),

- за 10 лет - около 3*(10**17),

- за 30 лет - около 10**18 операций.

Таким образом, даже если допустить, что потенциальный взломщик цифровой подписи располагает вычислительной системой эквивалентной по мощности 1000 суперкомпьютерам типа CRAY-3, то на выполнение вычислений объемом 10**21 операций ему потребовалось бы не менее 30 лет непрерывной работы всей системы, что с практической точки зрения означает невозможность их выполнения.

Поэтому, цифровая подпись с надежностью не менее 10**21 может считаться практически неподделываемой.

В этом месте автору обычно задают вопрос: "А что, если где-то в недрах специальных служб известны более совершенные методы решения этой задачи, которые могут быть применены для фальсификации цифровых подписей?"

В настоящее время ответ на него оказывается довольно простым. Если вы боитесь, что обычно предлагаемого при длине ключей в 64 байта запаса надежности в 10**18 - 10**21 недостаточно, применяйте алгоритмы с более длинными ключами. Современные цифровые процессоры Intel486 и Pentium позволяют за доли секунды вычислять и проверять цифровые подписи с ключами до 512 байт, а стойкость большинства широко применяемых методов цифровой подписи при такой длине ключей заведомо превосходит все разумные требования ( более чем 10**50).

Итак, как видим, современные принципы построения системы цифровой подписи, общепризнанные в мире, просты и изящны:

методы вычисления и проверки цифровых подписей всех пользователей системы одинаковы, всем известны и основываются на широко известных математических задачах,

методы вычисления ключей проверки цифровых подписей из индивидуальных ключей подписывания одинаковы для всех и хорошо известны, их надежность также основывается на широко известных математических задачах,

индивидуальные ключи подписывания выбираются самими пользователями по случайному закону из большого множества всех возможных ключей,

при конкретном алгоритме цифровой подписи его стойкость может быть оценена без привлечения какой-либо "закрытой" информации на основе только известных математических результатов и разумных допущений о вычислительных мощностях потенциального "взломщика", посколку она базируется на общедоступных теоретических результатах по оценке сложности широко известных сложных вычислительных задач.

2. АЛГОРИТМЫ.

Проведем теперь сопоставление некоторых конкретных алгоритмов цифровой подписи с целью выявления их преимуществ и недостатков в различных ситуациях.

Для удобства оценки основных свойств того или иного алгоритма мы будем сравнивать его основные характеристики:

длину ключей,

длину цифровой подписи,

сложность (время) вычисления и

сложность (время) проверки подлинности цифровой подписи

при условии, что уровень стойкости подписи по отношению к любым методам фальсификации не ниже, чем 10**21 (или 30 лет непрерывной работы сети из 1000 суперкомпьютеров).

В качестве "базовой" длины ключей и длины самой цифровой подписи мы будем рассматривать длину в 64 байта.

RSA. Первым по времени изобретения конкретным алгоритмом цифровой подписи был разработанный в 1977 году в Массачусетском технологическом институте алгоритм RSA.

Алгоритм RSA основывается на том математическом факте, что задача дискретного логарифмирования при выборе целого параметра n в виде произведения двух различных простых чисел примерно равных по порядку величины, т.е.

n = p*q

становится не менее сложной, чем разложение n на эти простые множители, а последняя задача давно (еще со времен Архимеда и Евклида) известна в математике как сложная.

По современным оценкам сложность задачи разложения на простые множители при целых числах n из 64 байт составляет порядка 10**17 - 10**18 операций, т. е. находится где-то на грани досягаемости для серьезного "взломщика". Поэтому обычно в системах цифровой подписи на основе алгоритма RSA применяют более длинные целые числа n (обычно от 75 до 128 байт).

Это соответственно приводит к увеличению длины самой цифровой подписи относительно 64-байтного варианта примерно на 20% -100% (в данном случае ее длина совпадает с длиной записи числа n), а также от 70% до 800% увеличивает время вычислений при подписывании и проверке.

Кроме того, при генерации и вычислении ключей в системе RSA необходимо проверять большое количество довольно сложных дополнительных условий на простые числа p и q (что сделать достаточно трудно и чего обычно не делают, пренебрегая вероятностью неблагоприятного исхода - возможной подделки цифровых подписей)., а невыполнение любого из них может сделать возможным фальсификацию подписи со стороны того, кто обнаружит невыполнение хотя бы одного из этих условий (при подписывании важных документов допускать, даже теоретически, такую возможность нежелательно).

В дополнение ко всем этим алгоритмическим слабостям метода RSA следует также иметь в виду, что он защищен патентом США и поэтому любое его использование на территории США или западноевропейских стран требует приобретения соответствующей лицензии на использование, стоимость которой на 100 пользователей составляет $5000.

EGSA. Существенным шагом вперед в разработке современных алгоритмов цифровой подписи был новый алгоритм Т. ЭльГамаля, предложенный им в 1984 году. В этом алгоритме целое число n полагается равным специально выбранному большому простому числу p, по модулю которого и производятся все вычисления. Такой выбор позволяет повысить стойкость подписи при ключах из 64 байт примерно в 1000 раз, т.е. при такой длине ключей обеспечивается необходимый нам уровень стойкости порядка 10**21. Правда, при этом длина самой цифровой подписи увеличивается в два раза и составляет 128 байт.

Главная "заслуга" алгоритма ЭльГамаля состояла в том, что в дальнейшем он послужил основой для принятия нескольких стандартов цифровой подписи, в том числе национального стандарта США DSS, введенного в действие 1 декабря 1994 года и государственного стандарта РФ ГОСТ Р 34.10, введенного с 1 января 1995 года.

DSA. Национальным институтом стандартов и технологий СЩА в 1991 году на основе алгоритма ЭльГамаля был разработан и представлен на рассмотрение Конгресса США новый алгоритм цифровой подписи, получивший название DSA (сокращение от Digital Signature Algorithm). Алгоритм DSA, ставший в дальнейшем основой национального стандарта США на цифровую подпись имеет по сравнению с алгоритмом RSA целый ряд преимуществ:

во-первых, при заданном уровне стойкости цифровой подписи целые числа, с которыми приходится проводить вычисления, имеют запись как минимум на 20% короче, что соответственно уменьшает сложность вычислений не менее, чем на 70% и позволяет заметно сократить объем используемой памяти;

во-вторых, при выборе параметров достаточно проверить всего три достаточно легко проверяемых условия;

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

Эти преимущества, а также соображения, связанные с возможностью его реализовывать любым разработчиком свободно без коммерческих лицензионных соглашений с держателями патента, компанией RSA Data Security, и возможностью свободного безлицензионного экспорта такой технологии из США послужили главным мотивом для принятия в 1994 году национального стандарта цифровой подписи (DSS) на его основе.

Такое решение отнюдь не было очевидным, поскольку RSA, как наиболее известный алгоритм цифровой подписи и шифрования с открытым ключом, был гораздо шире распространен, практически опробован во многих странах и признан как стандарт de facto большинством разработчиков операционных систем, сетевых технологий и прикладного программного обеспечения. Популярность его объясняется, прежде всего, 8-летним опережением по времени появления, значительно более широкой известностью как самого алгоритма, так и его авторов в научных кругах, а также успешным бизнесом держателя патента - компании RSA Data Security, Inc. (сам автор алгоритма ЭльГамаль был в 1994-1995 гг. ее сотрудником).

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

По сравнению с оригинальным алгоритмом ЭльГамаля метод DSA имеет одно важное преимущество, - при заданном в стандарте уровне стойкости, числа, участвующие в вычислении подписи, имеют длину по 20 байт каждое, сокращая общую длину подписи до 40 байт.

Поскольку большинство операций при вычислении подписи и ее проверке также производится по модулю из 20 байт, сокращается время вычисления подписи и объем используемой памяти.

В алгоритме ЭльГамаля длина подписи при таком уровне стойкости была бы равна 128 байт.

НОТАРИУС. Поскольку в 1991 году наиболее распространенной моделью персонального компьютера в СССР был AT/286(12) то мы в своих ранних алгоритмических разработках должны были максимально упростить лучшие из известных тогда алгоритмов цифровой подписи, чтобы их программная реализация на таком процессоре позволяла вычислять и проверять подпись под электронными документами за разумное время, скажем, 1-2 секунды при размере документа до 10 KB.

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

Первым результатом такой работы был созданный в конце 1992 года аналог алгоритма ЭльГамаля НОТАРИУС-1.Основное отличие алгоритма НОТАРИУС-1 от алгоритма ЭльГамаля состоит в том, что вместо обычной операции умножения целых чисел по модулю большого простого p, как это делается у ЭльГамаля, алгоритм НОТАРИУС-1 использует похожую операцию, эффект от использования которой состоит в том, что обеспечивая точно такой же уровень стойкости, что и умножение по модулю простого числа, эта операция гораздо эффективней вычисляется на распространенных процессорах Intel, Motorola и др.

Процедуры подписывания электронных документов и проверки цифровых подписей по алгоритму НОТАРИУС-1 выглядят аналогично соответствующим процедурам алгоритма ЭльГамаля, обеспечивают тот же уровень стойкости подписи, но выполняются быстрее.

Затем, аналогичным образом был усовершенствован алгоритм DSA, который послужил основой для алгоритма цифровой подписи, названного НОТАРИУС-D.

Реализация этого алгоритма на стандартном процессоре Intel486DX4(100) позволила добиться времени подписывания электронного документа объемом 1 KB вместе с его предварительным хэшированием в 0.014 сек., а времени проверки подписи под документами такого объема, - 0.027 сек.

Если же объем документа равен 100 KB , время подписывания составляет 0.124 сек., а время проверки - 0.138 сек. Длина подписи 40 байт, стойкость - 10**21.

Дальнейшее совершенствование алгоритмов подписывания и проверки произошло за счет использования совместно с нашими, также запатентованных в США и Германии идей немецкого криптографа Клауса Шнорра, который предоставил нам право использования своего алгоритма на территории стран СНГ. Совместное применение этих идей привело в 1996 году к разработке алгоритма НОТАРИУС-S, который при сохранении стойкости подписи позволил сократить ее длину еще на 32.5%. Для базового варианта с ключами из 64 байт длина подписи сократилась относительно DSA и НОТАРИСА-D с 40 байт до 27 байт. Соответственно уменьшилось время вычисления и проверки подписи. Стойкось осталась на том же уровне - 10**21.

Эти алгоритмические разработки позволили нам предложить пользователю широкий выбор программ с длинами цифровой подписи от 16 до 63 байт и уровнями стойкости, соответственно, от 10**14 (или несколько дней работы сети из несколькими десятков персональных компьютеров) до 10**54 (или более 100 миллиардов лет непрерывной работы любой мыслимой вычислительной системы обозримого будущего). Более детальные технические характеристики различных алгоритмов приведены ниже, в Таблице 1.

Автор надеется, что параметры алгоритмов, приведенные в таблице, дадут читателю возможность оценить их основные качества без дальнейших пространных комментариев. Дополнительных пояснений требуют только разделы таблицы, посвященные алгоритму ГОСТ 34.10.

ГОСТ34.10. Стандарт на электронную подпись ГОСТ34.10 был опубликован впервые Госстандартом РФ в мае 1994 года и введен в действие с 1 января 1995 года. В предварительном варианте он был введен в качестве ведомственного стандарта на цифровую подпись ЦБ РФ и использовался в этом качестве с сентября 1993 года по декабрь 1994 года. Алгоритмы вычисления и проверки подписи в ГОСТ34.10 устроены аналогично алгоритму DSA, но предварительная обработка электронных документов перед подписыванием (так называемое хэширование) выполняются по другому, существенно более медленному способу. К сожалению, разработчики допустили целый ряд досадных ошибок, которые есть даже в официальном тексте стандарта. Поэтому при реализации следует быть внимательным и не всегда следовать формальному тексту.

Мы рассматриваем следующие виды угроз:

1. Предполагаем, что попытки подделать подпись предпринимают не профессионалы. "Злоумышленники" могут располагать сетью из нескольких персональных компьютеров, общая вычислительная мощность которой равна 2*10⁸ операций/сек.

Предполагаем, что "противостоим" профессионалам с вычислительной системой общей мощностью до 10¹² операций/ сек. Это может быть сеть из нескольких десятков мощных современных суперкомпьютеров.

Предполагаем, что "противостоим" самой мощной государственной спецслужбе, располагающей возможностью ( и желанием ) создать для этой задачи сеть из сотен специализированных параллельных суперкомпьютеров с 1000 специальных мощных

( по 10¹³ оп./ сек.) процессоров каждый и практически неограниченной памятью.

Фантазии на тему будущего.

Фантазии на тему далекого будущего.

СЕРТИФИКАЦИЯ.

Принятые в различных странах в настоящее время процедуры сертификации, которые могут быть применены к программам или программно-аппаратным реализациям цифровой подписи, состоят в проверке соответствия, реализованных разработчиком алгоритмов описанным в официальных текстах стандартов.

В США, аккредитованные Национальным институтом стандартов и технологий лаборатории проводят тестирование процедуры порождения простых чисел, определяющих параметры алгоритма DSA, на основании опубликованных в тексте стандарта конкретных значений параметров и начальных установок процедуры генерации простых чисел, затем, при тестовых значениях параметров алгоритма, тестовых индивидуальных ключах и тестовых рандомизирующих значениях подписывания производится вычисление и проверка цифровых подписей под тестовыми примерами электронных документов. Таких циклов тестирования может быть довольно много - до нескольких десятков тысяч. Вся последовательность результатов предъявляется в лабораторию для сравнения с результатами работы эталонной программы на таких же значениях входных параметров. По результатам сравнения делается заключение о соответствии данной реализации цифровой подписи стандарту.

Таким же или примерно таким образом происходит процесс сертификации программ цифровой подписи и в ряде западноевропейских стран.

У нас ситуация оказывается, мягко говоря, парадоксальной. Поскольку в официальном тексте стандарта есть ошибки, которые, будь он реализован строго формально, привели бы к совершенно другому алгоритму цифровой подписи, о стойкости которого можно только догадываться (особенно при специальном "неудачном" выборе параметров), то проверить для программных или аппаратных реализаций "соответствие стандарту ГОСТ34.10" просто невозможно. Если реализация абсолютно точно соответствует формальному тексту стандарта с ошибками,