Алгоритм возведения в степень по модулю натурального числа.

Для выполнения шифрования по методу RSA приходится выполнять возведение в большую степень различных чисел, а результат приводить по модулю числа N, являющегося параметром метода и имеющего длину 512 и более бит. Уже для небольших a и e вычислить значение

(1)

выполняя сначала возведение в степень, а потом вычисляя остаток от деления на N, становится невозможным. Между тем, если применить алгоритм, описанный в этом разделе, можно вычислять выражения (1), для достаточно больших чисел a, e, N, оставаясь в рамках обычных операций с целыми числами, заложенных в компьютере.

Алгоритм быстрого возведения в степень основывается на идее замены прямого вычисления возведения в степень последовательными операциями умножения на a и возведения в квадрат. Для этого представим степень e число в двоичном исчислении

(2)

где любое t_i для принадлежит , . Зная вектор разрядов , можно вычислить число e, применяя последовательные вычисления:

, (3)

Например, если e = 13, то в двоичном представлении e = 1101₂, и 13 можно представить как результат вычисления , .

Последнее число и есть e.

Используя формулы (3), можно процедуру возведения в степень по модулю натурального числа N, записать в виде последовательности итераций:

где . Множитель в зависимости от принимает либо значение a, если , либо 1, если . Результат вычислений можно свести в таблицу

			...
			...

Пример. Вычислить .

Решение. Переведем степень e=13 в двоичный вид. Для этого заполним следующую таблицу:

e div 2
e mod 2

Таблица 1. Перевод десятичного числа e к двоичному представлению.

Искомое двоичное разложение числа e будет во второй строке таблицы, записанное в обратном порядке справа налево.

Далее, составим таблицу вычисления с, заполняя следующую таблицу:

е
с

Таблица 2. Возведение а=5 в степень e=13 по модулю 19.

В первой строке запишем цифры двоичное разложения числа 13. В первую ячейку второй строки поместим основание а =5. Далее каждое следующее значение с будем вычислять по формуле:

Например,

Приведем код на Паскале вычисления функции возведения в степень:

Function Rise(A,B,N:Integer):Integer;

var

B2:array[1..20] of byte;

i,C,L:integer;

Begin

C:=B; i:= 1;

While C > 0 do

Begin

B2[i]:= C Mod 2;

C:= C div 2;

i:= i + 1;

End;

L:= i - 1;

i:= 1;

D:= A;

While i <L do

Begin

D:= (D * D) Mod N;

If B2[L-i]= 1 Then D:=(D * A) Mod N;

i:= i + 1;

End;

Rise:= D;

End;

Генерация простых чисел

Для определения параметров RSA необходимо генерировать простые числа заданной длины. Известно, что на интервале [1; N ] число простых чисел равно примерно . Например, для N, равного 1 млн, число простых чисел в интервале от 1 до 10⁶, равно примерно 50 тысяч. Для генерации простых чисел можно выбрать произвольное нечетное число T и проверить его на простоту с помощью одного из тестов, описанных ниже. Если T окажется составным, то надо заменить его на T+2 и проверить снова затем проверить T+4 и т.д. В среднем, через шагов простое число будет найдено. Для генерации числа из заданного интервала [A; B] в Visual Basic можно использовать следующий алгоритм:

Function Generator(A as Integer, B as integer) As Integer

Randomize

t = Rnd() * (B - A) + A

Generator = t

End Function

1. Перебор делителей числа Т. Если число Т – составное, то найдется число k, меньшее , которое делит Т. Поэтому простейшим тестом на простоту является проверка делителей числа Т от 2 до . Приведем программу на Visual Basic:

Function Check_prime(T As Integer) As Boolean

Dim k as integer

Dim k As Integer

Dim i As Integer

Dim b As Boolean

b = True

k = Int(Sqr(T))

For i = 2 To k

If T Mod i = 0 Then

b = False

Exit For

End If

Next i

Test_prime = b

End function

2. ТестФерма. Согласно теореме Ферма, если число Т – простое, то для любого . На обращении этой теоремы основан следующий вероятностный тест:

Если для произвольных различных k чисел a, меньших T, выполняется условие , то с вероятностью, не меньшей, чем , число a является простым.

