Глава 36. Схемы шифрования rsa, Эль Гамаля, Полига-Хеллмана

Часть 5. Шифры с открытым ключом шифрования

Глава 36.

Схемы шифрования RSA, Эль Гамаля, Полига-Хеллмана

В частях 5, 6 пособия с согласия авторов использованы материалы книг и работ:

• Ю.В. Романец, П.А. Тимофеев, В.Ф. Шаньгин. Защита информации в компьютерных системах и сетях. Радио и связь, 1999;

• Грушо А.А., Применко Э.А., Тимонина Е.Е. Криптографические протоколы. Йошкар-Ола, 2001;

• Грушо А.А., Тимонина Е.Е., Применко Э.А. Анализ и синтез криптоалгоритмов, Йошкар-Ола, 2000;

• Лекции Фролова А.Б.;

• Работы Семаева И.А..

36.1. Основные понятия модулярной арифметики

Запись

a  b (mod n)

читается так: «a сравнимо с b по модулю n». Это соотношение справедливо для целых значений a,b и n  0, тогда и только тогда, если a = k∙n+ b для некоторого целого k.

Отсюда, в частности, следует n|(a – b). Это читается как «n делит (a– b)».

Если a  b (mod n), то b называют вычетом числа a по модулю n.

Операцию нахождения вычета числа a по модулю n (mod n)

называют приведением числа a по модулю n или приведением по модулю.

Множество Z/n = {0,1,2,..,,(n –1)} с бинарными операциями сложения по модулю n и умножения по модулю n называют кольцом вычетов по модулю n. Множество {0,1,2,..,, (n –1)}называют полным набором положительных вычетов по модулю n. Это означает, что для любого целого a (a > 0) его вычет r по модулю n есть некоторое целое число из Z/n, определяемое из соотношения

a= k∙n+ r,

где k – целое число, r остаток от деления a на n. Например, для n=12 полный набор вычетов: {0,1,2,…,11}.

Приведение по модулю n является гомоморфным отображением кольца целых чисел в кольцо целых по модулю n. Поэтому мы можем либо сначала приводить по модулю n, а затем выполнять операции сложения, умножения, либо сначала выполнять операции, а затем приводить по модулю n. Легко проверяется, что

(a + b) mod n = [a (mod n) + b (mod n)] mod n,

(a – b) mod n = [a (mod n) – b (mod n)] mod n,

(a ∙ b) mod n = [a (mod n) ∙ b (mod n)] mod n,

[a ∙ (b + c)] mod n = {[a∙ b (mod n)] + [a∙ c (mod n)]} mod n.

Вычисление степени числа a по модулю n

a^x mod n

можно выполнить как ряд умножений и последним действием выполнить деление. Модно вычислить это число быстрее, производя возведение в степень как ряд последовательных умножений совместно с приведением по модулю. Это особенно заметно, если работать с длинными числами (200 бит и более). Например, если нужно вычислить

a⁸ mod n,

не следует применять примитивный подход с выполнением семи перемножений и одного приведения по модулю громадного числа:

(a ∙ a ∙ a ∙ a ∙ a ∙ a ∙ a ∙ a) mod n.

Вместо этого выполняют три малых умножения и три малых приведения по модулю:

((a² mod n)² mod n)² mod n.

Тем же способом вычисляют

a¹⁶ mod n = (((a² mod n)² mod n)² mod n)² mod n.

Вычисление

a^x mod n,

где x не является степенью 2, лишь немного сложнее. Двоичная запись числа x позволяет представить число x как сумму степеней 2:

x = 25₍₁₀₎  1 1 0 0 1₍₂₎ – двоичное представление числа 25, поэтому 25 = 2⁴ + 2³ + 2⁰.

Тогда

a²⁵ mod n = (a∙a²⁴) mod n = (a∙a⁸∙a¹⁶) mod n =

= a ∙ ((a²)²)² ∙ (((a²)²)²)² mod n = ((((a^{2 ∙} a)²)²)² ∙ a) mod n.

При разумном накоплении промежуточных результатов потребуется только шесть умножений:

(((((((a² mod n) ∙a) mod n)² mod n)² mod n)² mod n) ∙ a) mod n.

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

УТВЕРЖДЕНИЕ. Чтобы вычислить степень mⁿ, где m элемент некоторого кольца вычетов, а n – некоторое натуральное число, достаточно выполнить не более 2[log2n] умножений, где [log2n] – целая часть числа log2n.

