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

Еще в 1998 году ISO, в 1999-м ANSI, а в 2000 году IEEE и NIST приняли новый стандарт для цифровой подписи ECDSA (Elliptic Curve Didital Signature Algorithm), основанный на использовании эллиптических кривых. С принятием алгоритма Национальным институтом стандартов США он получил статус федерального стандарта. Не будем рассматривать политические и экономические причины, а тем более последствия этих событий: многое еще неясно. Разберем математические основы, необходимых каждому заинтересованному читателю для того, чтобы для него понятия «эллиптическая кривая» или «сложность дискретного логарифмирования».

Сразу договоримся о терминологии. В отечественной литературе прижились три термина для определения одного понятия: электронная подпись; электронно-цифровая подпись (ЭЦП); цифровая подпись. Последний вариант является прямым переводом английского словосочетания digital signature. Термин «цифровая подпись» более удобен и точен.

Общеизвестно, что цифровая подпись файлов или электронных почтовых сообщений выполняется с использованием криптографических алгоритмов, использующих несимметричные ключи: собственно для подписи используется «секретный ключ», а для проверки чужой подписи – «открытый». Ключи представляют собой числа достаточно большой длины (от 512 до 4096 бит), математически связанные между собой.

Цифровая подпись сообщения (файлы, электронные письма, сетевые пакеты и прочие наборы данных) – это последовательность бит фиксированной длины, формирующаяся по тексту сообщения с использованием секретного ключа его создателя. Корректность подписи проверяется с помощью открытого ключа. Обычно вместе с сообщением подписываются и некоторые его «реквизиты»: дата и время создания сообщения, (возможно) номер версии сообщения, время «жизни» сообщения. Можно придумать и другие «критичные для приложений» параметры сообщения. Цифровая подпись отправляется вместе с сообщением, и, обычно, становится неотюемлемой его частью. Получатель сообщения должен располагать копией открытого ключа отправителя. Схемы распространения открытых ключей могут быть разными: от простого личного обмена ключами до сложной многоуровневой «инфраструктуры открытых ключей» (public key infrastructure – PKI). Если при проверке цифровой подписи получатель устанавливает ее корректность, то может быть уверен не только в неизменности и «актуальности» сообщения, но – что самое важное – и в том, что сообщение «подписал» действительно его автор или отправитель. Сообщение может нести на себе несколько подписей, служащих для разных целей. При этом каждая следующая подпись «накладывается» на сообщение вместе со всеми предыдущими подписями. Скажем, в некоторых системах «клиент-банк» платежное поручение подписывается «автором» (бухгалтером, клиентом или другим лицом, уполномоченным провести платеж) и «отправителем» (операционистом, дежурным оператором или другим лицом, выполняющим техническую работу по пересылке).

Подписанное сообщение может и не иметь конкретного получателя. Возможно, например, разместить на корпоративном Web-сервере подписанный документ, а открытый ключ подписи разместить в публичном репозитарии. Каждый посетитель сайта может, проверив подпись под ним, убедиться в его подлинности.

Немного математики

Из школьного курса алгебры известно понятие «сравнения по модулю». Говорят, что целое положительное число a сравнимо с b по модулю p , если остаток от деления b на p равен a. Дальше начинается алгебра высшая.

Можно ввести операции сложения и умножения «по модулю p». А именно, результатом сложения двух чисел по модулю p будем считать остаток от деления их суммы на число p. Аналогичным образом определим и произведение. Нетрудно заметить, что результаты операций сложения или умножения пары произвольных неотрицательных целых чисел по модулю p не будут превосходить число p. В результате, можно ограничится рассмотрением множества чисел 0,1... pб-1 с заданными на нем операциями сложения и умножения по модулю p. Множество 0,1...p-1 с заданными операциями сложения и умножения, подчиняющимися обычным школьным законам сложения, умножения и раскрытия скобок, образуют «кольцо классов вычетов по модулю p» [1].

Далее, можно определить «обратный элемент». Элемент b называется обратным к элементу a, если ab=1. Скажем, обратным элементом числа 3 в кольце по модулю 5 будет число 2 (3*2 = 6, 6 mod 5 = 1). Обратный элемент обозначается a-1. Оперируя только целыми неотрицательными числами, нетрудно ввести операцию деления как умножение на обратный элемент, операцию вычитания и даже «отрицательные» числа. Оказывается, если p – простое число, то обратный элемент существует для всех элементов кольца (кроме, естественно, числа 0). Кольцо классов вычетов, для каждого элемента которого (кроме 0) существует обратный элемент, называют «простым полем» (или «конечным полем», «полем Галуа») и обозначается GF(p).

