1.1 Популярный очерк

Криптография как искусство скрытой передачи информации существует уже тысячелетия. Люди уже давно поняли, что информация является большой ценностью, и поэтому много усилий затрачивалось как на ее охрану, так и на ее добывание. Вообще говоря, совершенно не обязательно это связано с какими-то "шпионскими" делами. Информация, которая нуждается в защите, возникает в самых разных жизненных ситуациях. Обычно в таких случаях говорят, что информация содержит тайну или является защищаемой, приватной, конфиденциальной, секретной. Для наиболее типичных, часто встречающихся ситуаций такого типа введены даже специальные понятия:

• государственная тайна;

• военная тайна;

• коммерческая тайна;

• юридическая тайна;

• врачебная тайна и т. д.

Далее мы будем говорить о защищаемой информации, имея в виду следующие признаки такой информации:

• имеется какой-то определенный круг законных пользователей, которые имеют право владеть этой информацией;

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

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

Основной объект криптографии можно представить в виде схемы, показанной на рис. 1. В этой схеме A и B -- удаленные законные пользователи защищаемой информации; они хотят обмениваться информацией по общедоступному каналу связи. П -- незаконный пользователь (противник), который может перехватывать передаваемые по каналу связи сообщения и пытаться извлечь из них интересующую его информацию. Приведенную формальную схему можно также считать моделью типичной ситуации, в которой применяются криптографические методы защиты информации.

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

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

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

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

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

Под ключом в криптографии понимают сменный элемент шифра, который применен для шифрования конкретного сообщения.

Зачем нужен ключ? Известно, что придумывание хорошего шифра -- дело трудоемкое. Поэтому желательно увеличить "время жизни" хорошего шифра и использовать его для шифрования как можно большего количества сообщений. Но при этом возникает опасность, что противник уже разгадал (вскрыл) шифр и читает защищаемую информацию. Если же в шифре есть сменный ключ, то, заменив ключ, можно сделать так, что разработанные противником методы уже не дают эффекта. Этот принцип особенно полезен и важен в тех случаях, когда применяются дорогостоящие шифрующие машины (шифрмашины) в больших сетях связи.

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

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

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

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

Из более специфических приведем еще три примера возможностей противника:

• противник может перехватывать все шифрованные сообщения, но не имеет соответствующих им открытых текстов;

• противник может перехватывать все шифрованные сообщения и добывать некоторые соответствующие им открытые тексты;

• противник имеет доступ к шифру (но не к ключам!) и поэтому может зашифровывать и дешифровывать любую информацию.

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

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

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

Прежде всего подчеркнем большое разнообразие видов защищаемой информации: документальная, телефонная, телевизионная, компьютерная и т.д. Каждый вид информации имеет свои специфические особенности, и эти особенности сильно влияют на выбор методов шифрования информации. Большое значение имеют объемы и требуемая скорость передачи шифрованной информации. Выбор вида шифра, его параметров и его стойкости существенно зависит от характера защищаемых секретов или тайны. Некоторые тайны (например, государственные, военные и др.) должны сохраняться десятилетиями, а некоторые (например, биржевые) -- уже через несколько часов можно разгласить. Необходимо учитывать также и возможности того противника, от которого защищается данная информация. Одно дело -- противостоять одиночке или даже банде уголовников, а другое дело -- мощной государственной структуре.

Из-за такого разнообразия требований приходится разрабатывать различные шифры, которые реализуются в сотнях типов шифрующих машин и устройств. Вместе с тем в наиболее развитых в криптографическом отношении странах существуют стандартные шифры: например, DES -- в США и СКЗД -- в России.

Теоретически существует абсолютно стойкий шифр, но единственным таким шифром является какая-нибудь форма так называемой ленты однократного использования, в которой открытый текст "объединяется" с полностью случайным ключом такой же длины. Этот результат был доказан К. Шенноном с помощью разработанного им теоретико-информационного метода исследования шифров. Мы не будем здесь останавливаться на этом подробно, а лишь обсудим особенности строения абсолютно стойкого шифра и возможности его практического использования. Для абсолютной стойкости существенным является каждое из следующих требований к ленте однократного использования:

