лаб 15. Лаб раб 15. Лабораторные работы

• Название: Лабораторные работы
• Анкор: лаб 15
• Дата: 22.09.2022
• Размер: 0.6 Mb.
• Имя файла: Лаб раб 15.docx
• Тип: Документы; #690117
• страница: 22 из 26

Шифрование и дешифрование

Как шифрование, так и дешифрование в RSA предполагает использование операции возведения целого числа в целую степень по модулю n. Если возведение в степень выполнять непосредственно с целыми числами и только потом проводить сравнение по модулю n, то промежуточные значения окажутся просто огромными. Поэтому воспользуемся свойствами арифметики в классах вычетов:
[(a mod n) * (b mod n)] mod n = (а * b) mod n.
Таким образом, мы можем рассматривать промежуточные результаты по модулю n. Это делает вычисления практически возможными.

Другой проблемой является эффективная реализация операции возведения в степень, так как в случае применения RSA мы должны иметь дело с потенциально большими показателями. Чтобы продемонстрировать, насколько здесь можно увеличить эффективность вычислений, предположим, что необходимо вычислить x¹⁶. Прямолинейный подход потребует 15 умножений, как показано ниже.

Х¹⁶=х*х*х*х*х*х*х*х*х*х*х*х*х*х*х*х
Однако такого же конечного результата можно достичь и с помощью всего четырех умножений, если повторно возводить в квадрат промежуточные результаты, получая при этом х², х⁴, х⁸, х¹⁶.


_ 2
В общем случае предположим, что нам нужно найти значение a^m, где а и m являются ^{положительными целыми числами. Если представить m в виде двоичного числа b}k^bk-1^…b0^, то

i

M = ,

b_i0

и поэтому
 

_ a
 _{ 2}ⁱ

2ⁱ

a^m =



_a b_i 0



^ = ,

b_i0

a^m mod n =

^



_b_i0

a^2i ^ mod n





_a^2i ^ mod n


.

=
b_i 0

Таким образом, для вычисления a^b mod n можно использовать алгоритм, показанный на рисунке 2. В таблице 2 показан пример последовательности значений, получаемых в результате выполнения этого алгоритма. Обратите внимание на то, что переменная с, вообще говоря, не нужна — она включена в алгоритм только с целью обеспечения наглядности. Конечное значение с будет значением показателя вычисляемой степени.
c←0; d←1

for i←k downto 0 do c←2*c d←(d*d) mod n ^{if b}i ^{= 1}

then c← c+1 d← (d*a) mod n return d
Рисунок 2 - Алгоритм вычисления а^b mod n
Таблица 2 - Результаты выполнения алгоритма быстрого возведения в степень для а^b mod n при а = 7, b = 560 = 1000110000, n = 561.

i	9	8	7	6	5	4	3	2	1	0
b	1	0	0	0	1	1	0	0	0	0
с	1	2	4	8	17	35	70	140	280	560
d	7	49	157	526	160	241	298	166	67	1