Закономерен вопрос: а зачем это все? Как эти абстрактные алгебраические определения помогут разобраться с цифровой подписью? Дело в том, что в алгоритмах цифровой подписи активно используются вычисления в конечных полях. На идее «модульной» арифметики и строится «сложность» восстановления секретного ключа по открытому ключу.

Алгоритмы цифровой подписи.

Схема Эль-Гамаля

На сегодняшний день придумано и реализовано не так много алгоритмов цифровой подписи:

  • алгоритм подписи Ривеста-Шамира-Адельмана (RSA);
  • алгоритм Шнорра;
  • алгоритм DSA, являющийся федеральным стандартом на цифровую подпись в США;
  • алгоритм Эль-Гамаля, на котором построен "старый" российский стандарт на цифровую подпись ГОСТ Р 34.10-94.

Про RSA и DSA написано много, а алгоритм Шнорра очень похож на DSA, но был предложен раньше [3]. Схема же Эль-Гамаля заслуживает не только упоминания, но и описания. Действительно, было бы интересно для сравнения иметь перед глазами оба российских стандарта на цифровую подпись. Кроме того, из описания алгоритма становится ясна «анатомия» цифровой подписи.

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

Оригинальный алгоритм Эль-Гамаля не фиксирует алгоритм используемой хэш-функции (в «старом» российском стандарте зафиксирован алгоритм хэширования ГОСТ 34.11-94.) Опишем ключевые идеи этого алгоритма.

Выбираем рабочее поле; рекомендуется выбрать поле порядка p = 2512. Выбираем секретный ключ x длиной 256 бит. Открытым ключом подписи будем считать пару чисел a и Y, где

Y = ax (mod p),1 < a < p-1

Число а выбирают неким специальным образом (кстати, эта процедура является одним из самых «мутных» мест в стандарте) и накладывают на него дополнительные ограничения. Далее, вычисляют хэш-функцию от сообщения, которое хотят подписать, и представлют значение хэш-суммы в виде числа (обозначим его h). Цифровой подписью сообщения будем считать пару чисел (r, s), удовлетворяющих уравнению:

ah = Yr rs (mod p)

Числа a и p не являются параметрами алгоритма и должны быть известны всем участникам обмена. Они не секретны; обычно криптографические программы содержат эти числа внутри себя. При организации центров сертификации, параметры генерации открытого ключа могут выдаваться в центре вместе с рекомендованным программным обеспечением или быть частью открытого ключа центра сертификации.

Что значит «сложно»

Под стойкостью криптографического алгоритма обычно понимают число («гипотетических», «элементарных») операций, которые следует выполнить для вычисления секретного ключа по открытому ключу или, если исследуется симметричный алгоритм шифрования, для расшифровки сообщения без знания ключа. От числа и характера «элементарных» операций напрямую зависит время, необходимое для их выполнения. Например, «элементарной операцией» в задаче дешифрования текста путем полного перебора ключей можно считать процедуру расшифрования текста одним ключом. Тогда сложность всего дешифрования оценивается как 2(длина ключа), что соответствует «классической» оценке сложности полного перебора. Итак, в схеме Эль-Гамаля секретным ключом является случайное число x, а открытым – пара (g, Y), где

Y = gx (mod p)

Поиск числа х по известным Y, g и p называют дискретным логарифмированием. «Логарифмирование» – потому, что надо найти показатель степени, а «дискретное» – потому, что задача решается в целых числах (более того, в простом поле).

После опубликования работ Диффи, Хеллмана, Эль-Гамаля и других исследователей, задача дискретного логарифмирования оказалась в центре внимания многих математиков и криптоаналитиков. Стойкость подписи напрямую зависит от эффективности нахождения дискретного логарифма. Попробуем пояснить, не приводя математических выкладок, что же, собственно, надо сделать. На рис. 1 «изображено» конечное поле. Его элементы поля размещены по «окружности», что, собственно, отражает структуру поля. Где-то на «окружности» размещается точка а и точка Y с координатами ax. Где-то расположено и неизвестное нам число x.

Рис. 1. Конечное поле

