Поскольку большинство операций при вычислении подписи и ее проверке также производится по модулю из 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*108 операций/сек.

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

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

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

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

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

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

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

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

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

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