Современные средства криптографии

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

      Недостатки  существующего не одно десятилетие  метода полной матрицы хорошо известны. Протокол Диффи-Хеллмана предполагает двусторонний обмен открытыми ключами  и наличие сертификатов у отправителя  и получателя сообщений. В случае односторонней аутентификации (сертификат имеется только у одной из сторон) предпочтение отдается последнему методу. В этой ситуации выбор RSA вполне оправдан – метод цифрового конверта на базе криптоалгоритма RSA описан в стандарте PKCS и применяется в протоколе SSL и других стандартах Internet (PEM, PEM-MIME и т.д.).

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

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

      n=pq.

Далее случайным  образом выбираеться ключ шифрования e, такой, что e и φ(n)=(p-1)(q-1) являються взаимно простыми числами. Наконец расширенный алгоритм Евклида используеться для вычисления ключа дешифрования d, такого, что

ed=1 mod φ(n).

Другими словами,

d=e^-1 mod φ(n).

      Заметим, что d и n – так же взаимно простые  числа. Числа e и n – открытый ключ, а d – секретный. Два простых числа p и q хранятся в секрете. Для шифрования сообщения m необходимо выполнить его разбивку на блоки, каждый из которых меньше n (для двоичных данных выбирается самая большая степень числа 2, меньшая n). То есть если p и q – 100-разрядные простые числа, то n будет содержать около 200 разрядов. И каждый блок сообщения m_i должен иметь такое же число разрядов. (Если нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями слева, тобы гарантировать, что блоки всегда будут меньше n.) Зашифрованное сообщение c будет состоять из блоков c_i той же самой длины. Шифрование сводиться к вычислению

c_i=m_i^e mod n.

При дешифровании для каждого зашифрованного блока c_i вычисляеться

m_i=c_i^d mod n.

Последнее справедливо, так как

C_i^d=(m_i^e)^e=m_i^ed=m_i^kφ(n)+1=m_i*m_i ^kφ(n)=m_i*1=m_i.

Все вычисления выполняються по модулю n.

      Отметим, что сообщение может быть зашифровано  с помощью d, а дешифровано с помощью e, возможен любой выбор.

      Рассмотрим  короткий пример. Если

p=47 и q=71, то n=pq=3337.

Ключ e не должен иметь общих множителей с 

φ(n)=46*70=3220.

Выберем (случайное) e равным 79. В этом случае d=79^-1 mod 3220 = 1019. Опубликуем e и n, сохранив в секрете d. Для шифрования сообщения

m=6882326879666683

сначала разобьем его на блоки. Для выбранных параметров ограничимся блоками по три десятичных разряда. Сообщение разбивается на шесть блоков m_i:

m₁=688

m₂=232

m₃=687

m₄=966

m₅=668

m₆=003

Первый блок шифруется как 688⁷⁹ mod 3337 = 1570 = c₁. Выполняя те же операции для последующих блоков, создадим шифротекст сообщения:

c=15702756209122762423158.

Для дешифрования нужно выполнить возведение в  степень, используя ключ дешифрования 1019:

1570¹⁰¹⁹ mod 3337 = 688 = m₁.

Аналогично восстанавливается  оставшаяся часть сообщения.

Эффективность реализации

      Существует  много публикаций, затрагивающих  тему аппаратных реализаций RSA.

      Быстродействие  аппаратной реализации RSA примерно в 1000 раз ниже, чем быстродействие аппаратной реализации DES. Быстродействие СБИС-реализации RSA с 512-битовым модулем – 64 Кбит/сек. Существуют также микросхемы RSA, которые оперируют с 1024-битовыми числами. В настоящее время разрабатываются микросхемы, которые, используя 512-битовый модуль, приблизятся к рубежу 1 Мбит/сек. Производители так же реализуют RSA в интеллектуальных карточках, однако производительность этих реализаций невысока. Программная реализация DES примерно в 100 раз быстрее программной реализации RSA. Эти оценки могут незначительно могут незначительно меняться в зависимости от используемых технологий, но RSA никогда не достигнет производительности симметрических алгоритмов.

      Шифрование RSA выполняются намного эффективнее, если правильно выбрать значение e. Чаще всего используются 3, 17 или 65537 = 2¹⁶+1 – двоичное представление этого числа содержит только две единицы, поэтому для возведения в степень нужно выполнить лишь 17 умножений. Стандарт X.509 рекомендует число 65537, PEM – 3, PKCS#1 – 3 или 65537. Использование в качестве e любого из указанных значений (при условии, что сообщение дополняются случайными числами) не влияет на криптостойкость, даже если одно и то же значение e используется группой пользователей. Операции с секретным ключом можно ускорить при помощи китайской теоремы об остатках, если сохранить значения p и q, а так же заранее по секретному и открытому ключам вычислить вспомогательные значения: d mod (p-1), d mod (q-1) и q^-1 mod p.