ДОКАЗАТЕЛЬСТВО. Пусть 2^k-1n<2^k. Тогда [log2n]=k-1. Запишем n в двоичной системе счисления

.

Теперь mⁿ можно представить в виде

mⁿ=

Для получения значений чисел 1,m, m², m⁴,…,достаточно выполнить k-1 умножений (возведений в квадрат). Для получения значения mⁿ некоторые из приведенных чисел следует перемножить. Их не более k-1. Следовательно, для получения mⁿ потребуется не более 2(k-1)= 2[log2n] умножений.

Алгоритм Евклида для нахождения наибольшего общего делителя. Целое число a делит без остатка другое целое число b, если, и только если

b = k ∙ a

для некоторого целого числа k (т.е. остаток отделения равен 0). В этом случае a называют делителем числа b или множителем в разложении числа b на множители.

Пусть a – целое число, большее 1. Тогда a является простым числом, если его единственными положительными делителями будут 1 и само a, в противном случае a называется составным.

Любое целое n >1 может быть представлено единственным образом с точностью до порядка сомножителей как произведение простых.

Существенный с точки зрения криптографии факт состоит в том, что не известно никакого эффективного алгоритма разложения чисел на множители.

Наибольший общий делитель чисел a и b, обозначаемый как НОД (a,b) или просто (a,b), – это наибольшее целое, делящее одновременно числа a и b. В эквивалентной форме (a,b) – это то единственное натуральное число, которое делит a и b и делится на любое целое, делящее и a и b. Если НОД (a,b)=1, то целые a и b – взаимно простые.

Наибольший общий делитель может быть вычислен с помощью алгоритма Евклида. Опишем алгоритм Евклида для нахождения НОД(a,b). Введем обозначения: q_i – частное; r_i – остаток. Тогда алгоритм можно представить в виде следующей цепочки равенств:

a = b ∙q₁ + r₁, 0 < r₁< b,

b = r₁ ∙ q₂ + r₂, 0 < r₂< r₁,

r₁ = r₂ ∙ q₃ + r₃, 0 < r₃< r₂,

 

r_k–2 = r_k–1 ∙ q_k + r_k, 0 < r_k< r_k–1,

r_k–1 = r_k ∙ q_k+1.

Остановка гарантируется, поскольку остатки r_i от делений образуют строго убывающую последовательность натуральных чисел. Из этой цепочки немедленно получаем, что r_k есть общий делитель чисел a и b и, более того, что любой общий делитель чисел a и b делит и r_k. Таким образом, r_k = НОД(a, b) или r_k = (a, b).

УТВЕРЖДЕНИЕ. Пусть a и b натуральные числа, a<b. Тогда число k операций последовательного деления в алгоритме Евклида, необходимых для отыскания значения НОД (a,b), удовлетворяет неравенству

.

При операции умножения действительных чисел нетрудно вычислить мультипликативную обратную величину a^–1 для ненулевого числа a:

a^–1 =1/a или a ∙ a^–1 =1.

Например, мультипликативная обратная величина от числа 4 равна 1/4, поскольку 4 =1.

При операции умножения по модулю n в кольце Z/n={0,1,2,..,(n –1)} вычисление обратной величины является более сложной задачей. Например, решение сравнения 4∙x 1 (mod 7) эквивалентно нахождению таких значений x и k, что 4∙x  7∙k +1, где x и k – целые числа.

Общая формулировка этой задачи – нахождение такого целого числа x, что

a∙x (mod n) =1, или a^–1  x (mod n)

Решение этой задачи иногда существует, а иногда его нет. Например, обратная величина для числа 5 по модулю 14 равна 3, поскольку 5∙3=15  1 (mod 14). С другой стороны, число 2 не имеет обратной величины по модулю 14. Вообще сравнение a^–1  x (mod n) имеет единственное решение, тогда и только тогда когда a и n – взаимно простые числа.

В этом случае говорят, что элемент a обратим и его обратный элемент a^–1 равен x. Часто элемент a^–1 обозначают через . Надо всегда понимать, что это целый положительный вычет по модулю n.

Сформулируем основные способы нахождения обратных величин. Пусть a{0,1,2,…,n–1}. Если НОД (a,n) =1, то a∙i (mod n) при i{0,1,2,…,n–1} является перестановкой множества {0,1,2,…,n–1}. Например, если a = 3 и n = 7 (НОД (3,7) =1), то 3∙i (mod 7) при последовательных значениях i равных 0, 1, 2, …, 6 является последовательностью 0, 3, 6, 2, 5, 1, 4, т.е. перестановкой множества чисел 0, 1, 2, …, 6. Это становится неверным, когда НОД (a, n)  1. Например, если a = 2 и n = 6, то 2∙i (mod 6) принимает значения 0, 2, 4, 0, 2, 4 при значениях i равных 0, 1, 2, …, 5. Если НОД (a,n) =1, то для a всегда существует обратное число a^–1, 0 < a^–1 < n, такое, что a∙a^–1 1 (mod n).

