Смекни!
smekni.com

Методические указания и варианты заданий к выполнению лабораторных работ по дисциплине «Информационная безопасность в сетях» (стр. 2 из 7)

Генерация параметров RSA завершена. Пара (N, e) объявляется открытым ключом, а параметры

и d закрытыми параметрами (d – закрытый ключ).

Шифрование/расшифровка сообщений по методу RSA.

Текст, который следует зашифровать, разбивается на отдельные символы (или на блоки по k бит в реальных задачах, где

, L – длина N в битовом представлении). Для шифрования числа с, служащего кодом символа, выполняется операция возведения в степень по формуле

(*)

где числа N, e взяты из открытого ключа RSA.

Обратная расшифровка выполняется возведение шифра r в степень d, где d – секретный параметр RSA.

(**)

Гарантией того, что при повторном возведении в степень, будет получено исходное число, служит теорема Эйлера, которая утверждает, что для любого

выполняется формула
. Проверим операцию (**):

Расширенный алгоритм Евклида.

Алгоритм Евклида используются для нахождения по заданным целым числам A и B их наибольшего общего делителя С=НОД(А; B). Расширенный алгоритм Евклида используется также для нахождения целых чисел x, y таких, что выполняется условие

. Используется во многих криптографических конструкциях, в том числе в методе RSA.

Основным равенством, используемым для вычисления НОД чисел А и В, является условие

НОД(А, В) = НОД( В, A mod B) (3)

где A mod B – остаток от целочисленного деления А на В. Применяя последовательно формулу (3), мы будем уменьшать числа А и В в этом алгоритме, пока A mod B не станет равным 0, тогда последнее значение аргумента В даст искомый НОД (А, В). Полное описание расширенного алгоритма мы объясним на примере. Пусть числа А и В равны 172 и 38 соответственно. Откроем рабочий лист Excel и разметим в первых строчках заголовки столбцов, а под заголовками А и В поместим числа 172 и 38, как указано на рисунке.

Рис.1. Примерный вид рабочего листа Excel для реализации расширенного алгоритма Евклида.

В столбце Amod B напишем формулу вычисления остатка от целочисленного деления А на В: =ОСТАТ(A3;B3), а в столбце A div B впишем формулу =ЦЕЛОЕ(A3/B3), обозначающую операцию нахождения целой части от деления A на В.

В следующей строке в столбах А и В поместим значения 38 и 20, взятые из двух ячеек, находящихся выше и правее (применение формулы (3)). Значения ячеек под заголовками Amod B и A div B надо вычислить как в предыдущей строке. В Excel для этого достаточно просто скопировать и вставить вышележащие клетки на строку ниже.

Повторяем эти операция несколько раз, пока не получим в столбце Amod B значение 0. Значение В в этой строке будет равно НОД(А,В) (в нашем примере он равен 2).

Далее заполняем столбцы x и y в обратном порядке снизу вверх. Поместим в столбцы x и y в последней полученной строке значения 0 и 1. Далее в каждой следующей (вышележащей) строке i поместим значения xi и yi, вычисленные по формулам:

где

обозначает значение из столбца A div B, взятое из той же строки, где вычисляются значения x и y. Используя эти формулы, заполним столбцы x и y. В верхней строке получим значения x и y, которые нам нужны.

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

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

(1)

выполняя сначала возведение в степень, а потом вычисляя остаток от деления

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

Алгоритм быстрого возведения в степень основывается на идее замены прямого вычисления возведения в степень

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

(2)

где любое ti для

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

,
(3)

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

,
.

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

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

где

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

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

.

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

e div 2 13 6 3 1
e mod 2 1 0 1 1

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

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

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

е

1

1

0

1

с

5

11

7

10

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

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