решения известной сложной вычислительной задачи. Поскольку задача является

общеизвестно сложной, то если ее не научились решать за обозримое время все

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

ее не сумеют решить быстро и в ближайшем будущем.

Практический результат последующих 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 секунды при размере

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11