К сожалению, полностью обратить теорему Ферма нельзя, т.к. существуют так называемые числа Кармайкла, для которых условие Ферма выполнено для всех a, меньших T, но числа являются составными. Однако, поскольку числа Кармайкла встречаются чрезвычайно редко, то в наших условиях можно ими пренебречь.

3. Тест Миллера Рабина. Пусть Т – произвольное число. Представим Т–1 в виде N–1=2^s∙t, где t – нечетно. Будем говорить, что число a отвергает число Т, если выполнено одно из двух условий:

а) Т делится на a,

б) и для всех целых k, .

Если найдется число а, отвергающее Т, то Т является составным. Тест Миллера выполняется следующим образом:

1. Выбираем случайное число a, 1 < a < Т, и проверим, что Т не делится на а нацело,
2. Проверим далее, что или найдется k, , такое, что

Если какое-то из условий 1 и 2 не будет выполнено, то число Т – составное, иначе, ответ не известен. Повторим процедуру с новым а.

После k циклов вероятность того, что Т – составное, меньше 4^-k, т.е. убывает очень быстро.

Разложение чисел на множители методом ρ-эвристики Полларда.

Этот метод факторизации натурального числа N был разработан известным криптографом Джоном Поллардом и является самым быстрым среди простых методов факторизации. Его идея состоит в том, что порождается случайная последовательность чисел {x_i} (например, взяв x₀=2, и продолжить вычисление по формуле ). Далее, вычисляются всевозможные разности . Для каждой такой пары (x_i, x_j) находятся с помощью алгоритма Евклида наибольший общий делитель НОД(N, |x_i - x_j|)). Если будет найдена пара (x_i, x_j) со свойством НОД(N, |x_i - x_j|))>1, то этот НОД и даст искомый делитель числа N.

Обоснование метода Полларда. Пусть p –делитель N. Среди членов последовательности {x_i} рано или поздно попадутся числа x_i и x_j такие, что = (это равенство записывается более кратко ). Это условие означает, что для некоторого целого числа k. Т.к. p – делитель N, то для выбранной пары (x_i, x_j) НОД(N; |x_i - x_j|)= p.

Оценка сходимости метода Полларда. Т.к. меньший делитель числа N меньше , то элементы последовательности меньше . По парадоксу близнецов (см. [1]) среди первых членов последовательности с вероятностью, большем чем 0,5, попадутся два одинаковых члена, т.е. найдутся i, j, удовлетворяющие условию . Поэтому, с вероятностью, большей 0,5, мы найдем искомый делитель N, просмотрев не более , членов последовательности.

При практическом применении метода Полларда для сокращения объема вычисления рассматривают не все разности |x_i - x_j|, а только те, для которых номер j является степенью 2, т.е. принимает значения 2, 4, 8,...

Рассмотрим пример. Пусть N=1387. Зададим рекуррентную последовательность чисел {x_i} следующим соотношением: =2, . Значения строки x_j определим равными ближайшему слева x_i, у которого i является степенью 2 (такие x_i выделены красным). В следующей строке поместим их разность, а в последней строке – НОД(N; |x_i - x_j|), вычисленный с помощью алгоритма Евклида.

N
xi
yi
|xi-yi|
НОД

Из таблицы видно, что уже на 7-м шаге был найден делитель N, равный 19.

{Вычисление наибольшего общего делителя}

Function NOD(A as integer, B as integer) as integer

if (A mod B)=0 then

NOD=B

Else

NOD=NOD(B, A mod B)

End if

End

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Что вычисляет алгоритм Евклида?
2. Сколько строчек вычислений необходимо произвести в алгоритме Евклида?
3. Как производится заполнение столбцов x и y в расширенном алгоритме Евклида?
4. Какая алгоритмически сложная задача лежит в основе метода RSA?
5. Что такое простое число? Какие методы проверки простоты числа вы знаете?
6. Как генерируется параметры метода RSA?
7. Какие параметры в RSA вычисляются с помощью алгоритма Евклида?
8. Как производится процедура шифрования/расшифровки в методе RSA?
9. Какой длины должны быть простые числа p и q в методе RSA, чтобы обеспечить необходимый уровень надежности?
10. Каким образом, зная значение функции Эйлера и открытый ключ е, можно рассчитать закрытый параметр d?
11. Дайте определение односторонней функции.
12. Сколько итераций потребуется сделать в методе Полларда, если N ≈100 млн (10⁸)?

Лабораторная работа №2