Методические указания и варианты заданий к выполнению лабораторных работ по дисциплине «Информационная безопасность в сетях» (стр. 3 из 7)
Например,
Приведем код на Паскале вычисления функции возведения в степень:
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 до 106, равно примерно 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=2s∙t, где t – нечетно. Будем говорить, что число a отвергает число Т, если выполнено одно из двух условий:
а) Т делится на a,
б)
и для всех целых k, 
.Если найдется число а, отвергающее Т, то Т является составным. Тест Миллера выполняется следующим образом:
1. Выбираем случайное число a, 1 < a < Т, и проверим, что Т не делится на а нацело,
2. Проверим далее, что
или найдется k, 
, такое, что 
Если какое-то из условий 1 и 2 не будет выполнено, то число Т – составное, иначе, ответ не известен. Повторим процедуру с новым а.
После k циклов вероятность того, что Т – составное, меньше 4-k, т.е. убывает очень быстро.
Разложение чисел на множители методом ρ-эвристики Полларда.
Этот метод факторизации натурального числа N был разработан известным криптографом Джоном Поллардом и является самым быстрым среди простых методов факторизации. Его идея состоит в том, что порождается случайная последовательность чисел {xi} (например, взяв x0=2, и продолжить вычисление по формуле
). Далее, вычисляются всевозможные разности 
. Для каждой такой пары (xi, xj) находятся с помощью алгоритма Евклида наибольший общий делитель НОД(N, |xi - xj|)). Если будет найдена пара (xi, xj) со свойством НОД(N, |xi - xj|))>1, то этот НОД и даст искомый делитель числа N.Обоснование метода Полларда. Пусть p –делитель N. Среди членов последовательности {xi} рано или поздно попадутся числа xi и xj такие, что
= 
(это равенство записывается более кратко 
). Это условие означает, что 
для некоторого целого числа k. Т.к. p – делитель N, то для выбранной пары (xi, xj) НОД(N; |xi - xj|)= p. Оценка сходимости метода Полларда. Т.к. меньший делитель числа N меньше
, то элементы последовательности 
меньше . По парадоксу близнецов (см. [1]) среди первых 
членов последовательности 
с вероятностью, большем чем 0,5, попадутся два одинаковых члена, т.е. найдутся i, j, удовлетворяющие условию 
. Поэтому, с вероятностью, большей 0,5, мы найдем искомый делитель N, просмотрев не более 
, членов последовательности.При практическом применении метода Полларда для сокращения объема вычисления рассматривают не все разности |xi - xj|, а только те, для которых номер j является степенью 2, т.е. принимает значения 2, 4, 8, ...
Рассмотрим пример. Пусть N=1387. Зададим рекуррентную последовательность чисел {xi} следующим соотношением:
=2, 
. Значения строки xj определим равными ближайшему слева xi, у которого i является степенью 2 (такие xi выделены красным). В следующей строке поместим их разность, а в последней строке – НОД(N; |xi - xj|), вычисленный с помощью алгоритма Евклида. | N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| xi | 2 | 3 | 8 | 63 | 1194 | 1186 | 177 | 814 | 996 | 310 | 396 |
| yi | 1 | 2 | 3 | 3 | 63 | 63 | 63 | 63 | 814 | 814 | 814 |
| |xi-yi| | 1 | 1 | 5 | 60 | 11131 | 1123 | 114 | 751 | 182 | 504 | 418 |
| НОД | 1 | 1 | 1 | 1 | 1 | 1 | 19 | 1 | 1 | 1 | 19 |
Из таблицы видно, что уже на 7-м шаге был найден делитель N, равный 19.
{Вычисление наибольшего общего делителя}