Криптография с открытым ключом

Алгоритм RSA

Диффи и Хеллман определили новый подход к шифрованию, что вызвало к жизни разработку алгоритмов шифрования, удовлетворяющих требованиям систем с открытым ключом. Одним из первых результатов был алгоритм, разработанный в 1977 году Роном Ривестом, Ади Шамиром и Леном Адлеманом и опубликованный в 1978 году. С тех пор алгоритм Rivest-Shamir-Adleman ( RSA ) широко применяется практически во всех приложениях, использующих криптографию с открытым ключом.

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

Алгоритм RSA представляет собой блочный алгоритм шифрования, где зашифрованные и незашифрованные данные являются целыми между 0 и n -1 для некоторого n .

Описание алгоритма

Алгоритм, разработанный Ривестом, Шамиром и Адлеманом, использует выражения с экспонентами. Данные шифруются блоками, каждый блок рассматривается как число, меньшее некоторого числа n. Шифрование и дешифрование имеют следующий вид для некоторого незашифрованного блока М и зашифрованного блока С.

С = Ме (mod n)
M = Cd (mod n) = (Me)d (mod n) = Med (mod n)

Как отправитель, так и получатель должны знать значение n. Отправитель знает значение е, получатель знает значение d. Таким образом, открытый ключ есть KU = {e, n} и закрытый ключ есть KR = {d, n}. При этом должны выполняться следующие условия:

Сначала рассмотрим первое условие. Нам необходимо выполнение равенства:

Med = М (mod n)

Рассмотрим некоторые математические понятия, свойства и теоремы, которые позволят нам определить e, d и n.

{p, 2 x p, ј, (q-1)  x p}
{q, 2 x q, ј, (p-1)  x q}
0

Теперь рассмотрим сам алгоритм RSA. Пусть p и q - простые.

n = p x q.

Надо доказать, что $$\forall M < n: M^{\Phi (n)} = M^{(p-1) x (q-1)} \equiv 1 mod n$$

Если gcd (M, n) = 1, то соотношение выполняется. Теперь предположим, что $$gcd (M, n) \ne 1$$, т.е. $$gcd (M, p x q) \ne 1$$. Пусть $$gcd (M, p) \ne 1$$, т.е. M = c x p => gcd (M, q) = 1, так как в противном случае M = c x p и M = l x q, но по условию M < p x q.

Следовательно,

По определению модуля это означает, что $$M^{\Phi (n)} = 1 + k \times q$$. Умножим обе части равенства на M = c x p. Получим

Или

Таким образом, следует выбрать e и d такие, что $$е \times d \equiv 1 mod (n)$$

Или $$e \equiv d^{-1} mod \Phi (n)$$

e и d являются взаимнообратными по умножению по модулю $$\Phi (n)$$. Заметим, что в соответствии с правилами модульной арифметики, это верно только в том случае, если d (и следовательно, е ) являются взаимнопростыми с $$\Phi (n)$$. Таким образом, $$gcd (\Phi (n), d) = 1$$.

Теперь рассмотрим все элементы алгоритма RSA.

Закрытый ключ состоит из {d, n}, открытый ключ состоит из {e, n}. Предположим, что пользователь А опубликовал свой открытый ключ, и что пользователь В хочет послать пользователю А сообщение М. Тогда В вычисляет С = Ме (mod n) и передает С. При получении этого зашифрованного текста пользователь А дешифрует вычислением М = С d (mod n).

Суммируем алгоритм RSA:

Рассмотрим конкретный пример:

Вычислительные аспекты

Рассмотрим сложность вычислений в алгоритме RSA при создании ключей и при шифровании/дешифровании.

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

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

[(a mod n) x (b mod n)] mod n = (a x b) mod n

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

Создание ключей

Создание ключей включает следующие задачи:

Прежде всего, рассмотрим проблемы, связанные с выбором р и q. Так как значение n = p x q будет известно любому потенциальному противнику, для предотвращения раскрытия р и q эти простые числа должны быть выбраны из достаточно большого множества, т.е. р и q должны быть большими числами. С другой стороны, метод, используемый для поиска большого простого числа, должен быть достаточно эффективным.

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

Были разработаны различные тесты для определения того, является ли число простым. Это тесты вероятностные, то есть тест показывает, что данное число вероятно является простым. Несмотря на это они могут выполняться таким образом, что сделают вероятность близкой к 1. Если n "проваливает" тест, то оно не является простым. Если n "пропускает" тест, то n может как быть, так и не быть простым. Если n пропускает много таких тестов, то можно с высокой степенью достоверности сказать, что n является простым. Это достаточно долгая процедура, но она выполняется относительно редко: только при создании новой пары (KU, KR).

На сложность вычислений также влияет то, какое количество чисел будет отвергнуто перед тем, как будет найдено простое число. Результат из теории чисел, известный как теорема простого числа, говорит, что простых чисел, расположенных около n в среднем одно на каждые ln (n) чисел. Таким образом, в среднем требуется проверить последовательность из ln (n) целых, прежде чем будет найдено простое число. Так как все четные числа могут быть отвергнуты без проверки, то требуется выполнить приблизительно ln (n)/2 проверок. Например, если простое число ищется в диапазоне величин 2200, то необходимо выполнить около ln (2200) / 2 = 70 проверок.