• полная случайность (равновероятность) ключа (это, в частности, означает, что ключ нельзя вырабатывать с помощью какого-либо детерминированного устройства);

• равенство длины ключа и длины открытого текста;

• однократность использования ключа.

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

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

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

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

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

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

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

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

Существенные изменения в криптографии произошли после появления в 1976 г. работы молодых американских математиков У. Диффи и М. Э. Хеллмана "Новые направления в криптографии". Была предложена новая теоретическая система передачи защищаемой информации, причем выполнены два новых свойства:     1) для передачи сообщений не требуется предварительный обмен ключами по секретному каналу связи;

    2) стойкость шифра зависит от сложности решения трудной математической задачи инвертирования односторонней функции с секретом.

Односторонней называется функция , обладающая двумя свойствами:      а) существует полиномиальный алгоритм вычисления значений ;

     б) не существует полиномиального алгоритма инвертирования функции , т. е. решения уравнения относительно .

Другим понятием, более близким к традиционной криптографии, в которой есть секретный ключ, является понятие функции с секретом. Иногда еще употребляются термины функция с ловушкой, функция опускной двери (английское название: one-way trap-door function).

Функцией с секретом называется функция , зависящая от параметра и обладающая тремя свойствами:      а) существует полиномиальный алгоритм вычисления значений ;

     б) не существует полиномиального алгоритма инвертирования ;

     в) при известном существует полиномиальный алгоритм инвертирования .

Отметим, что односторонняя функция и функция с секретом существенно отличаются от функций, привычных со школьной скамьи, из-за ограничений на сложность их вычисления и инвертирования. Эти новые понятия в математике введены в 70-е годы. Но за истекшие 20 лет так и не удалось построить ни одного примера односторонней функции. Тем не менее активное изучение свойств этого, пока гипотетического, математического объекта позволило установить его связь с другими более изученными объектами. При этом удалось доказать, что в некотором смысле проблема существования односторонней функции эквивалентна одной из хорошо известных нерешенных проблем -- "совпадают ли классы сложностей P и NP"?

Говоря неформально, класс P состоит из задач с полиномиальной сложностью. Более строго, класс P -- это класс языков, распознаваемых за полиномиальное время на детерминированной машине Тьюринга. Если такую машину Тьюринга дополнить гипотетической способностью "угадывания", получается более сильная модель -- недетерминированная машина Тьюринга. Класс NP -- это класс языков, распознаваемых за полиномиальное время на недетерминированной машине Тьюринга. Проблема совпадения классов P и NP -- это проблема соотношения возможностей двух моделей вычислений: детерминированная и недетерминированная машина Тьюринга.

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

Применение функции с секретом в криптографии позволяет:     1) организовать обмен шифрованными сообщениями с использованием только открытых каналов связи, т. е. отказаться от секретных каналов связи для предварительного обмена ключами;

    2) включить в задачу вскрытия шифра в качестве подзадачи трудную математическую задачу и тем самым повысить обоснованность стойкости шифра;

    3) решать новые криптографические задачи, отличные от шифрования (цифровая подпись и др.)

Опишем идею Диффи и Хеллмана в общем виде. Пользователь A, который хочет получать шифрованные сообщения, должен сначала выбрать какую-нибудь функцию с секретом . Он сообщает всем заинтересованным (например, публикует) описание функции в качестве своего алгоритма шифрования. Но при этом значение секрета он никому не сообщает и держит в секрете. Если теперь пользователь B хочет послать А защищаемую информацию , то он вычисляет и посылает по открытому каналу к A. Поскольку A для своего секрета умеет инвертировать , то он вычисляет по полученному . Никто другой не знает и поэтому в силу свойства б) функции с секретом не сможет за полиномиальное время по известному шифрованному сообщению вычислить защищаемую информацию .

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

