90

Для вычисления x = loga y в GF(p), когда α имеет мультипликативный порядок N (αN =1(modp)), используют алгоритм Shank [Massey 94].

Выбирается некоторое целое d , где d ≈						N .
	Тогда x = Qd + r, 0 ≤ r < d ≈				N и
	0 ≤ Q < N ≈	N .
	α
	Далее все вычисления ведутся в GF(p).						аρ = a a ρ−1 и запоминаем
1.	Для ρ = 0,	1,	… ,	d-1 вычисляем
(α ρ , ρ) ρ = logα (α ρ ) - это все логарифмы γ такие, что logα γ < d.
2.	Составляем таблицу (γ, logα γ ) для 0 ≤ logα γ < d – таблицу малых
логарифмов.
3.	Вычисляем α−d =α N −d с помощью алгоритма быстрого возведе-
ния в степень.
	Заметим, что
	y =α x =αQd +r = aQd ar ,
	yα−Qd =αr
и, следовательно,
	y(α−d )Q = ar .
4.	Для q = 0, 1, 2, … вычисляем				y (α −d )q до тех пор, пока y (α −d )q
не станет равным некоторому γ =α ρ					в таблице.
5.	Тогда x = qd + ρ		и	α qd +ρ =α qd		α ρ	=α qd y(α −d )q = y .

Сложность алгоритма имеет порядок 2 N операций умножения и память

N .

Пример 2. Найдем x = log5 13, здесь 5- примитивный элемент GF(23), и

N = 22 (522 = 1(mod23)) .

(0)d = 5

(1)50 =1

51 = 5

52	= 25 = 2
53	= 5 2 =10		3 операции умножения.
54
	= 5 10 = 4

(2)

91

γlogα γ

10

22

44

51

10 3

(3) α−d =α N −d =α17 =α16 α1

α1 = 5
α 2 = 5	×5 = 2
α 4 = 2 × 2 = 4			α −d = 3 ×5 =15
α8 = 4	× 4 =16

α16 =16 ×16 = 3

(4)y = 13 не принадлежит входу в таблице (q = 0).

y α−d =13×15 =11 непринадлежит входу в

таблице (q =1), 2 операции умножения

( y α−d ) α−d =11×15 = 4 принадлежит входув таблице при q = 2.

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

(4, 4) = (4, ρ) x = qd + ρ = 2 5 + 4 =14 . x = log5 13 = 14

и для его нахождения требуется 5 операций умножения.

Проблема дискретного логарифмирования упрощается, если основание логарифма α имеет порядок N и N = N1 N2 и сводится к дискретному логарифмированию по основанию, имеющему порядок N1, и дискретному логарифмированию по основанию, имеющему порядок N2 .

Алгоритм [Massey 94] нахождения дискретного логарифма, когда основание логарифма α имеет порядок N и N = N1 N2 приведен ниже. Пусть

x = logα y (a N =1, N = N1 N2 ) .

(0)Вычисляем y1 = y N2 с помощью алгоритма быстрого возведения в степень.

(1)Вычисляем α1 =α N2 с помощью алгоритма быстрого возведения в степень.

(2)Находим x1 = logα1 y1 .

92

(3)Вычисляем α N −x1 с помощью алгоритма быстрого возведения в степень.

(4)Вычисляем y2 = y α N −x1 .

(5)Вычисляем α2 =α N1 с помощью алгоритма быстрого возведения в степень.

(6)Находим x2 = logα2 y2 .

(7)Получаем x = x 2 N1 + x1.

4.6. Схема RSA.

RSA [Schn 96] используется как для шифрования, так и для подписи. Выберем p и q – большие простые числа. Пусть модуль n = p q, функция ϕ(n) = (p-1) (q-1) – функция Эйлера. Возьмем произвольное 1≤ е<ϕ(n) такое, что НОД(е, ϕ(n)) = 1. Тогда существует единственное

1≤ d <ϕ(n) такое, что ed(modϕ(n)) = 1.

Система шифрования RSA – это система с открытым ключом, где е –открытый, а d – секретный ключи. Если 0≤ x<n – это открытое сообщение, то шифрсообщение получается следующим образом:

С = хe (mod n).

Возможность расшифрования следует из следующей теоремы.

Теорема 1. Если p и q – большие простые числа, ed(modϕ(n)) = 1, то х, 0≤ x<n:

(хe ) d (modn) = x.

Д о к а з а т е л ь с т в о. Пусть НОД(х, n) =1. Тогда

(хe ) d = хe d = x k ϕ(n)+1 .

Поэтому по теореме Эйлера

(хe ) d (modn) = (х( x ϕ(n) (modn)))(modn)= (x 1)(modn) = x.

Если НОД(х,n) ≠ 1, то или х =0(modn), или НОД(х,n) = p, или НОД(х,n) = q. Если х =0(modn), то хe d =0(modn). Пусть НОД(х,n) = p. Тогда х = х1p, где