Криптостойкость RSA

      Предполагается, что криптостойкостью RSA зависит от проблемы разложения на множители больших чисел. Однако никогда не было доказано математически, что нужно разложить n на множители, чтобы восстановить m по c и e. Не исключено, что может быть открыт совсем иной способ криптоанализа RSA. Однако, если этот новый способ позволит криптоаналитику получить d, он также может быть использован для разложения на множители больших чисел. Так же можно атаковать RSA, угадав значение (p-1)(q-1). Однако этот метод не проще разложения n на множители. Доказано, что при использовании RSA раскрытие даже нескольких битов информации по шифротексту не легче, чем дешифрования всего сообщения. Самой очевидной атакой на RSA является разложение n на множители. Любой противник сможет получить открытый ключ e и модуль n. Чтобы найти ключ дешифрования d, противник должен разложить n на множители. Криптоаналитик может перебирать все возможные d, пока не подберет правильное значение. Но подобная силовая атака даже менее эффективна, чем попытка разложения n на множители. В 1993 г. Был предложен метод кирптоанализа, основанный на малой теореме Ферма. К сожалению, этот метод оказался медленнее разложения на множители. Существует еще одна проблема. Большинство общепринятых тестов устанавливает простоту числа с некоторой вероятностью. Что произойдет, если p или q окажется составным? Тогда у модуля n будет три или более делителей. Соответственно некоторые делители будут меньше рекомендованной величины, что, в свою очередь, открывает возможности для атаки путем факторизации модуля. Другая опасность заключается в генерации псевдопростых чисел (чисел Кармайкла), удовлетворяющих тестам на простоту, но при этом не являющихся простыми. Однако вероятность генерации таких чисел пренебрежимо мала. На практике, последовательно применяя набор различных тестов на простоту, можно свести вероятность генерации составного числа до необходимого минимума.

Итоги по безопасности

      На  основании известных атак можно  сформулировать следующие ограничения  при использовании RSA:

• знание одной пары показателей шифрования/дешифрования для данного модуля позволяет злоумышленнику разложить модуль на множители;
• знание одной пары показателей шифрования/дешифрования для данного модуля позволяет злоумышленнику вычислить другие пары показателей, не расладывая модуль на множители;
• в криптографических протоколах с использованием RSA общий модуль использоваться не должен. (Это являеться очевидным следствием предыдущих двух пунктов.);
• для предотвращения раскрытия малого показателя шифрования сообщения должны быть дополнены («набиты») случайными значениями;
• показатель дешифрования должен быть большим.

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

Криптосистема ЭльГамаля.

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

      Для генерации пары ключей сначала выбираются простое число p и два случайных числа, g и x; оба этих числа должны быть меньше p. Затем вычисляется

y=g^x mod p.

Открытым ключом являются y, g и p. И g, и p можно сделать  общими для группы пользователей. Секретным является x.

Вычисление  и проверка подписи

      Чтобы подписать сообщение M, сначала выбирается случайное число k, взаимно простое  с p-1. Затем вычисляется a=g^k mod p, и с помощью расширенного алгоритма Евклида из уравнения

M=(xa+kb) mod (p-1)

находиться b. Подписью является пара чисел: a и b. Случайное  значение k должно храниться в секрете. Для проверки подписи необходимо убедиться, что

y^aa^b mod p = g^M mod p.

Каждая новая  подпись требует нового значения k, и это значение должно выбираться случайным образом. Если злоумышленник раскроет k, используемое Алисой, он сможет раскрыть секретный ключ Алисы x. Если злоумышленник сможет получить два сообщения, подписанные при помощи одного и того же k, он сможет раскрыть x, даже не зная k.

      Рассмотрим  простой пример. Выберем p=11 и g=2. Пусть  секретный ключ x=8. Вычислим

y=g^x mod p = 28 mod 11 = 3.

Открытым ключом являются y=3, g=2 и p=11. Чтобы подписать M=5, сначала выберем случайное число k=9. Убедимся, что gcd(9,10)=1. Далее вычислим

a=g^k mod p = 29 mod 11 = 6,

и затем с  помощью расширенного алгоритма  Евклида найдем b из уравнения

5=(8*6+9*b) mod 10.

Решение: b=3, а  подпись представляет собой пару: a=6 и b=3. Для проверки подписи убедимся, что y^aa^b mod p = g^M mod p:

3663 mod 11 = 25 mod 11. 
 

Шифрование/дешифрование

      Некоторая модификация позволяет использовать криптосистему для шифрования/дешифрования сообщений.

      Для шифрования сообщения M сначала выбирается случайное число k, взаимно-простое  с p-1. Затем вычисляются:

a=g^k mod p,

b=y^kM mod p.

Пара (a,b) является шифротекстом. Отметим, что шифротекст в два раза длиннее открытого текста.

 Для дешифрования (a,b) вычисляются

      По  сути описанное преобразование –  это то же самое, что и экспоненциальный ключевой обмен по Диффи-Хеллману, за исключением того, что обмен по Диффи-Хеллману, за исключением того, что - это часть ключа, а при шифровании сообщение умножается на y^k.  

Хеш-функции

      Односторонняя функция H применяется к сообщению произвольной длины M и возвращает значение h=H(M) фиксированной длины m. Многие функции позволяют значение фиксированной длины по входным данным произвольной длины, но однонаправленные (или односторонние) хеш-функции обладают рядом дополнительных свойств:

• зная M, легко вычислить h;
• при заданном h задача нахождения M, для которого H(M)=h, должна быть вычислительно-трудоемкой;
• при заданном M задача нахождения другого сообщения M’, для которого H(M)=H(M’), должна быть вычислительно трудоемкой.

      Смысл применения однонаправленных хеш-функций  и состоит в обеспечении для M уникального значения – «отпечатка пальца» сообщения. Если Алиса подписала M цифровой подписью с использованием хеш-функции H(M), а боб может создать другое сообщение M' отличное от M, для которого H(M)=H(M'), то Боб сможет утверждать, что Алиса подписала сообщение M'. В некоторых приложениях необходимо выполнение дополнительного требования, называемого устойчивостью к коллизиям. Смысл данного требования заключается в том, что задача нахождения двух случайных сообщений M и M', для которых H(M)=H(M’), должна быть вычислительно-трудоемкой (с экспоненциальным объемом перебора).