Алгоритм RSA

В этой статье рассмотрим еще один один алгоритм шифрования – алгоритм RSA. Будет приведено описание и программная реализация на языке программирования C#.

Алгоритм RSA. Описание

RSA (аббревиатура от фамилий создателей: Rivest, Shamir и Adleman) – один из самых популярных алгоритмов шифрования. Сначала приведем несколько определений:

mod – операция взятия остатка от деления.

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

Шаги алгоритма RSA

Теперь опишем последовательность шагов алгоритма RSA:

  • выбрать два больших простых числа p и q;
  • вычислить: n = p ⋅ q, m = (p – 1) ⋅ (q – 1);
  • выбрать случайное число d, взаимно простое с m;
  • определить такое число e, для которого является истинным выражение: (e ⋅ d) mod (m) = 1;
  • числа e и n – это открытый ключ, а числа d и n – это закрытый ключ;

На практике это означает следующее: открытым ключом зашифровывают сообщение, а закрытым – расшифровывают. Пара чисел закрытого ключа держится в секрете.

  • разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа M(i);

Обычно блок берут равным одному символу и представляют этот символ в виду числа – его номера в алфавите или кода в таблице символов (например ASCII или Unicode).

  • шифрование алгоритмом RSA производится по формуле: C(i) = (M(i)e) mod n;
  • расшифровка сообщения производится с помощью формулы: M(i) = (C(i)d) mod n.

Алгоритм RSA. Программная реализация

Программа для шифрования алгоритмом RSA имеет интерфейс, представленный на рисунке 1.

RSA - Пользовательский интерфейс программы

Рисунок 1. Пользовательский интерфейс программы

В программе будем использовать следующий алфавит:

Число M(i) для конкретной буквы будет равно её номеру в массиве characters[].

Приведем код кнопки “Зашифровать”:

И кнопки “Расшифровать”:

Теперь покажем код остальных методов.

Проверка: является ли число простым?

Метод, выполняющий шифрование строки алгоритмом RSA:

При возведении числа в степень в данном случае получаются очень большие числа, которые не помещаются ни в один из стандартных типов. Поэтому для их хранения используется экземпляр класса BigInteger. Этот класс позволяет хранить целые числа произвольной (любой) длины и выполнять математические операции с ними.

Метод, выполняющий расшифровку строки алгоритмом RSA:

Вычисление параметра d (d должно быть взаимно простым с m).

Метод, вычисляющий значение параметра e.

RSA – демонстрация работы программы и исходник

На рисунках 2 и 3 представлены скриншоты с демонстрацией работы программы шифрования алгоритмом RSA.

демонстрация работы программы RSA

Рисунок 2. Демонстрация работы программы

Входные и выходные данные RSA

Рисунок 3. Входные и выходные данные

Исходник программы на языке C# можно скачать, нажав на кнопку:

Скачать исходник

 

 

Алгоритм RSA
5 (100%) 4 votes

Поделиться в соц. сетях:

5 комментария(ев) к статье “Алгоритм RSA

  1. Илья

    Выдает ошибку в методе расшифровки: result += characters[index].ToString();(пишет индекс находился вне границ массива
    )

      1. Илья

        На входе документ блокнот. Я код использовал полностью. Шифрует он почему то одинаковыми числами, причем одни минус единицы и 306. Мне кажется проблема в этой минус единице, именно из за нее проблема с выходом из массива. Подскажите пожалуйста просто вот прошу. Благодарен буду всю жизнь. И можете пожалуйста сказать какие именно данные должны быть на входе. Может шрифт особенный.

          1. admin Автор статьи

            Для начала попробуйте у входного текстового файла изменить кодировку на UTF-8 (без BOM) – сделать это можно с помощью программы Notepad++: в верхнем меню кнопка “Кодировки” -> “Преобразовать в UTF-8 без BOM”.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">