ИМИТАЦИЯ «ШИФРОВАЛЬНОЙ МАШИНЫ» RSA СРЕДСТВАМИ ЭЛЕКТРОННЫХ ТАБЛИЦ

IMITATION OF THE RSA «ENCRYPTION MACHINE» BY MEANS OF SPREADSHEETS

Valerii Kuminov

Student of the Russian University of Transport (MIIT) specialty "Computer security",

Russia, Moscow

АННОТАЦИЯ

В статье представлены результаты разработки наглядных материалов для применения в образовательном процессе студентов специальностей и направлений подготовки компьютерная и информационная безопасность. Приведены примеры применения электронных таблиц, в частности MS Excel для демонстрации метода RSA в целях шифрования информации.

ABSTRACT

The report presents the results of the development of visual materials for use in the educational process of students of specialties and areas of training in computer and information security. Examples of the use of spreadsheets, in particular MS Excel, are given to demonstrate the RSA method for encrypting information.

Ключевые слова: RSA, шифрование, криптография, открытый ключ, закрытый ключ.

Keywords: RSA, encryption, cryptography, public key, private key.

Статья направлена на разработку наглядных материалов для применения в образовательном процессе студентов специальностей компьютерная и информационная безопасность. Высокую наглядность представляют электронные таблицы, которые позволяют имитировать различные виды криптографических систем. В настоящем статье представлены результаты разработки шифровальной машины шифра RSA средствами MS Excel.

RSA — буквенная аббре­виатура от фамилий Rivest, Shamir и Adleman. Он является первым практическим применением придуманной Диффи Хеллманом системы шифрования с от­крытым ключом, которая повсеместно используется и по сей день. Надежность шифра практически гарантирована, потому что процесс расшифровки является невероятно сложным, почти невозможным делом. (RSA. URL: https://ru.wikipedia.org/wiki/RSA)

Пользователи RSA создают и публикуют открытые ключи на основе двух простых чисел, которые должны быть засекречены.

Любой человек может использовать открытый ключ для выполнения операции шифровки сообщений.

Математические операции, применяемые в RSA, могут быть наглядно реализованы в программе Microsoft Excel.

Представим, что Боб хочет получить от Алисы секретное сообщение. Для начала Боб создаст пару открытый и закрытый ключ. Опишем реализацию данного процесса:

Первое, что нужно сделать, это ввести в ячейки простые числа p и q (рис. 1). Далее, с помощью встроенных формул MS Excel находим n. Оно используется и в открытом, и в закрытом ключах. Значение n равно:

Теперь, нужно найти функцию Эйлера. Это очень просто, она равна:

Рисунок 1. Исходные данные

Следующее, что необходимо отыскать ­­­­– это открытый ключ, Его может знать Алиса, Боб и другие так как он не является секретным. Нужно отыскать такое e, чтобы выполнялись следующие условия:

Другими словами, e и  должны быть взаимно простыми и e не должна быть меньше 1 и не должна превышать .

Следует отметить, что открытому ключу e может удовлетворять несколько значений и можно выбирать любое значение, которое удовлетворяет упомянутому раннее условию. В MS Excel есть данная функция. Поэтому сделаем таблицу из двух столбцов, первый из которых отвечает за подбор  (от 2 до ), а второй столбец – функция НОД. Формула второго столбца будет выглядеть следующим образом:

Как видно из рисунка 2, открытый ключ для исходных данных может быть 5, 7, 11 и так далее. Пусть, Боб выбрал число 11. Внесём его к исходным данным. (рис 4)

Рисунок 2. Выбор открытого ключа

1. Теперь нужно отыскать закрытый ключ, он является совершенно секретным и может быть известен только его создателю, то есть Бобу. Для любого из выбранных ранее e, существует единственный d. (Чичикин Г. Я., Семёнов Д. А. Криптосистема RSA. РТУ г. Москва 2019г.)

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

В Excel создадим таблицу с двумя столбцами, первый из которых будет отвечать за поиск подходящей d (от 1 до n), а вторая будет содержать в себе формулу 5. Для нашей таблицы формула будет преобразована в:

Рисунок 3. Выбор закрытого ключа

Как мы видим из рисунка 3, условие закрытого ключа удовлетворяется при d = 59. Внесём его к нашим исходным данным (рисунок 4).

Рисунок 4. Открытый и закрытый ключи

И так, для Боба была создана пара открытый и закрытый ключ. Теперь он делится с Алисой открытым ключом. Она сможет зашифровать сообщение для Боба по следующей формуле:

Где m – Сообщение, c – шифр.

В MS Excel при реализации степенных выражений, возникает трудность с тем, что электронные таблицы просто не предназначены для вычисления больших чисел. Однако, никто не запрещал делать вычисления последовательно. Для этого создадим таблицу «Шифрование» и впишем в колонки открытый ключ, формулу (для наглядности) и вычисляемый результат. Первая колонка отвечает за подсчёт количества итераций. Например, если e = 11, количество вычисляемых строк будет 11. Вторая колонка служит для наглядности происходящих действий (см. рис. 5). В третьей колонке будет вычисляться результат арифметических операций. В ячейку G3 запишем следующую формулу:

Далее, в ячейку G4 мы впишем следующую формулу и растянем её до 11 строки. Где  – шифруемое сообщение, .

Рисунок 5. Шифрование сообщения

Боб получает от Алисы сообщение 4. И теперь ему необходимо его расшифровать. Он легко с этим справится, если воспользуется следующей формулой:

Создадим таблицу из трех столбцов. Первый будет отвечать за счётчик нашего закрытого ключа, который мы возводим в степень. Второй столбец отвечает за формулу 10. Так как мы будем считать результат по модулю последовательно, для этого в ячейку K3 мы внесём следующую формулу:

Где K3 – результат предыдущей операции.

.

Рисунок 6. Расшифрование сообщения

Вспомним, что закрытый ключ d = 59. Значит на 59-й итерации мы должны получить расшифрованное сообщение, что прекрасно видно на рисунке 6.

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

Список литературы:

1. Чичикин Г. Я., Семёнов Д. А. Криптосистема RSA. РТУ г. Москва 2019г.
2. RSA. URL: https://ru.wikipedia.org/wiki/RSA (дата обращения 10.04.2022)
3. Алгоритм шифрования RSA. URL: https://revolution.allbest.ru/programming/00369326_0.html (дата обращения 13.04.2022)