Выбрав простые числа р и q, далее следует выбрать значение е так, чтобы $$gcd(\Phi (n), e) = 1$$ и вычислить значение d, $$d = e^{-1} mod \Phi (n)$$. Cуществует единственный алгоритм, называемый расширенным алгоритмом Евклида, который за фиксированное время вычисляет наибольший общий делитель двух целых и если этот общий делитель равен единице, определяет инверсное значение одного по модулю другого. Таким образом, процедура состоит в генерации серии случайных чисел и проверке каждого относительно $$\Phi (n)$$ до тех пор, пока не будет найдено число, взаимнопростое с $$\Phi (n)$$. Возникает вопрос, как много случайных чисел придется проверить до тех пор, пока не найдется нужное число, которое будет взаимнопростым с $$\Phi (n)$$. Результаты показывают, что вероятность того, что два случайных числа являются взаимнопростыми, равна 0.6.

Обсуждение криптоанализа

Можно определить четыре возможных подхода для криптоанализа алгоритма RSA:

Защита от лобовой атаки для RSA и ему подобных алгоритмов состоит в использовании большой длины ключа. Таким образом, чем больше битов в е и d, тем лучше. Однако, так как вычисления необходимы как при создании ключей, так и при шифровании/дешифровании, чем больше размер ключа, тем медленнее работает система.

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

L (n) = esqrt (ln n * ln (ln n))

Пока не разработаны лучшие алгоритмы разложения числа на простые множители, можно считать, что величина n от 100 до 200 цифр в настоящее время является достаточно безопасной. На современном этапе считается, что число из 100 цифр может быть разложено на множители за время порядка двух недель. Для дорогих конфигураций (т.е. порядка $10 млн) число из 150 цифр может быть разложено приблизительно за год. Разложение числа из 200 цифр находится за пределами вычислительных возможностей. Например, даже если вычислительный уровень в 10¹² операций в секунду достижим, что выше возможностей современных технологий, то потребуется свыше 10 лет для разложения на множители числа из 200 цифр с использованием существующих алгоритмов.

Для известных в настоящее время алгоритмов задача определения $$\Phi (n)$$ по данным е и n, по крайней мере, сопоставима по времени с задачей разложения числа на множители.

Для того чтобы избежать выбора значения n, которое могло бы легко раскладываться на сомножители, на р и q должно быть наложено много дополнительных ограничений: р и q должны друг от друга отличаться по длине только несколькими цифрами. Таким образом, оба значения р и q должны быть от 1075 до 10100.

Оба числа (р - 1) и (q - 1) должны содержать большой простой сомножитель.

gcd (p -1, q - 1) должен быть маленьким.

Алгоритм обмена ключа Диффи-Хеллмана

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

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

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

A mod Q, A2 mod Q, . . . , AQ - 1 mod Q

являются различными и состоят из целых от 1 до Q - 1 с некоторыми перестановками. В этом случае для любого целого Y < Q и примитивного корня A простого числа Q можно найти единственную экспоненту Х, такую, что

Y = AХ mod Q, где 0 <= X <= (Q - 1)

Экспонента X называется дискретным логарифмом, или индексом Y, по основанию A mod Q. Это обозначается как

indA, Q (Y).

Теперь опишем алгоритм обмена ключей Диффи-Хеллмана.

Предполагается, что существуют два известных всем числа: простое число Q и целое A, которое является примитивным корнем Q. Теперь предположим, что пользователи I и J хотят обменяться ключом для алгоритма симметричного шифрования. Пользователь I выбирает случайное число Хi < Q и вычисляет Yi = AXi mod Q. Аналогично пользователь J независимо выбирает случайное целое число Хj < Q и вычисляет Yj = AXj mod Q. Каждая сторона держит значение Х в секрете и делает значение Y доступным для другой стороны. Теперь пользователь I вычисляет ключ как К = (Yj)Xi mod Q, и пользователь J вычисляет ключ как K = (Yi)Xj mod Q. В результате оба получат одно и то же значение:

K = (Yj)Xi mod Q 
  = (AXj mod Q)Xi mod Q
  = (AXj )Xi mod Q 
  по правилам модульной арифметики
  = AXj Xi mod Q
  = (AXi )Xj mod Q
  = (AXi mod Q)Xj mod Q
  = (Yi)Xj mod Q

Таким образом, две стороны обменялись секретным ключом. Так как Хi и Хj являются закрытыми, противник может получить только следующие значения: Q, A, Yi и Yj. Для вычисления ключа атакующий должен взломать дискретный логарифм, т.е. вычислить

Xj = inda, q (Yj)

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

Следует заметить, что данный алгоритм уязвим для атак типа "man-in-the-middle". Если противник может осуществить активную атаку, т.е. имеет возможность не только перехватывать сообщения, но и заменять их другими, он может перехватить открытые ключи участников Yi и Yj, создать свою пару открытого и закрытого ключа (Xоп, Yоп) и послать каждому из участников свой открытый ключ. После этого каждый участник вычислит ключ, который будет общим с противником, а не с другим участником. Если нет контроля целостности, то участники не смогут обнаружить подобную подмену.