5. Описание использованных атак

   1. Атака на общий модуль против алгоритмаRsa

Предположим, что генерация ключей для группы пользователей происходит следующим образом: всем пользователям дается одно значение n, но разные значенияeиd. ПользовательA хочет послать одно и то же сообщение,m, двум различным пользователям с открытыми ключами (n,e₁) и (n,e₂). Зашифрованными текстами будут:

c₁ =m^e1modn,

c₂=m^e2modn.

Противник узнал c₁иc₂, и хочет узнатьm. Чтобы он смог это сделать надо, чтобыe₁иe₂были взаимно простыми, а чаще всего так и оказывается. Поэтому будем считать, что НОД(e₁,e₂) = 1. Следовательно, существуют числаrиs, такие чтоr*e₁+s*e₂=1. Для вычисленияrиsможно воспользоваться расширенным алгоритмом Евклида.

Числа rиsимеют разные знаки. Предположим, чтоrотрицательно. Тогда противник может вычислить (c₁^-1)^-r*c₂^s=mmodn, т.е. получить открытый текст.

Описание атаки взято из [3].

2. Атака на выбранный шифртекст против алгоритмаRsa

Пользователю A направлено сообщениеm, зашифрованное его открытым ключом,e. ПротивникE смог получить соответствующий зашифрованный текст,c.Е хочет узнать открытый текст, т.е. получитьm=c^dmodn, но он не знает секретного ключаd. ПоэтомуEдействует следующим образом:

1. Eвыбирает случайным образом числоr:r<n.

2. Имея открытый ключ A - e, Eвычисляет

x = r^e mod n

y = xc mod n

t = r^-1 mod n.

3. E добивается, чтобыA подписалyс помощью алгоритмаRSA, т.е. расшифровалy, а затем послал ему результатu=y^dmodn.A должен подписать само сообщение, а не его дайджест. Сообщениеyскорее всего будет выглядеть случайным, а на практике иногда приходится подписывать случайные сообщения.

4. E вычисляет

tu mod n = r^-1 y^d mod n = r^-1 x^d c^d mod n = c^d mod n = m,

т.е. получает открытый текст.

Описание атаки взято из [3].

3. Атака против алгоритмаDsa

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

Первый сценарий атаки

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

Противник знает:

r= (g^kmodp)modq,

s = (k^-1 (H(m) + xr)) mod q,

k, m.

Противник вычисляет:

s - k^-1*H(m) = k^-1rx mod q

т.к. q– простое, то можно найти (k^-1*r)^-1modq, откуда

x = (s – k^-1*H(m))* (k^-1*r)^-1 mod q.

Второй сценарий атаки

Противник не знает значения k, но он получил две подписи, при создании которых использовалось одно и то же значениеk.

Противник знает:

r= (g^kmodp)modq,

s₁ = (k^-1 (H(m₁) + xr)) mod q,

s₂ = (k^-1 (H(m₂) + xr)) mod q,

m₁,m₂.

Противник производит следующие действия.

1. s₁ – s₂ = k^-1 (H(m₁) – H(m₂)) mod q (1)

2. из уравнения (1) вычисляет k^-1modq

3. зная k^-1modq, вычисляетk

4. когда kизвестно, можно произвести те же вычисления, что и в первом сценарии

6. Особенности реализации алгоритмов

   1. Управление ключами

      1. Генерация ключей

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

Алгоритм генерации простых чисел [3]

Вход: длина числа в битах n.

1. Сгенерировать случайным образом число pдлинойnбит.

2. Установить младший бит числа равным 1, т.е. сделать его нечетным.

3. Последовательно вычислять остаток от деления pна все простые числа от 3 до 1471. Еслиpделится хотя бы на одно из этих чисел, то прервать вычисление остатков, увеличитьpна 2 и повторить шаг 3.

4. Произвести тест Рабина-Миллера 5 раз. Если pпрошло все тесты, то закончить работу алгоритма, иначе увеличитьpна 2 и перейти к шагу 3.

Выход: число p, которое является простым с вероятностью близкой к 1.

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

a^N-1 1 (modN).

Если же при каком-то aэто сравнение нарушается, можно утверждать, чтоN– составное. Миллер предложил проверять несколько иное условие. ЕслиN– простое число,N-1=2^st, гдеtнечетно, то согласно малой теореме Ферма для каждогоaс условием (a,N)=1 хотя бы одна из скобок в произведении

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

Для простого числа Nне существует чиселa, 1<a<N, для которых нарушается одно из двух условий:

1. Nне делится наa;

2. a^t1 (modN) или существует целоеk, 0k<s, такое, что

Если же Nсоставное число, то, как доказал Рабин, их существует не менее.

Алгоритм Рабина-Миллера, доказывающий, что число не является простым [1]:

1. Выбрать случайным образом число a, 1<a<N, и проверить для этого числа указанные выше условия.

2. Если хотя бы одно из них нарушается, то число Nсоставное.

Составное число не будет определено как составное после однократного применения теста Рабина-Миллера с вероятностью не большей 4^-1. А вероятность не определить его послеkповторений не превосходит 4^-k, т.е. убывает очень быстро.

В данной программе тест Рабина-Миллера применялся 5 раз, т.е. вероятность взять вместо простого числа составное не превосходит 4^-5. Сама по себе эта величина не так уж мала. Но 4^-k- это самая пессимистичная оценка. Практика показывает, что для большинства составныхNтаких чисел не, а примерно[3].

При разработке программы было выяснено, что проведение теста Рабина-Миллера является довольно длительной операцией, поэтому сначала надо попытаться разделить Nна маленькие простые числа. При этом отсеивается большинство составныхN. Было выяснено, что увеличение скорости генерации простых чисел имеет место при делении на все простые числа до 1500.

В алгоритме DSAтребуется два простых числа,pиq, причемqделитp-1. В этом случае сначала генерируетсяq, затем начинается поискp:

1. p := q*q+1

2. Пока pявляется составным, увеличиватьpнаq.

Эта процедура конечна, т.к. доказано, что в арифметической прогрессии

a,a+q,a+ 2q,…,

для которой выполняется условие (a,q)=1, бесконечно много простых чисел. В данном случаеa=1.

В алгоритме цифровой подписи ГОСТ требуется получить число a, такое чтоa^qmodp= 1. Для этого выбирается случайное числоt, и. При этом требуемое условие выполняется, т.к.t^p-1modp=1 по малой теореме Ферма.