Перспективы развития и использования асимметричных алгоритмов в криптографии

В статье, рассчитанной на специалистов
(теоретиков и практиков) в области защиты информации, знакомых с проблематикой
асимметричной криптографии,изложено нынешнее состояние проблемы и рассмотрены
направления вероятного развития криптографии с открытым ключом в ближайшем
будущем. Традиционно
считается, что концепция асимметричной криптографии впервые была предложена в
1976 году Уитвелдом Диффи и Мартином Хеллманом нанациональной компьютерной
конференции [1] и опубликована в том же году в основополагающей работе
Новые направления в криптографии [2]. Кчислу отцов-основателей
асимметричной криптографии относят также и Ральфа Меркля, который независимо от
Диффи и Хеллмана пришел к тем же конструкциям,однако опубликовал свои результаты
только в 1978 году [3]. На приоритет в открытии асимметричной криптографии
претендует и Агентствонациональной безопасности США. В статье энциклопедии
Британника директор АНБ Симмонс заявляет, что двухключевая
криптография былаизвестна в Агентстве за 10 лет до публикации Диффи и
Хеллмана [4]. В настоящее время термином
асимметричная криптография обозначают большую группу механизмов,
алгоритмов, протоколов и идей,применяемых при разработке систем защиты
информации. Перечислим основные из них и кратко прокомментируем, что конкретно
понимается под каждым термином(систематический словарь терминов из области
асимметричной криптографии приведен в работе [5]). 2) односторонняя функция с секретом (One-way trap-door
function) - этонекоторая функция FK: X®Y, зависящая от параметра K (ее можно
рассматривать также как параметризованное семейство функций) и обладающая
следующимисвойствами: a) при любом значении параметра K существует
полиномиальный алгоритм вычисления значения функции в любой точке FK(x) при
условии, чтопараметр K неизвестен; в) при
известном значении параметра K существует полиномиальный алгоритминвертирования
функции FK (здесь не обсуждается модель вычислений, в рамках которой мы говорим
об их полиномиальности). Понятие односторонней функции с секретом явилось
исходным для асимметричной криптографии. Собственно, тот факт, что для
вычисления самой функции сполиномиальной сложностью и для ее инвертирования
требуется различная исходная информация (то есть наличие определенной
асимметрии), и дал название новомунаправлению в криптографии. 3)
криптографические протоколы - это такая процедура взаимодействия абонентов,в
результате которой они достигают своей цели, а их противники - не достигают. Под
это неформальное определение подпадают все практически интересные
способыприменения асимметричной криптографии: · протоколы
электронной цифровой подписи; ·
электронные деньги (здесь, на самом деле, имеется в виду целая
совокупность протоколов взаимодействия между различными участниками
системы). Формальные определения для перечисленных протоколов даны в книге
[5]. В последнее время число различных типов криптографических протоколов
стремительнорастет, но, поскольку большая их часть представляет (пока) чисто
теоретический интерес, мы на них останавливаться не будем. 4) доказательства
(интерактивные) с нулевым разглашением - это общая теоретическая модель, к
которой в 1985-1986 годах пришли исследователиразличных криптографических
протоколов: [6], [7]). Качественно, доказательство (интерактивное) с нулевым
разглашением можноопределить как протокол взаимодействия двух абонентов:
Доказывающего (обозначение - P от английского Prover) и Проверяющего
(обозначение - V отанглийского Verifier). Абонент P хочет доказать проверяющему
V, что некоторое утверждение S истинно. Протокол при этом должен удовлетворять
условиям: а)полноты - если S истинно, то P убедит абонента V признать это; б)
корректности - если S ложно, то P вряд ли убедит V, что S истинно; в) свойству
нулевогоразглашения - в результате выполнения протокола Проверяющий V не сможет
извлечь никакой дополнительной информации о том, почему S истинно (см. например,
[8]). Доказательства с нулевым разглашением заслуживают отдельного упоминания
не только потому, что их идея позволяет с единой позиции взглянуть на
большинствокриптографических протоколов, но также и потому, что они, по-
видимому, будут основным объектом изучения нового, бурно развивающегося
направления вматематике и теоретической криптографии. Кроме того, доказательства
с нулевым разглашением находят важные практические сферы применения (например, в
областиразработки протоколов для интеллектуальных карточек [5]).
Двигателем развития асимметричной
криптографии, без сомнения, являются потребности практики. В связи с бурным
развитием информационных систем(в первую очередь здесь следует отметить
поразительные успехи инженерной мысли в области развития аппаратных средств),
расширением их инфраструктурыпрактические потребности ставят новые задачи перед
разработчиками криптографических алгоритмов. На сегодняшний день основные
побудительные мотивыразвития асимметричной криптографии, на наш взгляд, можно
сгруппировать следующим образом (приведенная ниже классификация отражает
наиболеесущественные из них и не претендует на то, чтобы быть
исчерпывающей): - потребности развивающихся телекоммуникационных сетей
самого разнообразногоприменения, в том числе имеющих сложную топологию; - потребности банковских систем (в том числе использующих
интеллектуальные карты); Несмотря на снисходительную улыбку, вызываемую обычно последним
побудительныммотивом, нельзя не учитывать, что на сегодняшний день проблемы
асимметричной криптографии превратились в самодостаточную область исследований.
Вопросыпостроения криптографических протоколов, доказательств с нулевым
разглашением, теоретико-числовые аспекты асимметричной криптографии постоянно
входят в числообсуждаемых проблем на ряде авторитетных ежегодных научных
конференций, из которых наиболее высоким рейтингом обладают STOC (ACM Symposium
on Theory ofComputing) и FOCS (IEEE Annual Symposium on Foundations of Computer
Science). В последнее время к ним по уровню приближаются криптографические
конференцииEUROCRYPT, ASIACRYPT и CRYPTO. Многие авторитетные ученые начинают
включать в круг своих интересов и вопросы криптографии. Все эти факты необходимо
учитыватьпри разработке проблем, лежащих на стыке политики и криптографии.
Следует отметить и имеющую место, в определенном смысле, негативную
тенденцию.Иногда алгоритмы асимметричной криптографии пытаются использовать там,
где они по существу не нужны. Например, порой авторы не делают различия между
понятиямиимитоприставки и цифровой подписи. Общеметодологические проблемы
криптографии Осмысление конструкций асимметричной криптографии привело
исследователей к постановке проблем, имеющих отношение к криптографии в
целом:получение необходимых и достаточных условий существования функций с
секретом, односторонних функций, пар подстановок с трудно
обнаружимыми зубьями . Решение любой из упомянутых проблем, кроме
продвижения в философском понимании вопроса, без сомнения, даст интересные и для
практическихприложений конструкции. Перечень наиболее распространенных асимметричных
криптоалгоритмов Прежде всего назовем наиболее распространенные (наиболее
часто обсуждаемые) алгоритмы асимметричной криптографии: 1. Схема Диффи-
Хеллмана в мультипликативной группе конечного поля (статья 1976 года) и в группе
точек эллиптической кривой над конечным полем Нила Коблица[9]. 3. Схемы типа Фиата-Шамира [11]. 6. Теоретико-кодовые конструкции МакЭлиса [14]. Названные схемы
достаточно известны, поэтому формально описывать их не будем (тем более что их
описанию посвящены отдельные публикации). Со всемиперечисленными схемами связан
ряд теоретических проблем. Ниже мы приведем основные из них и укажем последние
опубликованные достижения по каждой. 1. Проблема эквивалентности задачи Диффи-Хеллмана и задачи
логарифмирования в соответствующей группе. Практически очевидно, что задача
Диффи-Хеллмана не сложнее задачи логарифмирования (если мы умеем
логарифмировать, то система открытогораспределения ключей Диффи-Хеллмана
нестойкая). Хотя большинство исследователей склоняется к мнению, что эти задачи
эквивалентны, вопрос о том, верно лиобратное, на сегодняшний день открыт.
Эквивалентность, при некоторых дополнительных условиях, доказали Маурэр [15] и
ден Бур [16]. Из отечественныхисследователей сильный результат по данной
проблематике получен М. А. Черепневым, которому удалось построить
субэкспоненциальный алгоритм сведениязадачи дискретного логарифмирования в
простом конечном поле к задаче Диффи-Хеллмана. Наиболее же близки к решению
проблемы швейцарские ученые [17]. 3. Проблема
эквивалентности задачи вскрытия системы RSA и задачи факторизации целых чисел
(под секретным ключом понимается экспонента e). Задача определения секретного
ключа здесь эквивалентна факторизации, тем не менее, вопрос об эквивалентности
бесключевого чтения и факторизации открыт. Вто же время известны частные случаи,
когда задача решается легко (случай, так называемых, слабых
ключей ). 4. Проблема построения стойких (доказуемо) криптографических
протоколов в предположении о существовании тех или иных криптографических
примитивов. Теоретико-числовые
проблемы Далее, приводя субэкспоненциальные асимптотические оценки
сложности алгоритмов, будем традиционно пользоваться следующим обозначением:
Следует
отметить, что многие из асимптотических оценок носят эвристическийхарактер,
часть из которых доказана в предположении истинности гипотезы (расширенной)
Римана. Ряд исследователей проводят работы по строгомудоказательству этих
эвристических оценок. По-прежнему актуальной остается задача получения не
асимптотических, а точныхоценок трудоемкости для ряда разработанных алгоритмов.
Практически сразу после опубликования работы У. Диффи и М.
Хеллмана Дж. Поллард публикует вероятностные алгоритмы решения задачидискретного
логарифмирования, имеющие корневую оценку сложности и не требующие большого
объема памяти [18]. Этот метод называют r-методом Полларда (вариацияметода - l-
метод Полларда, общая идея известна также под названием baby step, giant
step ). В дальнейшем основные идеи построения эффективных алгоритмов для
решения задачи дискретного логарифмирования были связаны с, так называемым,
методом решета.Долгое время асимптотически наиболее эффективным (асимптотическая
оценка сложности - , оставался метод
Д. Копперсмита, А. Одлыжко, Р. Шрёппеля [19]. Метод был реализован иприменен для
логарифмирования в простых полях при p длиной до 67 десятичных знаков.
Последним существенным достижением в этой области является метод решетачислового
поля Д. Гордона [20]. Асимптотически метод более эффективен, чем все предыдущие:
оценка его трудоемкости . Однако его
практическая реализация сложнее: пока имеется сообщение, что этим методомудалось
решить задачу дискретного логарифмирования в простом поле при p длиной 40
десятичных знаков. Для этого специалистам немецкого университета Universitatdes
Saarlandes в Саарбрюккене потребовались 21 час работы рабочей станции Sparc и 40
минут работы суперкомпьютера Cray [21]. По последним данным 1997 годанемецким
исследователям удалось реализовать процедуру логарифмирования для чисел длиной
85 десятичных знаков. За каждым из названных методов стоит целый спектр их
модификаций и вариантов. Из отечественных исследователей, работающих в этом
направлении необходимоназвать О. Н. Василенко и И. А. Семаева. В тезисах
выступлений последнего на конференциях по теории чисел и ее приложениям (Тула,
Воронеж) содержатся весьмаинтересные новые идеи в развитие метода решета.
Исследователи постоянно предпринимают попытки поиска принципиально иныхподходов
(отличных от идей метода решета) к задаче дискретного логарифмирования. Из
опубликованного здесь следует упомянуть работы, связанныес попыткой
использования частных Ферма [22], [23], однако, пока успешное логарифмирование
этим методом требует большего объема информации, чем классическая
постановка задачи. Также следует упомянуть о том, что с середины 1997 года
в научной средециркулируют слухи о том, что российскому ученому С. А. Степанову
удалось построить полиномиальный алгоритм дискретного логарифмирования. Однако,
вплотьдо сегодняшнего дня убедительные подтверждения этому факту отсутствуют,
впрочем, как и убедительные опровержения. По сравнению с задачей дискретного логарифмирования
задача факторизации чисел или разложения их на множители имеет более
длительнуюисторию, ведомую обычно с античных времен от Эратосфена
(предположительно 284 - 202 гг. до н.э.), а в дальнейшем связанную с именами
таких великих математиков,как Фибоначчи (предположительно 1180-1250 гг.), Ферма
(1601-1665 гг.), Эйлер (1707-1783 гг.), Лежандр (1752-1833 гг.), Гаусс (1777-
1855 гг.). В большинствеслучаев удается разложить число на множители с помощью
пробных делений на первые (маленькие) простые числа. Задача становится
содержательной, когдатребуется разложить число, равное произведению двух больших
простых чисел (например, число Блюма). В 70-х годах был предложен (p-1)-метод
Полларда [24],эффективный для случая, когда p-1 раскладывается на маленькие
простые множители, где p - один из делителей факторизуемого числа. Вскоре, как
развитиеданного решения появился (p+1)-метод Полларда. Следующим шагом в этом
направлении стала идея использования псевдослучайных отображений (r-
методПолларда). Этим методом было разложено на множители 8-ое число Ферма ( - число
длиной 77 десятичных знаков). Дальнейшее развитие этих идей вылилось в методы
сиспользованием группы точек эллиптической кривой [25]. На сегодняшний день,
как и для задачи дискретного логарифмирования, основныепродвижения в проблеме
факторизации связаны с развитием методов решета, в которых выделяют следующие
этапы развития: методы линейного решета, методыквадратичного решета [26] и метод
решета числового поля [27], [28]. Сегодня практически наиболее эффективным для
факторизации чисел длиной до 130десятичных знаков остается метод квадратичного
решета. Его асимптотическая оценка трудоемкости - , где . Именно
этим методом был решен предложенный Райвестом практический пример
вскрытиясистемы RSA [29], для чего потребовалось разложить на множители число
длиной 129 десятичных знаков. Методы решета числового поля асимптотически
более эффективны (оценка трудоемкости: ), но применимы
только для чисел вида n=re-s, где r и s сравнительно малы. Напрактике считается,
что рассматриваемые методы следует применять для чисел из интервала
10130<n<10160. Именно таким образом в 1993 году были полученырекордные
разложения: 9-ое число Ферма (2512+1 - длина 155 десятичных знаков); 2523-1 -
длина 159 десятичных знаков. Как уже было сказано выше, новые идеи в развитие
метода решета содержатся в работах И. А. Семаева, что позволяет надеяться на
дальнейший прогресс в данной проблематике. Для нужд
практической криптографии актуальна проблема построения быстрых алгоритмов
нахождения случайных простых чисел заданнойдлины. Скорость работы
алгоритмов построения больших простых чисел важна для систем, использующих схему
RSA, так как ключами в них собственно и являютсябольшие простые числа. Обычно в
этих алгоритмах реализуется какая-либо модификация решета с
последующей проверкой чисел на простоту. Приэтом используется тот факт, что
простые числа расположены достаточно густо : результаты о плотности
распределения простых чисел срединатуральных образуют отдельное направление в
теории чисел. В частности для функции p(x), равной количеству простых чисел
меньших x, имеет местоасимптотическое равенство: . На сегодня известно
достаточно много алгоритмов проверки чисел на простоту: какправило, ответ на
этот вопрос дает уже малая теорема Ферма. Проблема заключается в доказательстве
того, что проверяемое число действительно являетсяпростым. Несмотря на то, что
большинство из таких алгоритмов имеет субэкспоненциальную оценку сложности, на
практике они показывают вполнеприемлемую скорость работы. Из отечественных
ученых существенный вклад в эту проблематику внес Ю. В. Нестеренко
[22]. Существуют вероятностные алгоритмы, имеющие полиномиальные оценки
сложности [30]: подробные обзоры публикаций по этой теме подготовлены О. Н.
Василенко. Важной особенностью известных методов дискретного логарифмирования
является существенная зависимость их трудоемкости от мощности простого поля, в
которомрешается задача. Отсюда возникает необходимость разработки как алгоритма
проверки простого числа на слабость , так и алгоритма,
позволяющегогарантированно избегать построения слабых чисел. Более
подробно эти вопросы рассмотрены в [31]. Помимо
методов, применимых для логарифмирования в произвольной конечной группе, здесь
известны работы И. А. Семаева [32], в одной из которыхрассматривается метод,
идейно близкий методам логарифмирования в конечном поле Адлемана Л. [33]. В
другой работе для эллиптических кривых специального вида(накладываются некоторые
условия на модуль арифметики и на мощность группы точек) И. А. Семаев указал
способ сведения с полиномиальной сложностью задачилогарифмирования в группе
точек эллиптической кривой к задаче логарифмирования в некотором расширении
простого поля. При этом используется, так называемое,спаривания Вейля, после
чего можно применять известные субэкспоненциальные методы. Аналогичные
результаты были опубликованы и за рубежом [34]. Точные
формулы для мощностей групп точек эллиптической кривой известны только для
достаточно узкого класса кривых. На практике актуальназадача построения систем
асимметричной криптографии, где сама кривая является долговременным
ключом. Таким образом возникает проблема построенияэффективных алгоритмов
вычисления мощности группы точек эллиптической кривой произвольного вида. Здесь
известен вероятностный алгоритм Шенкса [35],основанный на идее типа baby
step, giant step . Метод имеет оценку сложности , где q - мощность
конечного поля. Из детерминированных алгоритмовизвестен метод Скуфа [36],
основанный на использовании эндоморфизма Фробениуса и имеющий оценку сложности ,
где q - мощность конечного поля. Однако дляпрактических вычислений метод, по-
видимому, мало пригоден. Хороший обзор по этому вопросу содержится в работе Х.
В. Ленстры младшего [37]. В последнее время исследования в
вопросах реализации асимметричных криптоалгоритмов на различных вычислительных
средствах (отинтеллектуальных карт до параллельных вычислительных систем)
фактически вылились в отдельное направление. С этим же тесно связаны проблемы
эффективнойреализации арифметических операций в конечных полях (см., например,
[38]). Важной и интересной задачей является проблема разработки протоколов
безопасныхраспределенных вычислений (например, требуется предложить протокол
взаимодействия интеллектуальной карты и терминала, при котором
трудоемкаяоперация возведения в степень выполняется с помощью последнего, причем
терминал не получает в результате протокола никакой информации о том, в какую
степеньвозводится основание). Сообщение о том, что схема Меркля-Хеллмана (напомним, что она разработана
в 1978 году) взломана, в открытой печати появилось в 1984
году[39]. ТогдаМеркль публикует схему типа рюкзак с нескольким
итерациями, но и этот вариант был взломан [40], после чего Меркль заплатил
Шамиру иБрикеллю 100$ и 1000$ соответственно, обещанные им тем, кто взломает
системы. В 1984 году Шор и Райвест разрабатывают свой вариант схемы
на рюкзаке , в котором не используется операция модульного умножения.
Его доработанная версия опубликована в 1988 году [41]. С
использованиемалгоритмов приведения целочисленных решеток, Шнорр и Хёрнер в 1995
году нашли подходы к вскрытию и этой системы при некоторых параметрах (но не
тех, которыерекомендовали использовать Шор и Райвест) [42]. Практически используемые алгоритмы
асимметричной криптографии основаны на двух задачах: дискретного
логарифмирования и факторизации.Существуют различные мнения о возможности
решения этих задач в будущем и о том, как скоро это может произойти. Поэтому для
специалистов в области защиты информациипостоянно остается актуальной задача
разработки альтернативных систем. При этом главными остаются проблемы
существования односторонней функции и функции ссекретом. Здесь следует выделить
следующие направления исследований. 1. Глобальная теоретическая идея
построения новых асимметричных криптосистемзаключается в попытке порождения
функций с секретом с помощью маскирования простых задач под сложные
(NP-полные). Было предложеномного вариантов, но все они оказались
нестойкими. 2. Полученные результаты по вскрытию некоторых вариантов
криптосхемы на основезадачи о рюкзаке сформировали в среде
криптографов-практиков скептическое отношение ко всем подобным схемам. В то же
время, формально схемаШора-Райвеста не взломана по сей день. Ряд
криптографов-теоретиков считают задачу о рюкзаке одной из
самыхперспективных для построения алгоритмов асимметричной криптографии,
поскольку сложность заложена в самой ее природе. Крометого, в
случаеуспехатакой схеме, по-видимому, не будет равных по эффективности (скорости
работы). 3. Схема открытого распределения ключей с использованием
некоммутативных группбыла предложена лабораторией МГУ по математическим
проблемам криптографии в 1993 году, что явилось принципиально новым подходом к
этой задаче. Однако досегодняшнего дня практически реализуемых схем, основанных
на этих идеях, не предложено. 4. После того, как Сидельников и Шестаков,
используя быстрые алгоритмы декодирования, показали, что одна из схем типа
МакЭлиса (схема Нидеррайтера) -нестойкая, был предложен ряд вариантов схемы на
основе теоретико-кодовых конструкций. Практического применения не нашла ни одна
из них либо в силу своейгромоздкости, либо в силу того, что ее стойкость
вызывает большие сомнения у специалистов. 5. Реализация протоколов
асимметричной криптографии (в первую очередь, схем электронной цифровой подписи)
с использованием традиционных криптографическихсхем. Это направление, на наш
взгляд, не заслуженно находится в тени. Теоретическая возможность построения
таких систем показана Лампортом, Наором иЮнгом. Известна также интересная статья
Березина и Дорошкевича [43], где приведены схемы ЭЦП, основанные на симметричных
алгоритмах. Кроме того,корпорация IBM в некоторых из разработанных ею банковских
систем реализует схемы ЭЦП на основе алгоритма DES с использованием защищенных
модулей. 6. С начала 90-х годов широко обсуждается возможность реализации
протоколов асимметричной криптографии на основе квантово-механических эффектов
[44], [45]. Юридические вопросы использования асимметричных алгоритмов в системах
Большинство алгоритмов асимметричной
криптографии защищено патентами. При рассмотрении этого вопроса следует иметь в
виду, что всоответствии с законодательством США патенты в этой стране выдаются
сроком на 17 летбез права их возобновления. Кроме того, патентодержатель,
возбудившийдело о защите своих прав на данный патент и не сумевший выиграть
дело, автоматически теряет все права по данному патенту.
США 4218582 19 августа 1984 года 2006580 18
августа 1982 Франция 2405532 8 июня
1979 Схема RSA запатентована только в США:
патент № 4,405,829 от 20 сентября 1983года, срок действия истекает 20 сентября
2000 года. Запатентованы также некоторые модификации данной схемы: например,
схема Полига-Хеллмана имеетпатент США № 4,424,414 от 8 января 1984 года (эта
модификация запатентована также и в Канаде). Схема Эль-Гамаля не
запатентована, однако некоторые организации считают, что патент на схему Диффи-
Хеллмана покрывает и все модификации схемы Эль-Гамаля. Схема Диффи-Хеллмана
(держатели патента - Диффи, Хеллман, Меркль): патент США № 4,200,770 от 29
апреля 1980 года (истек 29 апреля 1997 года); патент Канады №1,121,480 от 6
апреля 1982 года. Схема Шнорра: патент США № 4,995,082 от 19 февраля 1991
года (истекает 19февраля 2008 года). Кроме США, этот алгоритм запатентован также
в ряде других стран. Схема DSA (стандарт США на ЭЦП): формальный держатель
патента - Дэвид Кравитц(бывший сотрудник АНБ, см.[46]): патент США № 5,231,668
от 27 июля 1993 года. Однако, права на этот алгоритм оспаривают Диффи, Хеллман,
Меркль и Шнорр. Держателем пяти из выше приведенных патентов является группа Public
KeyPartners, специально созданная компаниями RSA Data Security Inc. (65% акций)
и Caro-Kahn Inc. (35% акций): 4,200,770 29.03.80 Hellman, Diffie, Merkle открытое
распределение ключейДиффи-Хеллмана 4,405,829 20.09.83 Rivest,Shamir, Adleman
схема RSA Экспортно-импортные
ограничения Правительства ряда стран относят криптографию к военным
технологиям. Контролем за экспортом криптографических средств в США
занимаютсядва правительственных ведомства: Bureau of Export Administration (BXA)
in the Department of Commerce, руководствующееся в своей деятельности
сериейзаконодательных актов под общим названием Export Administration
Regulations (EAR) и Office of Defense Trade Controls (DTC) in the State
Department,руководящими документами для которого является серия законодательных
актов под общим названием International Traffic in Arms Regulations
(ITAR).Распространение криптографических средств подпадает также под ограничения
CoCom (Coordinating Committee for Multilateral Export Controls). Ограничения
касаются схем стойкой (strong) криптографии. Для систем с открытым
ключом к таковым относят схемы с длиной ключа более 512 бит (длясравнения - для
симметричных криптоалгоритмов нижняя граница длины ключа исчисляется 40 битами).
Однако, при рассмотрении вопроса о выдаче разрешения на экспортрассматривается
все-таки не сам криптографический алгоритм, а то приложение, в рамках которого
он работает. Так, обычно дают разрешение на экспорт стойкихкриптографических
средств, используемых в · приложениях,
работающих с данными, представленными в аналоговой форме; ·
системах аутентификации; Возможно, в связи с программой депозита ключей , часть
законодательных актов США в этой области будет в ближайшее время пересмотрено.
В
связи с разработкой алгоритмов электронной цифровой подписи встает проблема
перехода на юридически значимые электронные документы. Этазадача связана с
большими организационно техническими и правовыми проблемами. Однако преимущества
такого подхода получают все большее признание в мире. Так,в августе 1997 года в
Италии вступил в силу Закон Бассанини № 59/97 от 15.03.97,
обязывающий все государственные органы к 31.12.98 быть готовымидля работы с
электронными документами. Аналогичный законопроект внесен в США конгрессменами
А. Ишу и Б. Тозин. Комиссия ООН по международному торговому законодательству
инициировала создание модели закона о безопасной электронной торговле, включая
закон об электроннойцифровой подписи. Зарубежные и международные стандарты на алгоритмы
асимметричной криптографии 1. В США вопросами стандартизации
криптоалгоритмов занимается Национальный институт стандартов и технологии (NIST
- National Institute ofStandards and Technology) - одно из подразделений U.S.
Department of Commerce. До 1988 года NIST назывался National Bureau of
Standards. В соответствии сзаконом от 1987 года Computer Security Act (Public
Law 100-235) NIST обязан координировать свою деятельность по вопросам защиты
информации с АНБ США. Касимметричным алгоритмам, стандартизированным NIST,
относится американский стандарт на цифровую подпись DSA. 2. Международная
организация по стандартам ISO в середине 80-х годов приняла решение, во-первых,
заниматься не стандартизацией алгоритмов, атолько их регистрацией и, во-вторых,
принимать к рассмотрению только алгоритмы шифрования. В настоящее время из
алгоритмов асимметричной криптографии в ISOзарегистрирована только схема LUC
(некоторое обобщение схемы RSA, где вместо экспоненты применены подстановочные
полиномы). Кроме алгоритмов ISOзарегистрировала ряд используемых в сетях
протоколов (X.509 - протокол вычисления сертификата и др.) 3. Компания
RSA Data Security, Inc. предпринимает активные попытки введения де-факто
промышленных стандартов на собственныекриптографические алгоритмы - так
называемых Public-Key Cryptography Standards (PKCS), описывающих интерфейсы,
форматы представления данных и алгоритмы (всего12 стандартов, принятых с 1993 по
1995 годы). Порядок принятия и пересмотра стандартов PKCS отступает от принятых
норм рассмотрения документов такого рода.PKCS по интерфейсу совместимы с X.509
частично. 4. Европейское Сообщество (ЕС) организовало собственную
программу Research and Development in Advanced Communication Technologies
(RACE). В неевошли 6 основных Европейских центров по криптографии: Center for
Mathematics and Computer Science (Amsterdam), Siemens AG, Philips Crypto BV,
Royal PTTNederland NV (PTT Research), Katholieke Universiteit Leuven, Aarhus
Universitet. В июне 1992 приняты стандарты RACE Integrity Primitives
Evaluation(RIPE) и Integrity Primitives, опирающиеся на схему RSA.
1. Для алгоритмов шифрования,
аутентификации, контроля целостности сообщений и управления ключами в сети
Internet приняты стандартыInternet Privacy-Enhanced Mail standards (PEM). Эти
протоколы разработаны в рамках групп Internet Resources Task Force (IRTF) и
Privacy and SecurityResearch Group (PSRG), затем переданы Internet Engineering
Task Force (IETF) PEM Working Group и, наконец, приняты Internet Architecture
Board (IAB).Протоколы опубликованы в серии Request for Comment (RFC). PEM
поддерживают протокол X.509 и алгоритм RSA (для ключей длиной до 1024 бит).
Существует такжевоенный аналог PEM, разработанный АНБ США в конце 80-х годов
(Message Security Protocol - MSP). 2. Созданная в марте 1996 года фирма
Pretty Good Privacy, Inc. для распространения коммерческих версий,
разработанного Филиппом Циммерманомпрограммного продукта PGP, предпринимает
активные попытки по введению де-факто в качестве стандарта в Internet своего
алгоритма, являющегося, по сути,алгоритмом RSA с длиной ключа - 2047 бит).
Сегодня сложно предсказывать дальнейшее развитие ситуации, поскольку PGP, Inc.
вынуждена обсуждать проектывнедрения в свои алгоритмы процедур депонирования
ключей, что неизбежно подрывает доверие к системе в целом со стороны
пользователей. Алгоритм RSA,
лицензированный группой Public Key Partners, используется многими крупными
компаниями: IBM, Microsoft, Lotus, Apple, Novell,Digital, National
Semiconductor, AT&T, Sun. Лицензию для внутрикорпоративного использования
схемы RSA имеют также Boeing, Shell Oil,DuPont, Raytheon, Citicorp, TRW
Corporation, причем последняя компания приобрела лицензию только после судебного
разбирательства в 1992 году. Алгоритмы асимметричной криптографии (в частности, схема открытого
распределения ключей) реализованы в телефонной аппаратуре серии STU(Secure
Telephone Unit): STU-II, STU-III. В последние несколько лет в США ведется
активная политическая борьба вокругпопыток принудительного внедрения в сети
связи Clipper Chip (также называемого MYK-78T). Основные проблемы здесь связаны
с процедурой депонирования ключей.Нам же хотелось лишь упомянуть, что Clipper
Chip позволяет выполнять и некоторые протоколы асимметричной криптографии.
Потребности практики подтолкнули Россию к разработке и опубликованиюсобственного
стандарта на ЭЦП. Из
отечественных коммерческих средств защиты информации, реализующих
алгоритмыасимметричной криптографии, наиболее известна на рынке Верба-
О московского отделения Пензенского научно-исследовательского
электротехническогоинститута [47]. На свою роль на этом рынке претендуют и
некоторые другие коммерческие фирмы, например, ЛАН-Крипто. Однако, как правило,
у этих фирм неотрегулированы юридические вопросы их деятельности, а
криптографические качества их продуктов далеко не бесспорны. Однозначного ответа на вопрос о том,
какие алгоритмы - симметричные или асимметричные - предпочтительнее, на сегодня
нет. Обычно к достоинствам асимметричной криптографии относят отсутствие
необходимости в предварительном доверенном обмене ключевыми элементами
приорганизации секретного обмена сообщениями. Однако, возникает потребность в
обеспечении аутентичности открытых ключей, что порой превращается в
весьманетривиальную задачу. То же самое относится и к протоколам цифровой
подписи. Кроме того, существующие асимметричные алгоритмы заметно
проигрывают поскорости симметричным криптосистемам. Целесообразность применения
криптосистем того или иного типа (или их комбинации), конечно, определяется теми
условиями,в которых их предполагается использовать, поскольку существуют
приложения, где асимметричная криптография заведомо хуже симметричной (например,
при использованиикриптографического алгоритма только для защиты информации на
компьютере и отсутствии обмена сообщениями). Несмотря на острую потребность
современных информационно-телекоммуникационных систем в протоколах асимметричной
криптографии на сегодняшний день реализуютсяи активно используются только
системы на основе дискретного логарифма и факторизации, над которыми продолжает
висеть дамоклов меч ихвозможной полной компрометации.
1. Diffie W., Hellman M. E. Multi-user
Cryptographic Techniques , Proceedings of AFIPS National Computer
Conference, 1976,pp.109-112. 2. Diffie W., Hellman M. E. New
Directions in Cryptography , IEEETransactions on Information Theory, v.IT-
22, n.6, November 1976, pp. 644-654. 3. Merkle R. C. Secure
Communication Over Insecure Channels ,Communications of the ACM, v.21, n.4,
1978, pp.294-299. 5. Анохин М. А., Варновский Н.
П., Сидельников В. М., Ященко В. В. Криптография в банковском деле ,
МИФИ, 1997. 6. Goldwasser S., Micali S., Rackoff C. The Knowledge
Complexity of Interactive Proof Systems , Proceedings of the 17th ACM
Symposium onTheory of Computing (STOC), 1985, pp.291-304. 7. Goldwasser S.,
Micali S., Rackoff C. The Knowledge Complexity ofInteractive Proof
Systems , SIAM Journal on Computing, v.18, n.1, February 1989, pp.186-
208. 9. Koblitz N. Elliptic Curve
Cryptosystems , Mathematics of Computation,48, 1987, pp.203-209. 10.
Rivest R. L., Shamir A., Adleman L. M. A Method for Obtaining
DigitalSignature and Public-Key Cryptosystems , Communications of the ACM,
21(2), February 1978, pp.120-126. 11. Feige U., Fiat A., Shamir A.
Zero-Knowledge Proofs of Identity , Journal of Cryptography, 1, 1988,
pp.66-94. 12. ElGamal T. A Public-Key Cryptosystem and a Signature
Scheme Based on Discrete Logarithms , IEEE Transactions on Information
Theory, IT-31,1985, pp.469-472. 13. Merkle R. C., Hellman M. E. Hiding
Information and Signatures inTrapdoor Knapsacks , IEEE Transactions on
Information Theory, IT-24, 1978, pp.525-530. 14. McEliece, A Public-Key
Cryptosystem Based on Algebraic Coding Theory , JPL DSN Progress Report 42-
44, 1978, pp.42-44. 15. Maurer U. M. Towards the Equivalence of
Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms ,
Proc. CRYPTO'89, LectureNotes in Computer Science, v.839, pp.271-281. 16.
den Boer B. Diffie-Hellman is as Strong as Discrete log for
CertainPrimes , Proc. CRYPTO'88, Lecture Notes in Computer Science, v.403,
1989, pp.530-539. 17. Maurer U. M., Wolf S. Diffie-Hellman
Oracles , Advances in Cryptology - CRYPTO'96, Lecture Notes in Computer
Science, v.1109, pp.268-282. 19.
Coppersmith D., Odlyzko A., Schroeppel R. Discrete Logarithms in
GF(p) , Algorithmica, v.1, 1986. 21. Weber D., An Implementation of the General Field Sieve
to Compute Discrete Logarithms mod p , Lect. Notes in Comput.Sci., n.921,
1995. 22. Нестеренко Ю. В. Алгоритмические проблемы теории
чисел , Математическое просвещение, третья серия, вып. 2, 1997. 23.
Сидельников В. М. Частные Ферма и логарифмирование в конечном простом
поле , Международные научные чтения по аналитической теории чисел
иприложениям, МГУ им. М. В. Ломоносова, 1997. 25. Chudnovsky D. V., Chudnovsky G. V.
Sequences of Numbers Generated byAddition in Formal Groups and New
Primality and Factorization Tests , Research report RC 11262 (#50739), IBM
Thomas J.Watson Res. Center, YorktownHeights, N.Y., 1985. 27. Lenstra A. K., Lenstra H. W., Manasse M. S., Pollard J. M.
The NumberField Sieve , 22-nd Annual ACM Symp. on Theory of Computing
(STOC), 1990. 28. Buhler D. J., Lenstra H. W., Pomerance C. Factoring
Integers with theNumber Field Sieve , Lect. Notes in Math, v. 1554,
1993. 30. Konyagin S. V.,
Pomerance C. On Prime Recognizable in DeterministicPolynomial Time ,
The Mathematics of Paul Erdos, 1995, Springer-Verlag 32. Семаев И. А. О сложности вычисления логарифмов на
эллиптическихкривых , Вторая международная конференция по теории чисел и ее
приложениям, Тула, 1993. 33. L.Adleman, A Subexponential Algorithm for
the Discrete Logarithm with Application to Cryptography , Proc. IEEE 20-th
Annual Symposium onFoundations of Computer Science (FOCS), 1979. 34. Frey
G., Ruck H.-G. A Remark Concerning m-Divisibility and DiscreteLogarithm in
the Divisor Class Group of Curves . 35. Shanks D. Class Number, a
Theory of factorization, and Genera ,Proc. Sympos. Pure Math., vol. 20,
Amer. Math. Soc., Providence, R.I., 1971. 36. Schoof R. J. Elliptic
Curves over Finite Fields and the Computationof Square Roots mod p , Math.
Comp., 44, 1985. 37. Lenstra, jr. H. W. Elliptic Curves and Number-
TheoreticAlgorithms , ICM86 (имеется перевод, - М.: Мир, 1986). 38.
Christof Paar, Pedro Soria-Rodriguez, Fast Arithmetic Architecturesfor
Public-Key Algorithms , EUROCRYPT' 97. 39. Shamir A. A Polynomial
Time Algorithm for Breaking the BasisMerkle-Hellman Cryptosystem , IEEE
Transactions on Information Theory, v.IT-30(5), September 1984, pp. 699-
704. 40. Brickell E. F. Breaking Iterated Knapsacks , in Advances
in Cryptology - CRYPTO'84, Springer-Verlag, 1985, pp.342-358. 41. Chor B.,
Rivest R.L., A Knapsack-Type Public-Key Cryptosystem Based on Arithmetic
in Finite Fields , IEEE Transactions on Information Theory,v.IT-34(5),
1988, pp. 901-909. 42. Schnorr C. P., Horner H. H. Attacking the Chor-
Rivest Cryptosystem byImproved Lattice Reduction , in Advances in
Cryptology - EUROCRYPT'95, Springer-Verlag, 1995, pp.1-12. 43. Березин Б. В.,
Дорошкевич П. В., Цифровая подпись на основе традиционной
криптографии , Защита информации . - Москва, 1992,№2, с.148-
167. 44. Bennett C.H., Bessette F., Brassard G., Savail L., Smolin J.,
Experimental Quantum Cryptography , Journal of Cryptology, 5(1),1992,
pp.3-28). 45. Беннет Чарльз Г., Брассар Жиль и др. Квантовая
криптография , Вмире науки (Scientific American), № 11-12, 1992, с. 130-
139. 46. Schneier Bruce, Applied Cryptography, Second
Edition (Protocols, Algorithms and Source Code in C), John Wiley &
Sons, Inc., 1996. 47. Скородумов Б. И. Программно-аппаратные комплексы
защиты отнесанкционированного доступа к информации , Центральный Банк
Российской Федерации, Государственный комитет Российской Федерации по высшему
образованию,Московский государственный инженерно-физический институт
(технический университет), Москва, 1996.