В этой статье рассмотрим еще один один алгоритм шифрования — алгоритм 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.
Рисунок 1. Пользовательский интерфейс программы
В программе будем использовать следующий алфавит:
|
1 2 3 4 5 |
char[] characters = new char[] { '#', 'А', 'Б', 'В', 'Г', 'Д', 'Е', 'Ё', 'Ж', 'З', 'И', 'Й', 'К', 'Л', 'М', 'Н', 'О', 'П', 'Р', 'С', 'Т', 'У', 'Ф', 'Х', 'Ц', 'Ч', 'Ш', 'Щ', 'Ь', 'Ы', 'Ъ', 'Э', 'Ю', 'Я', ' ', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0' }; |
Число M(i) для конкретной буквы будет равно её номеру в массиве characters[].
Приведем код кнопки «Зашифровать»:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
private void buttonEncrypt_Click(object sender, EventArgs e) { if ((textBox_p.Text.Length > 0) && (textBox_q.Text.Length > 0)) { long p = Convert.ToInt64(textBox_p.Text); long q = Convert.ToInt64(textBox_q.Text); if (IsTheNumberSimple(p) && IsTheNumberSimple(q)) { string s = ""; StreamReader sr = new StreamReader("in.txt"); while (!sr.EndOfStream) { s += sr.ReadLine(); } sr.Close(); s = s.ToUpper(); long n = p * q; long m = (p - 1) * (q - 1); long d = Calculate_d(m); long e_ = Calculate_e(d, m); List<string> result = RSA_Endoce(s, e_, n); StreamWriter sw = new StreamWriter("out1.txt"); foreach (string item in result) sw.WriteLine(item); sw.Close(); textBox_d.Text = d.ToString(); textBox_n.Text = n.ToString(); Process.Start("out1.txt"); } else MessageBox.Show("p или q - не простые числа!"); } else MessageBox.Show("Введите p и q!"); } |
И кнопки «Расшифровать»:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
private void buttonDecipher_Click(object sender, EventArgs e) { if ((textBox_d.Text.Length > 0) && (textBox_n.Text.Length > 0)) { long d = Convert.ToInt64(textBox_d.Text); long n = Convert.ToInt64(textBox_n.Text); List<string> input = new List<string>(); StreamReader sr = new StreamReader("out1.txt"); while (!sr.EndOfStream) { input.Add(sr.ReadLine()); } sr.Close(); string result = RSA_Dedoce(input, d, n); StreamWriter sw = new StreamWriter("out2.txt"); sw.WriteLine(result); sw.Close(); Process.Start("out2.txt"); } else MessageBox.Show("Введите секретный ключ!"); } |
Теперь покажем код остальных методов.
Проверка: является ли число простым?
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
private bool IsTheNumberSimple(long n) { if (n < 2) return false; if (n == 2) return true; for (long i = 2; i < n; i++) if (n % i == 0) return false; return true; } |
Метод, выполняющий шифрование строки алгоритмом RSA:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
private List<string> RSA_Endoce(string s, long e, long n) { List<string> result = new List<string>(); BigInteger bi; for (int i = 0; i < s.Length; i++) { int index = Array.IndexOf(characters, s[i]); bi = new BigInteger(index); bi = BigInteger.Pow(bi, (int)e); BigInteger n_ = new BigInteger((int)n); bi = bi % n_; result.Add(bi.ToString()); } return result; } |
При возведении числа в степень в данном случае получаются очень большие числа, которые не помещаются ни в один из стандартных типов. Поэтому для их хранения используется экземпляр класса BigInteger. Этот класс позволяет хранить целые числа произвольной (любой) длины и выполнять математические операции с ними.
Метод, выполняющий расшифровку строки алгоритмом RSA:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
private string RSA_Dedoce(List<string> input, long d, long n) { string result = ""; BigInteger bi; foreach (string item in input) { bi = new BigInteger(Convert.ToDouble(item)); bi = BigInteger.Pow(bi, (int)d); BigInteger n_ = new BigInteger((int)n); bi = bi % n_; int index = Convert.ToInt32(bi.ToString()); result += characters[index].ToString(); } return result; } |
Вычисление параметра d (d должно быть взаимно простым с m).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
private long Calculate_d(long m) { long d = m - 1; for (long i = 2; i <= m; i++) if ((m % i == 0) && (d % i == 0)) //если имеют общие делители { d--; i = 1; } return d; } |
Метод, вычисляющий значение параметра e.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
private long Calculate_e(long d, long m) { long e = 10; while (true) { if ((e * d) % m == 1) break; else e++; } return e; } |
RSA – демонстрация работы программы и исходник
На рисунках 2 и 3 представлены скриншоты с демонстрацией работы программы шифрования алгоритмом RSA.
Рисунок 2. Демонстрация работы программы
Рисунок 3. Входные и выходные данные
Исходник программы на языке C# можно скачать, нажав на кнопку:
Скачать исходник
Поделиться в соц. сетях:
Выдает ошибку в методе расшифровки: result += characters[index].ToString();(пишет индекс находился вне границ массива
)
Какие входные данные?
На входе документ блокнот. Я код использовал полностью. Шифрует он почему то одинаковыми числами, причем одни минус единицы и 306. Мне кажется проблема в этой минус единице, именно из за нее проблема с выходом из массива. Подскажите пожалуйста просто вот прошу. Благодарен буду всю жизнь. И можете пожалуйста сказать какие именно данные должны быть на входе. Может шрифт особенный.
Может как то надо блокнот настроить
Для начала попробуйте у входного текстового файла изменить кодировку на UTF-8 (без BOM) — сделать это можно с помощью программы Notepad++: в верхнем меню кнопка «Кодировки» -> «Преобразовать в UTF-8 без BOM».
Если у кого такая проблема будет — это проблемы с кирилицей при считывании с файла, после выражение
Array.IndexOf(characters, s[i])
попытается найти кракозябру в массиве, её там нет и результат «-1».
Что бы решить эту проблему надо добавить кодировку в параметр StreamReader-а: new StreamReader(«in.txt», Encoding.GetEncoding(1251));
Возникла такая ситуация, что при выводе в out2.txt последнее слово первой строки сливается с первым второй строки. С чем это может быть связано?
Попробуйте в конце первой строки поставить пробел.
Откуда взялся метод BigInteger? Он нигде не описан, а среда предлагает создать новый класс.
BigInteger — это структура из пространства имен System.Numerics, входящего в .NET Framework. Она позволяет работать с целыми числами произвольно большого размера.
Как сделать, чтобы прописные буквы расшифровывались прописными, а не заглавными?
Попробуйте добавить в алфавит прописные буквы и уберите из кода выражение:
s = s.ToUpper();
Супер! Чуть перепутаны d и e, но в целом все люкс, благодарю! Спасли от монотонной работы!