Можно показать, что задача дискретного логарифмирования эквивалентна задаче поиска «числа оборотов» при обходе по окружности в «пути» от точки a к точке Y. Нетрудно догадаться, что «великий поход» по окружности эквивалентен полному перебору ключей. Существуют методы, оптимизирующие перебор (в частности, метод Полларда или метод «прыгающего кенгуру»). Есть еще несколько сходных методов, но все они имеют эвристический характер и вероятностную оценку сложности: при длине ключа в 512 бит сложность дискретного логарифмирования будет порядка 2256.

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

Оригинальный метод отображений применим для любого числового поля GF(pn). ГОСТ 34.11-94 предполагает использование p порядка 2512, тогда сложность задачи дискретного логарифмирования имеет порядок 2180.

Утверждается, что алгоритм Копперсмита эффективен в полях GF(2k), где k < 520.

Эллиптические кривые и новый стандарт на электронную подпись

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

«Эллиптической кривой» называют множество пар точек (X,Y), удовлетворяющих уравнению:

y2 = ax3 + bx + c

Можно наложить ограничения на множество значений переменных х, y, и коэффициентов a, b, c. Ограничивая область определения уравнения значимым для приложений числовым множеством (полем) мы получим эллиптическую кривую, заданную над рассматриваемым полем. На рис. 2 изображен общий вид эллиптической кривой, определенной на множестве действительных чисел.

Рис. 2. Общий вид эллиптической кривой

В приложении к криптографии (и в новом стандарте на цифровую подпись) эллиптическая кривая над конечным простым полем GF(p) определяется как множество пар (x,y), таких что x,y Б?? GF(p), удовлетворяющих уравнению:

y2 = x3 +ax +b (mod p), a, b Б?? GF(p)

Пары (x,y) будем называть «точкой». Точки эллиптической кривой можно «складывать». «Сумма» двух точек, в свою очередь, тоже «лежит» на эллиптической кривой.

Кроме точек, лежащих на эллиптической кривой, рассматривается также «нулевая точка». Считается, что сумма двух точек A с координатами (XA, YA) и B с координатами (XB,YB) равна O, если XA = XB, YA = б-YB (mod p). Нулевая точка не лежит на эллиптической кривой, но, тем не менее, участвует в вычислениях; ее можно рассматривать как бесконечно удаленную от кривой.

Множество точек эллиптической кривой вместе с нулевой точкой и с введенной операцией сложения будем называть «группой». Для каждой эллиптической кривой число точек в группе конечно, но достаточно велико. Оценка порядка (числа элементов) группы точек эллиптической кривой m такова:

где р – порядок поля, над которым определена кривая. Если в схеме Эль-Гамаля рекомендуется использовать число р порядка 2512, то в случае эллиптической кривой достаточно взять p > 2255.

Важную роль в алгоритмах подписи с использованием эллиптических кривых играют «кратные» точки. Точка Q называется точкой кратности k, если для некоторой точки P k раз выполнено равенство:

P = Q + Q + Q + . + Q = kQ

Если для некоторой точки P существует такое число k, что kP = 0, это число называют порядком точки P.

Кратные точки эллиптической кривой являются аналогом степеней чисел в простом поле. Задача вычисления кратности точки эквивалентна задаче вычисления дискретного логарифма. Собственно, на сложности вычисления «кратности» точки эллиптической кривой и основана надежность цифровой подписи. Хотя эквивалентность задачи дискретного логарифмирования и задачи вычисления кратности и доказана, вторая имеет большую сложность. Именно поэтому при построении алгоритмов подписи в группе точек эллиптической кривой оказалось возможным обойтись более короткими ключами по сравнению с простым полем при обеспечении большей стойкости.

Секретным ключом, как и раньше, положим некоторое случайное число x. Открытым ключом будем считать координаты точки на эллиптической кривой P, определяемую как P = xQ, где Q – специальным образом выбранная точка эллиптической кривой («базовая точка»). Координаты точки Q вместе с коэффициентами уравнения, задающего кривую, являются параметрами схемы подписи и должны быть известны всем участникам обмена сообщениями.

Выбор точки Q зависит от используемых алгоритмов и весьма непрост. Так, стандарт ГОСТ 34.10-2001 определяет, что точка Q должна иметь порядок q, где q – простое число с «хорошими алгебраическими свойствами». Число q довольно велико (2254 < q < 2256). При построении конкретного алгоритма, реализующего вычисление цифровой подписи, американский стандарт предполагает использование алгоритма DSA. Новый российский стандарт использует модифицированную версию старого ГОСТ Р 34.10-94. Оказалось, оба они хорошо подходят для реализации в группе точек эллиптической кривой без особых модификаций. Некоторые специалисты отмечают даже, что описание алгоритма цифровой подписи Эль-Гамаля на эллиптической кривой «проще и естественней».

