Методические указания и варианты заданий к выполнению лабораторных работ по дисциплине «Информационная безопасность в сетях» (стр. 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. Далее каждое следующее значение с будем вычислять по формуле: