 |
|
Асимметричные криптосистемы
Метод шифрования с открытым ключом RSA
Цель работы.Ознакомиться на практике с методом шифрования RSA и особенностями его практической реализации (возведение больших чисел в большие степени с использованием модулярного умножения по Монтгомери и метода двоичного возведения в степень).
Исходные данные:
Зашифрованное число C, закрытый ключ D, часть открытого ключа N.
Выходные данные:
Нужно декодировать число M .
Теоретические основы:
Для расшифровки числа M в методе RSA достаточно зашифрованное число C возвести в степень D и найти остаток от деления на N. Основная проблема, возникающая при практическом использовании метода RSA, заключается в том, что числа C, D и N являются очень большими. Использовать традиционные методы умножения чисел при возведении числа C в степень D не получится из-за переполнения вычислительного устройства. На практике используют метод бинарного возведения в степень для сокращения количества умножений, а также метод модулярного умножения по Монтгомери для того, чтобы не выходить из разрядности чисел C, D и N в процессе умножения больше, чем на 1 разряд.
Методические указания:
1. Воспользуйтесь двоичным методом возведения в степень, чтобы определить последовательность умножений (текущий результат умножается сам на себя или же на исходное число), которая минимизирует общее число операций умножения.
2. Переведите число С в модулярную форму.
3. Возведите C в степень D двоичным методом, пользуясь модулярным умножением по Монтгомери (используйте на исходное число C, а его модулярную форму!).
4. Переведите число из модулярной формы в обычную. Для этого умножьте его на 1по Монтгомери.
5. Проверьте расшифрованное сообщение M (введя его в строку «Декодированное сообщение» и нажав кнопку «Проверить»).
Окно программы выполнения лабораторной работы:
Эта программа представляет собой калькулятор, в котором реализованы все необходимые для выполнения лабораторной работы функции: перевод из обычной формы в модулярную, перевод числа из десятичной системы счисления в двоичную, а также умножение по Монтгомери.
На рис. 8 приведено окно программы.
В верхних трех строках ввода находятся исходные данные для выполнения работы. Содержимое любой строки ввода в данной программе можно выделить и скопировать (правая клавиша мыши или же комбинация клавиш “Ctrl-C”) и вставить в другую строку ввода (правая клавиша мыши или же комбинация клавиш “Ctrl-V”). Кнопка “Перевести X в двоичную форму” переводит содержимое строки ввода “Переменная X” в двоичный вид и помещает результат в строку ввода “Результат операции”. Кнопка “Перевести X в модулярную форму” переводит содержимое строки ввода “Переменная X” в модулярную форму и помещает результат в строку ввода “Результат операции”. Кнопка “X*X : R (mod N)” выполняет умножение по Монтгомери содержимого строки ввода “Переменная X” само на себя и помещает результат в строку ввода “Результат операции”. Кнопка “X*Y : R (mod N)” выполняет умножение по Монтгомери содержимого строки ввода “Переменная X” на содержимое строки ввода “Переменная Y” и помещает результат в строку ввода “Результат операции”.
Рис. 8. Окно программы выполнения лабораторной работы
Кнопка “Скопировать в X” помещает результат последнего вычисления (содержимое строки ввода “Результат операции”) в строку ввода “Переменная X”.
Четыре строки ввода, располагающиеся ниже, являются вспомогательными и могут использоваться для хранения любой информации, например, числа D в двоичном виде. Копка “Проверить” предназначена для проверки правильности полученного результата, который должен быть предварительно помещен в строку ввода “Декодированное сообщение”.