Краткий обзор асимметричных алгоритмов шифрования

Большинство современных асимметричных алгоритмов базируется на сложности решения следующих математических задач:

• Задача факторизации (разложения на множители) большого числа: умножение двух больших чисел является полиномиальной от размеров сомножителей по сложности задачей. При этом обратная задача — разложения на сомножители — является чрезвычайно трудоемкой, так, для разложения на множители числа длиной 200 цифр требуется не менее 1024 арифметических операций, что с вычислительной точки зрения является нереализуемой задачей. На сложности решения задачи факторизации основан алгоритм RSA.
• Задача нахождения дискретного логарифма. С точки зрения вычислительной сложности достаточно легко выполнить операцию возведения в степень в конечном поле, но для решения обратной задачи — поиска дискретного логарифма — потребуется практически полный перебор элементов поля; на сложности решения задачи логарифмирования основаны алгоритмы DSA, EGSA, Diffie-Hellman.
• Сложность декодирования в некоторых кодах, исправляющих ошибки, велика: достаточно легко получить кодовое слово (перемножить матрицы), но по кодовому слову найти базовое — задача вычислительно трудная. Этот метод редко используется на практике (известна криптосистема МсЕНесе, использующая коды Гоппа).

Первой и наиболее известной в мире системой цифровой подписи стала система RSA, математическая схема которой была разработана в 1977 г. в Массачусетском технологическом институте (США) и запатентована в США в 1982 г. Она называется так по первым буквам фамилий авторов: R. Rivest, A. Shamir, L. Adleman.

В самых общих чертах система RSA состоит в следующем. Пусть р и q — два различных больших случайно выбранных простых числа (имеющих обычно не менее 100 разрядов в своем десятичном представлении).

Обозначим

Случайно выберем большое целое d, взаимно простое с ф(п), и определим 1<е<ф(п), удовлетворяющее сравнению:

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

Числа n, e и d называются, соответственно, модулем, экспонентой зашифрования и экспонентой расшифрования. Числа п и е образуют открытый ключ, тогда как оставшиеся числа р, q, ф(п) и d являются секретными. На практике следует оставить в качестве секретного ключа только экспоненту расшифрования d, а числа р, q, ф(п) могут быть уничтожены.

Процедура шифрования в схеме RSA определяется равенством

а процедура расшифрования — равенством

, что и доказывает равенство E(D(Y))=Y.

Для определения двух больших простых чисел р и q произвольно выбирается нечетное целое число г подходящего размера (скажем, 100-разрядное) и проверяется на простоту с помощью тестов Соловея-Штрассена. В случае если г не проходит тест на простоту, процедуре проверки подвергается число г+2 и т. д.

По теореме Чебышева о функции распределения числа простых чисел

100-разрядных простых чисел (здесь In означает натуральный логарифм). Если это число сравнить с числом

всех 100-разрядных нечетных чисел, видно, что вероятность успеха для конкретного теста приблизительно равна 0,00868. Как следует из определения схемы RSA, секретное и обратное преобразования являются коммутативными, что означает, что алгоритм RSA может использоваться для шифрования информации. Это свойство является чрезвычайно важным и широко используемым на практике.

Операцией, необходимой для зашифрования и расшифрования, является возведение в степень a^r (mod n). Для ее реализации на практике используется метод последовательного возведения в квадрат (а², а⁴, а⁸,…). Если k=[log2r]+1, то можно показать, что для получения а^r (mod n) методом последовательного возведения в квадрат потребуется не более 2*к+1 произведений.

Обычно на практике экспонента расшифрования выбирается небольшой по размеру (иногда экспонента расшифрования одна и та же для целых групп пользователей). Это делает процедуру шифрования быстрее процедуры расшифрования, а процедуру верификации подписи быстрее процедуры подписывания. Алгоритмически процедуры с открытым ключом требуют О(К²) операций, с закрытым ключом — О(К³) операций, а процедура генерации ключей — О(К⁴) операций, где К — число битов в двоичном представлении модуля n.

Известны аппаратно-программные реализации алгоритма RSA, имеющие производительность более 600 Кбит/с при n=512 бит. Существуют два подхода к вскрытию алгоритма RSA. Первый состоит в попытке разложения п на простые множители (задача факторизации). Старейший и самый медленный метод разложения, решето Эратосфена, гарантирует решение задачи за n^0,5 проверок. Асимптотически самые быстрые алгоритмы факторизации требуют времени работы порядка для произвольно малого ε.

Другой метод вскрытия RSA состоит в нахождении е-го корня по модулю n.

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

Сегодня криптосистемы RS А с модулем 384 бита считаются легко вскрываемыми, с модулем 512 битов — вскрываемыми правительственными службами, 784 бита — достаточно надежными, 1024 бита — надежными на ближайшие десятилетия.

В последние годы специалистам по компьютерной теории чисел с помощью весьма изощренных методов и мощных вычислительных систем (использовались самые быстрые суперкомпьютеры типа CRAY-3 или распределенные сети из нескольких сотен VAX-станций) удается иногда разлагать на множители целые числа из 150 десятичных знаков.