Как уже отмечалось, набор целых чисел от 0 до n –1 называют полным набором вычетов по модулю n. Это означает, что для любого целого числа a (a>0) его вычет r = a (mod n) – это некоторое целое число в интервале от 0 до n–1.

Выделим из полного набора вычетов подмножество G вычетов, взаимно простых с n. Такое подмножество называют приведенным набором вычетов, или совместно с операцией умножения по модулю n это множество называют мультипликативной группой G кольца вычетов Z/n. Дело в том, что произведение по модулю n таких вычетов является элементом того же множества G. Например, пусть модуль n=11 – простое число. Полный набор вычетов по модулю 11 есть множество {0, 1, 2, …, 10}. При формировании приведенного набора вычетов из них удаляется только один элемент – 0. Приведенный набор вычетов по модулю 11 имеет 11 – 1 = 10 элементов, G={1, 2, …, 10}. Вообще приведенный набор вычетов по модулю простого числа n имеет n –1 элементов.

Пусть модуль n =10. Полный набор вычетов по модулю n =10 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Из них только 1, 3, 7, 9 не имеют общего сомножителя с числом 10, то есть обратимы. Поэтому приведенный набор вычетов по модулю 10 равен G={1, 3, 7, 9}. При формировании этого приведенного набора были исключены элементы:

0 (1 элемент),

кратные 2 (4 элемента),

кратные 5 (1 элемент),

т.е. всего шесть элементов. Вычитая их из 10, получаем 10 – 1 – 4 – 1 = 4, т.е. четыре элемента в приведенном наборе (в мультипликативной группе кольца вычетов Z/10).

Для произведения простых чисел p∙q=n приведенный набор вычетов имеет (p –1) (q –1) элементов. При n=p∙q=2∙5=10 число элементов в приведенном наборе (p – 1)(q – 1) = = (2 – 1) (5 –1) = 4. Например, приведенный набор вычетов по модулю 27=3³ имеет 18 элементов:

{1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26}.

Из полного набора вычетов исключены элементы, кратные 3 (всего девять элементов). Для модуля в виде простой степени n^r приведенный набор вычетов имеет n^r–1 (n –1) элементов. При n = 3, r = 3 получаем 3^3–1 (3 –1) = 3² ∙ 2 =18.

Функция Эйлера (n) характеризует число элементов в приведенном наборе вычетов, ее значение совпадает с числом элементов |G| мультипликативной группы вычетов.

Модуль n	Функция (n)
n – простое n2 … nr	n –1 n (n –1) … nr–1 (n – 1)
n= p∙q (p, q – простые) … n=(pi – простые)	(p – 1)(q – 1) … a

Иначе говоря, значение функция (n) – это количество положительных целых, меньших n, которые взаимно просты с n.

Любой элемент a из группы G порождает подгруппу H =<a>={a,a²,a³,…,a^m}

Относительно умножения по модулю n порядок группы =<a>={a,a²,a³,…,a^m} (число ее элементов), которой совпадает с порядком элемента a – наименьшим натуральным числом m, при котором a^m 1 (mod n). Для g из G и H={h₁,h₂,.., h_m} положим gH={gh₁,gh₂,…gh_m}. Легко видеть, что |H|=|gH| и при g не принадлежащим H их пересечение пусто. Любая группа имеет разложение по левым (правым) смежным классам по своей подгруппе, G=e (G= ), e – нейтральный элемент (в нашем случае 1). Классы – подмножества (попарно не пересекаются и в объединении дают G). Из сказанного следует, что k|H|=|G| (теорема Лагранжа) и так как |H| в нашем случае совпадает с порядком элемента a, |H|= m, то m делит |G|=(n). По этой причине а^(n) =а^cm для некоторого с и а^(n) =а^cm=(1)^с(mod n) для любого элемента а из G. Таким образом, справедливы теоремы:

• малая теорема Ферма: если n– простое и НОД (a,n)=1, то a^n–1 1 (mod n);

• теорема Эйлера: если НОД (a,n) =1, то a^(n) 1 (mod n).