Для полного описания алгоритмов ECDSA и ГОСТ Р 34.10-2001 потребовалось расширить статью как минимум втрое, предположив, что читатель обладает приличной подготовкой в области высшей алгебры. Заинтересованного читателя отошлем к библиографии. Алгоритмам и методам «эллиптической» криптографии посвящено замечательное пособие [2], а систематическое изложение основ алгебры можно найти в [1]. Полезно (а иногда и необходимо) обратиться к тексту стандартов.

Заключение

Остается ответить на вопрос: зачем нужны эллиптические кривые? Помимо нетехнических причин, для принятия стандарта 34.10-2001 есть и причины, связанные с развитием вычислительной техники и криптоанализа.

Криптоанализ цифровой подписи весьма специфичен. Если при анализе классических блочных шифров используются в основном статистические методы, то анализ цифровой подписи основан на решении двух «сложных» задач: разложении «большого» составного числа на простые сомножители и дискретное логарифмирование. Первой задачей математики занимались издревле: Эратосфен, Евклид, Эйлер, Гаусс, Риман... Но несмотря на «солидный» возраст до появления алгоритма RSA и работы Диффи и Хеллмана, задача разложения на множители и поиск «формулы простого числа» оставались, как и вся математика, игрой ума. Задача дискретного логарифмирования обрела практический смысл сразу после того, как Диффи и Хеллман предложили в 70-х годах идею несимметричной криптографии. Установлено, например, что, научившись эффективно решать задачу разложения на множители, можно намного ускорить решение задачи логарифмирования. При этом задача дискретного логарифмирования остается «вычислительно сложнее» задачи разложения.

На сегодняшний день вычислительная техника позволяет за приемлемое время логарифмировать в полях порядка GF(2100). Подпись длиной в 160-200 бит на ближайшие несколько лет может считаться надежной. Логарифмирование в числовых полях порядка GF(2512) пока еще за разумное время не выполнимо. Но что будет завтра? Если верить закону Мура, то через 10б-15 лет окажутся доступными компьютеры, способные решать задачу «массового логарифмирования « в полях порядка GF(21024), т.е. решать задачу не вычисления одного, «конкретного» логарифма, но задачу эффективного вычисления x как «функции» от Y, g и p. Что же делать? Уже сейчас увеличивать длину ключа? Увеличение длины ключа (и «размерности» поля) приведет к заметному замедлению вычислений и прочим накладным расходам, связанным с хранением и пересылкой ключей.

Казалось бы, при резком падении стоимости оперативной памяти и удешевлении и увеличении пропускной способности каналов связи, зачем стараться сохранить короткие ключи? Это связано, в первую очередь, с массовым распространением мобильных устройств и Internet-технологий, с использованием смарт-карт и аутентификационных токенов. Память смарт-карты или SIM-карты является ресурсом дефицитным, к тому же, переход на выпуск смарт-карт с увеличенной памятью, приведет к потере совместимости с ранее выпущенными устройствами. Видимо, подобными технологическими соображениями и руководствовались американские специалисты, когда в 1999 году принимали вариант алгоритма DSA с использованием эллиптических кривых в качестве стандарта ANSI X9.62 ECDSA. В 2000 году алгоритм ECDSA был принят в качестве федерального стандарта и стандарта IEEE. А началось все годом ранее, в 1998 году, когда алгоритм ECDSA был принят в качестве стандарта ISO. России тоже пришлось спешить вслед за модой. Для детального знакомства с ECDSA и ГОСТ 34.10-2001 можно рекомендовать работы [4-10].

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

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

Литература
  1. Б.Л. ван дер Варден, "Алгебра", издание второе. М.: Наука, 1979
  2. А.А. Болотов, С.Б. Гашков, А.Б. Фролов, А.А. Часовских, "Алгоритмические основы эллиптической криптографии". Учебное пособие. М.: Изд-во МЭИ. 2000
  3. Bruce Schneier, "Applied Cryptography, Second edition: Protocols, Algorithms, and Source Code in C". John Wiley & Sons, 1996
  4. V.S. Miller, Use of elliptic curves in cryptography. Труды конференции Crypto'85. "Advances in Cryptology 1981-1997", Electronic Proceedings of the Crypto and Eurocrypt Conferences 1981-1997. Lecture Notes in Computer Science, Vol 1440. Springer.
  5. Taher ElGamal, "A public key cryptosystem and a signature scheme based on discrete logarithms". Труды конференции Crypto'84, Там же
  6. L.M. Adleman, J. DeMarrais, "A subexponential algorithm for discrete logarithms over all finite fields". Труды конференции Crypto'93, Там же
  7. A.M. Odlyzko, "Discrete logarithm in finite fields and their cryptographic significance". Труды конференции EuroCrypt'84, Там же
  8. Анохин М.И., Варновский Н.П., Сидельников В.М., Ященко В.В. "Криптография в банковском деле". М. Изд-во МИФИ, 1997
  9. D. Jonson, A. Menezes, S. Wanstone, "The Elliptic Curve Digital Signature Algirithm". Certicom Research, Canada. http://www.certicom.com/pdfs/whitepapers/ecdsa.pdf
  10. Elliptic Curve Cryptosystem. Remarks on the security of the elliptic curve cryptosystem. Certicom whitepaper. http://www.certicom.com/resources/download/EccWhite3.pdf

Глеб Семенов (semenov@jet.msk.su) – специалист по безопасности компании Jet Infosystems.

Алгоритмы шифрования

Криптография – дисциплина, изучающая математические методы сокрытия информации от посторонних наблюдателей, проверки целостности данных и аутентификации пользователей информационных систем. Различают два типа криптографических алгоритмов: симметричные и асимметричные. В первом случае оба абонента участвующих в процессе передачи информации используют одинаковые ключи, а во втором – разные, «секретный» и «открытый». Для сохранения конфиденциальности информации используются, как правило, симметричные алгоритмы, а для аутентификации и сохранения целостности персональных данных – асимметричные. Современная криптография – соревнование методов шифрования и криптоанализа, т.е. анализа и раскрытия шифров.

Симметричные алгоритмы

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

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

Криптоанализ

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

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

Криптоанализу, как и криптографии, уже несколько столетий. Наиболее простые алгоритмы – статистический и аналитический – давно известны. Статистический криптоанализ использует статистические методы для получения дополнительной информации о ключе, а аналитический – занимается математическим изучением алгоритма шифрования. Каждый новый метод криптоанализа добавляет новые требования к алгоритмам шифрования. Так, статистический метод, в котором по распределению символов в шифротексте выдвигаются гипотезы о ключе шифрования, породил требование равномерного распределения символов в шифротексте.

В число современных методов криптоанализа блочных шифров входят разностные (дифференциальные) алгоритмы. Первоначально они применялись для DES, но в силу своей универсальности стали использоваться и для других блочных шифров. Суть разностного анализа в следующем. Берутся два варианта открытого текста, отличающиеся, скажем, только в одном разряде, и анализируется разность зашифрованных текстов. Оказалось, что в DES и некоторых других алгоритмах распределение разностей соответствующих шифротекстов было не равномерным: определенные разности встречались чаще других. Если этот прием использовать для алгоритма DES с 15 циклами шифрования (для DES полное шифрование предусматривает 16 циклов), то, считая известными разности шифротекстов по 15 циклам, по известным шифротекстам после 16 циклов можно сделать определенные предположения о ключе, который использовался на последней, шестнадцатой итерации. Чаще всего выводы о ключе последней итерации будут неверными, но в большом массиве вариантов истинный цикловой ключ встречается чуть чаще, чем все остальные, что позволяет его выделить. Таким способом удается установить 48 разрядов из 56 разрядов ключа, используемого на последнем цикле, после чего определение остальных 8 разрядов не составит проблемы.

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

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

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

Шифрование

Базовый прием симметричного шифрования – перемешивание данных максимально сложным способом, чтобы криптоаналитик не смог ничего предположить о параметрах «замеса», т. е. о ключе шифрования. Дополнительные условия: увеличение скорости шифрования и уменьшение обюема кода программы, реализующей криптографический алгоритм. Шифровать данные можно, например, одним большим и сложным преобразованием, для которого, как правило, тяжело создать быструю и компактную реализацию. Подобные алгоритмы обычно вначале разрабатывали, а лишь потом думали об их программировании. Часто реализация оказывалась довольно неэффективной.

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

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

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

Асимметричные криптоалгоритмы

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

Криптоанализ

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

Базовые понятия теории сложности

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

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

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

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

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

Шифрование

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

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

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

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

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

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

При подготовке статьи были использованы материалы конференции «РусКрипто 2002», а также консультации Алексея Жукова, директора ассоциации «РусКрипто» и профессора кафедры информационной безопасности Бауманского государственного технического университета.

- Валерий Коржов