Алгоритм RSA де-факто является международным стандартом ЭЦП. Однако при рассмотрении вопроса о возможности практического использования метода RSA существуют следующие аргументы против:

• метод RSA защищен патентом США, и для его использования в коммерческих продуктах необходимо лицензионное соглашение с держателем патента — корпорацией RSA Data Security (США);
• для обеспечения стойкости подписи на уровне 1018 необходимо использовать целые числа длиной не менее 360 битов (или 108 десятичных знаков) каждое, что требует достаточно больших вычислительных затрат;
• при вычислении ключей в системе RSA необходимо проверять большое количество условий, невыполнение каждого из которых допускает возможность фальсификации подписи;
• метод RSA позволяет без знания секретных ключей легко получать подписи под определенными новыми документами.

Другой распространенный асимметричный алгоритм шифрования EGS А был разработан в 1984 г. американцем Т. Эль-Гамалем. Этот алгоритм не защищен патентом, что стало одним из доводов, использованных в августе 1991 г. Национальным институтом стандартов и технологий США для обоснования выбора алгоритма EGSА в качестве основы для национального стандарта DSA (Digital Signature Algorithm) перед комиссией Конгресса США.

По сравнению с методом RSA алгоритм EGSA имеет целый ряд преимуществ:

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

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

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

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

Суть алгоритма состоит в следующем. Все операции производятся в некотором конечном поле GF(q) с примитивным элементом g. Порядок поля q представляет собой большое число (в алгебре доказывается, что порядок любого конечного поля представляет собой степень некоторого простого числа; на практике в качестве q используется простое число). Теперь рассмотрим двух участников криптосистемы — А и В. Каждый из них генерирует для себя секретное число (соответственно, а и b), которое хранится в секрете. Кроме того, каждый участник системы вычисляет в поле GF(q) величину g^a и g^b, соответственно. Вычисленные экспоненты являются публичными открытыми ключами, известными всем участникам криптосистемы.

Тогда, если А хочет организовать защищенное соединение с В, А генерирует сессионный ключ для некоторого симметричного алгоритма шифрования следующим образом: А берет публичный ключ стороны В — gb — и возводит его в степень своего секретного ключа а. В результате получается ключ g^(a*b). Очевидно, что этот же ключ может быть получен и стороной В на основании знания собственного секретного ключа b и открытого ключа А — ga.

Вскрытие алгоритма Diffie-Hellman близко к решению задачи нахождения логарифма в дискретном конечном поле, являющейся NP-полной задачей.

Криптостойкость алгоритма существенно зависит от выбора порядка поля, его примитивного элемента, а также размера секретных экспонент. В последнее время большое внимание уделяется алгоритмам ЕСС (Elliptic Curve Cryptography), основанным на применении конструкций, называемых эллиптическими кривыми. В основе этих алгоритмов лежит тот факт, что для уравнения a*x=b относительно х при известных а и b и при условии, что a, b, x принадлежат эллиптической кривой Е, не известно другого алгоритма решения, кроме перебора всех возможных значений х. Более того, в силу сложности самой конструкции эллиптических кривых даже такой простой способ ее решения, как полный перебор, трудно оценить с вычислительной точки зрения. Поэтому оценки надежности систем цифровой подписи ЕСС до последнего времени считались специалистами существенно менее обоснованными, чем аналогичные оценки для задачи разложения на множители и дискретного логарифмирования. Лишь за последние 4-5 лет доверие аналитиков к конструкциям эллиптических кривых существенно возросло.

По современным оценкам сложности при уровне надежности алгоритмов ЕСС, соответствующим криптостойкости алгоритмов, основанным на задаче дискретного логарифмирования с длиной ключа 512 битов, можно ограничиться эллиптической кривой, точки которой описываются парами целых чисел, каждое из которых имеет длину 160 битов. Это позволяет сократить общую длину записи секретного ключа с 512 битов до 320, что, в свою очередь, уменьшает сложность вычислений (а значит, и время) в 2,4 раза. При этом в случае ЕСС сложность верификации ЭЦП в 36-480 раз больше, чем при использовании RSA.

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

В России приняты стандарты: ГОСТ Р 34.10-94 «Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма» и ГОСТ Р 34.11-94 «Функция хэширования». В основу российского стандарта положены схемы Эль-Гамаля и Шнорра.

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

MD2, MD4 и MD5 — алгоритмы дайджеста, разработанные Роном Райвестом. Каждый из них вырабатывает 128-битный хэш-код. Алгоритм MD2 — самый медленный, MD4 — самый быстрый. Алгоритм MD5 можно считать модификацией MD4, в котором скоростью пожертвовали ради увеличения надежности.

SHA-1 (Secure Hash Algorithm) — это алгоритм вычисления дайджеста сообщения, вырабатывающий хэш-код длиной 160 битов. Алгоритм SHA одобрен правительством США (как часть проекта Capstone). Он надежнее алгоритмов MDx, так как вырабатывает более длинный хэшкод, что снижает вероятность того, что разные входные последовательности будут преобразованы в одно значение хэш-кода.

В российском стандарте ГОСТ Р 34.11-94 длина дайджеста определена равной 256 битам.