(х1, n) =1.

хe d = x k( p−1)(q −1)+1= px1p k( p −1)(q −1) x1 k( p −1)(q −1) ≡ y(modpq).

Если mp= y(mod(pq)), то mp = pqk + y, следовательно, y = py1. Тогда m ≡ y1(modq. Следовательно,

x1((pх1) k( p −1) ) q−1 ≡ y1 (modq).

По теореме Ферма z1 q−1 ≡ 1 (modq). Поэтому

93

x= x1p(mod(pq)) = y (modn) ≡ хe d (modn),

что и требовалось доказать.

Открытый и шифрованный тексты эффективно вычисляются, если известны е и d при помощи алгоритма быстрого возведения в степень. Если искать секретный ключ d по известному открытому ключу е, то надо знать ϕ(n).

Теорема 2. Вычисление ϕ(n) = (p-1)( q-1) эквивалентно (с точностью до алгоритма полиномиальной сложности) факторизации числа n = p q.

Д о к а з а т е л ь с т в о. Пусть известны n и ϕ(n). Тогда p и q находятся быстро. Это следует из следующих равенств.

ϕ(n) = (p-1)(q-1) = pq-p-q+1 = n-p-q+1.

Отсюда

p+q= n-ϕ(n)+1, pq = n.

По теореме, обратной к теореме Виета, p и q являются корнями квадратного уравнения:

х2 - (n -ϕ(n)+1)x + n = 0.

Вычисление корней – полиномиальный алгоритм. Обратно, если известны p и q, pq = n, то ϕ(n) = (p-1)(q-1). Теорема доказана.

Подпись RSA.

Пусть М – сообщение, которое надо подписать. Подпись получается по следующему алгоритму:

С = Мd (mod n),

тогда (М, С) - сообщение с подписью. Проверка подписи осуществляется следующим образом

Сe ( mod n) = Мe d (mod n) = М’.

Если М = М’, то подпись верна.

4.7. Атаки на RSA.

1. Активная атака с помощью выбранного шифртекста.

Пусть злоумышленник Е перехватывает шифрованное сообщение с от корреспондента А к корреспонденту В. Пусть c = z e (modn), где z- открытый текст, е- открытый ключ и z = cd (mod n) , где d- секретный ключ. Е хочет

прочитать открытый текст z. Для этого Е выбирает число r, r < n, и вычисляет с помощью открытого ключа

94

x = re (mod n), y = x c(mod n), t = r −1(mod n),

так, что r = xd (mod n), t = x− d (mod n).

Пусть Е подписывает у А y с помощью секретного ключа d, т.е. u = yd (mod n) .

Затем Е вычисляет

t u(mod n) = x− d ( yd (mod n)) = x− d xd zed (mod n) = z .

Таким образом, Е читает z.

2. Предположим, что Е хочет получить подпись на число N у А, а А никогда не подпишет N. Тогда Е выбирает произвольным образом Х и вычисляет

Y = X e (mod n) .

Затем Е вычисляет M = Y N и посылает А на подпись. А подписывает М и возвращает Е число M = M d (mod n) . Е вычисляет

Md X −1(mod n) = (Y N )d X −1(mod n) =

=X e d N d X −1(mod n) = N d (mod n) ,

что и является подписью N.

3. Пусть Е хочет подписать у А число M 3 . Тогда Е генерирует 2 сообщения M1 и M 2 так, что

M 3 ≡ M1 M 2 (mod n) .

Подписав у А сообщения M1 и M 2 , Е затем вычисляет подпись для M 3 :

M3d (mod n) = M1d (mod n) M 2d (mod n).

4.Атака с использованием общего модуля.

Пусть у всех абонентов сети один модуль n и различные секретные и открытые ключи. Рассмотрим открытый текст Р и предположим, что он зашифрован на двух различных открытых ключах e1 и e 2

c1 = pe1 (mod n),

c	2	= pe2	(mod n),	где НОД(e , e	2	) =1.
				1

Тогда в силу обобщённой теоремы Евклида, существуют такие числа r и s,

что

r e1 + s e2 =1.

95

Пусть r отрицательно (отрицательно должно быть либо r, либо s). Тогда можно вычислить c1−1 , используя алгоритм Евклида, а затем

(c1−1)−r c2s = pe1r +e2 s (mod n) = P. 5. Атака с малой экспонентой.

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

y1 = x3 (mod m1); y2 = x3 (mod m2 );

y3 = x3 (mod m3 ),

и пусть m1 , m2 , m3 - взаимнопростые числа. Следовательно, x3 < m1 m2 m3 . Мы можем найти x3 из y1, y2 , y3, используя обращение китайской теоремы об остатках, а затем найти х путём извлечения кубического корня из x3 .