Ту же идею Диффи и Хеллман предложили использовать для цифровой подписи сообщений, которую невозможно подделать за полиномиальное время. Пусть пользователю A необходимо подписать сообщение . Он, зная секрет , находит такое , что , и посылает пользователю B в качестве своей цифровой подписи. Пользователь B хранит в качестве доказательства того, что A подписал сообщение . Это доказательство неопровержимо, поскольку никто другой в силу свойства б) функции с секретом не сможет за полиномиальное время по известному сообщению подделать цифровую подпись .

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

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

    3) при возникновении споров отказаться от подписи невозможно в силу ее неподделываемости;

    4) подписанные сообщения можно, не опасаясь ущерба, пересылать по любым каналам связи.

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

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

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

Приведем несколько примеров задач, решаемых удаленными абонентами.

1. Взаимодействуют два не доверяющих друг другу абонента. Они хотят подписать контракт. Это надо сделать так, чтобы не допустить следующую ситуацию: один из абонентов получил подпись другого, а сам не подписался.

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

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

Протокол решения этой задачи принято называть протоколом подбрасывания монеты.

3. Взаимодействуют два абонента A и B (типичный пример: A -- клиент банка, B -- банк). Абонент A хочет доказать абоненту B, что он именно A, а не противник.

Протокол решения этой задачи принято называть протоколом идентификации абонента.

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

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

Осмысление различных протоколов и методов их построения привело в 1985-1986 гг. к появлению двух плодотворных математических моделей -- интерактивной системы доказательства и доказательства с нулевым разглашением. Математические исследования этих новых объектов позволили доказать несколько утверждений, весьма полезных при разработке криптографических протоколов.

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

1) полнота -- если действительно истинно, то абонент почти наверняка убедит абонента признать это;

2) корректность -- если ложно, то абонент вряд ли убедит абонента , что истинно.

Здесь словами "почти наверняка" и "вряд ли" мы заменили точные математические формулировки, использующие понятие вероятности.

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

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

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

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

Условно можно выделить три принципиально разных этапа в развитии математического аппарата криптографии.

До 40-х годов XX века были только электромеханические шифрмашины, поэтому и спектр математических преобразований был ограничен: применялись в основном методы комбинаторного анализа и теории вероятностей.

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

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

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

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

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

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

Совершенствование аппаратных средств будет неумолимо продолжаться, что, казалось бы, "работает на противника" -- он сможет решить используемую теоретико-числовую задачу и найти ключ пользователя. Но, с другой стороны, совершенствование аппаратных средств позволяет пользователю выбирать ключ существенно большей длины без уменьшения скорости работы криптосистемы. Тем самым для противника задача определения ключа вновь станет непреодолимой. Итак, хотя совершенствование аппаратных средств и помогает противнику, оно в не меньшей мере помогает законному пользователю. Это правило не распространяется на ситуацию использования быстродействующих машин в будущем для вскрытия ключей, использовавшихся в прошлом; при таком сценарии преимущества от совершенствования аппаратных средств получает только противник. Это соображение заставляет выбирать длину ключа с учетом не только имеющихся в настоящее время оценок сложности теоретико-числовых задач, но и прогнозируемых изменений таких оценок. Оно также подтверждает необходимость замены ключей через каждые несколько лет на более длинные.

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

Хотя твердо считается, что рассматриваемые теоретико-числовые задачи являются сложными математическими проблемами, это не доказано. Таким образом, для них остаются в силе обе принципиальные возможности теоретических прорывов:

• получить нижнюю оценку сложности задачи и тем самым гарантировать определенную стойкость криптосистемы на ее основе;

• построить эффективный алгоритм решения задачи и тем самым доказать нестойкость криптосистемы на ее основе.