Перспективы развития и использования асимметричных алгоритмов в криптографии.
В статье, рассчитанной на специалистов (теоретиков и практиков) в области защиты информации, знакомых с проблематикой асимметричной криптографии, изложено нынешнее состояние проблемы и рассмотрены направления вероятного развития криптографии с открытым ключом в ближайшем будущем.
Введение
Краткая предыстория
Традиционно считается, что концепция асимметричной криптографии впервые была предложена в 1976 году Уитвелдом Диффи и Мартином Хеллманом на
национальной компьютерной конференции [1] и опубликована в том же году в основополагающей работе "Новые направления в криптографии" [2]. К
числу отцов-основателей асимметричной криптографии относят также и Ральфа Меркля, который независимо от Диффи и Хеллмана пришел к тем же конструкциям,
однако опубликовал свои результаты только в 1978 году [3].
На приоритет в открытии асимметричной криптографии претендует и Агентство
национальной безопасности США. В статье энциклопедии "Британника" директор АНБ Симмонс заявляет, что "двухключевая криптография была
известна в Агентстве за 10 лет до публикации Диффи и Хеллмана" [4].
Терминология
В настоящее время термином "асимметричная криптография" обозначают большую группу механизмов, алгоритмов, протоколов и идей,
применяемых при разработке систем защиты информации. Перечислим основные из них и кратко прокомментируем, что конкретно понимается под каждым термином
(систематический словарь терминов из области асимметричной криптографии приведен в работе [5]).
1) односторонняя функция (One-way function);
2) односторонняя функция с секретом (One-way trap-door function) - это
некоторая функция FK: X®Y, зависящая от параметра K (ее можно рассматривать также как параметризованное семейство функций) и обладающая следующими
свойствами: a) при любом значении параметра K существует полиномиальный алгоритм вычисления значения функции в любой точке FK(x) при условии, что
параметр K неизвестен;
б) при неизвестном значении параметра K не существует полиномиального алгоритма
инвертирования функции FK;
в) при известном значении параметра 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]).
Объективные потребности
Двигателем развития асимметричной криптографии, без сомнения, являются потребности практики. В связи с бурным развитием информационных систем
(в первую очередь здесь следует отметить поразительные успехи инженерной мысли в области развития аппаратных средств), расширением их инфраструктуры
практические потребности ставят новые задачи перед разработчиками криптографических алгоритмов. На сегодняшний день основные побудительные мотивы
развития асимметричной криптографии, на наш взгляд, можно сгруппировать следующим образом (приведенная ниже классификация отражает наиболее
существенные из них и не претендует на то, чтобы быть исчерпывающей):
- потребности развивающихся телекоммуникационных сетей самого разнообразного
применения, в том числе имеющих сложную топологию;
- потребности обеспечения информационной безопасности в глобальной сети
Internet;
- потребности банковских систем (в том числе использующих интеллектуальные карты);
- потребность мыслящего человечества в постижении мира.
Несмотря на снисходительную улыбку, вызываемую обычно последним побудительным
мотивом, нельзя не учитывать, что на сегодняшний день проблемы асимметричной криптографии превратились в самодостаточную область исследований. Вопросы
построения криптографических протоколов, доказательств с нулевым разглашением, теоретико-числовые аспекты асимметричной криптографии постоянно входят в число
обсуждаемых проблем на ряде авторитетных ежегодных научных конференций, из которых наиболее высоким рейтингом обладают STOC (ACM Symposium on Theory of
Computing) и FOCS (IEEE Annual Symposium on Foundations of Computer Science). В последнее время к ним по уровню приближаются криптографические конференции
EUROCRYPT, ASIACRYPT и CRYPTO. Многие авторитетные ученые начинают включать в круг своих интересов и вопросы криптографии. Все эти факты необходимо учитывать
при разработке проблем, лежащих на стыке политики и криптографии.
Следует отметить и имеющую место, в определенном смысле, негативную тенденцию.
Иногда алгоритмы асимметричной криптографии пытаются использовать там, где они по существу не нужны. Например, порой авторы не делают различия между понятиями
имитоприставки и цифровой подписи.
Перспективы теоретических исследований асимметричных алгоритмов
Общеметодологические проблемы криптографии
Осмысление конструкций асимметричной криптографии привело исследователей к постановке проблем, имеющих отношение к криптографии в целом: получение необходимых и достаточных условий существования функций с секретом, односторонних функций, пар подстановок с трудно обнаружимыми "зубьями". Решение любой из упомянутых проблем, кроме продвижения в философском понимании вопроса, без сомнения, даст интересные и для практических приложений конструкции.
Теоретические исследования известных алгоритмов
Перечень наиболее распространенных асимметричных криптоалгоритмов
Прежде всего назовем наиболее распространенные (наиболее часто обсуждаемые) алгоритмы асимметричной криптографии:
1. Схема Диффи-Хеллмана в мультипликативной группе конечного поля (статья 1976 года) и в группе точек эллиптической кривой над конечным полем Нила Коблица
[9].
2. Схема открытого шифрования RSA и построенные на ее основе схемы подписи и аутентификации
[10].
3. Схемы типа Фиата-Шамира [11].
4. Семейство схем подписи типа Эль-Гамаля [12].
5. Схемы на основе задачи "о рюкзаке" [13].
6. Теоретико-кодовые конструкции МакЭлиса [14].
Названные схемы достаточно известны, поэтому формально описывать их не будем (тем более что их описанию посвящены отдельные публикации). Со всеми
перечисленными схемами связан ряд теоретических проблем. Ниже мы приведем основные из них и укажем последние опубликованные достижения по каждой.
Теоретико-сложностные проблемы:
1. Проблема эквивалентности задачи Диффи-Хеллмана и задачи логарифмирования в соответствующей группе.
Практически очевидно, что задача Диффи-Хеллмана не сложнее задачи логарифмирования (если мы умеем логарифмировать, то система открытого
распределения ключей Диффи-Хеллмана нестойкая). Хотя большинство исследователей склоняется к мнению, что эти задачи эквивалентны, вопрос о том, верно ли
обратное, на сегодняшний день открыт. Эквивалентность, при некоторых дополнительных условиях, доказали Маурэр [15] и ден Бур [16]. Из отечественных
исследователей сильный результат по данной проблематике получен М. А. Черепневым, которому удалось построить субэкспоненциальный алгоритм сведения
задачи дискретного логарифмирования в простом конечном поле к задаче Диффи-Хеллмана. Наиболее же близки к решению проблемы швейцарские ученые [17].
2. Проблема эквивалентности задачи компрометации схемы Эль-Гамаля и задачи логарифмирования.
3. Проблема эквивалентности задачи вскрытия системы RSA и задачи факторизации целых чисел (под секретным ключом понимается экспонента e).
Задача определения секретного ключа здесь эквивалентна факторизации, тем не менее, вопрос об эквивалентности бесключевого чтения и факторизации открыт. В
то же время известны частные случаи, когда задача решается легко (случай, так называемых, "слабых ключей").
4. Проблема построения стойких (доказуемо) криптографических протоколов в предположении о существовании тех или иных криптографических примитивов.
Основная масса публикаций по теоретико-сложностным проблемам криптографии относится именно к этой тематике.
Теоретико-числовые проблемы
Далее, приводя субэкспоненциальные асимптотические оценки сложности алгоритмов, будем традиционно пользоваться следующим обозначением:
.
Следует отметить, что многие из асимптотических оценок носят эвристический
характер, часть из которых доказана в предположении истинности гипотезы (расширенной) Римана. Ряд исследователей проводят работы по строгому
доказательству этих эвристических оценок.
По-прежнему актуальной остается задача получения не асимптотических, а точных
оценок трудоемкости для ряда разработанных алгоритмов.
1. Задача вычисления дискретного логарифма в мультипликативной группе конечного поля
Практически сразу после опубликования работы У. Диффи и М. Хеллмана Дж. Поллард публикует вероятностные алгоритмы решения задачи
дискретного логарифмирования, имеющие корневую оценку сложности и не требующие большого объема памяти [18]. Этот метод называют r-методом Полларда (вариация
метода - l-метод Полларда, общая идея известна также под названием "baby step, giant step").
В дальнейшем основные идеи построения эффективных алгоритмов для решения задачи дискретного логарифмирования были связаны с, так называемым, методом решета.
Долгое время асимптотически наиболее эффективным (асимптотическая оценка сложности -
, оставался метод Д. Копперсмита, А. Одлыжко, Р. Шрёппеля [19]. Метод был реализован и
применен для логарифмирования в простых полях при p длиной до 67 десятичных знаков.
Последним существенным достижением в этой области является метод решета
числового поля Д. Гордона [20]. Асимптотически метод более эффективен, чем все предыдущие: оценка его трудоемкости
. Однако его практическая реализация сложнее: пока имеется сообщение, что этим методом
удалось решить задачу дискретного логарифмирования в простом поле при p длиной 40 десятичных знаков. Для этого специалистам немецкого университета Universitat
des Saarlandes в Саарбрюккене потребовались 21 час работы рабочей станции Sparc и 40 минут работы суперкомпьютера Cray [21]. По последним данным 1997 года
немецким исследователям удалось реализовать процедуру логарифмирования для чисел длиной 85 десятичных знаков.
За каждым из названных методов стоит целый спектр их модификаций и вариантов. Из отечественных исследователей, работающих в этом направлении необходимо
назвать О. Н. Василенко и И. А. Семаева. В тезисах выступлений последнего на конференциях по теории чисел и ее приложениям (Тула, Воронеж) содержатся весьма
интересные новые идеи в развитие метода решета.
Исследователи постоянно предпринимают попытки поиска принципиально иных
подходов (отличных от идей метода решета) к задаче дискретного логарифмирования. Из опубликованного здесь следует упомянуть работы, связанные
с попыткой использования частных Ферма [22], [23], однако, пока успешное логарифмирование этим методом требует большего объема информации, чем
"классическая" постановка задачи.
Также следует упомянуть о том, что с середины 1997 года в научной среде
циркулируют слухи о том, что российскому ученому С. А. Степанову удалось построить полиномиальный алгоритм дискретного логарифмирования. Однако, вплоть
до сегодняшнего дня убедительные подтверждения этому факту отсутствуют, впрочем, как и убедительные опровержения.
2. Задача разложения целых чисел на множители
По сравнению с задачей дискретного логарифмирования задача факторизации чисел или разложения их на множители имеет более длительную
историю, ведомую обычно с античных времен от Эратосфена (предположительно 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