Эту часть можно не читать. Итак это моя первая статья, по этому просьба сильно не пинать, но и критику буду рад услышать. Так же я решил сразу реализовывать математические функции на языке C# (код скорее всего не один из лучших), работа в консольной форме. Необходимо для работы: 1. Начальные знания языка C#. 2. Начальные знания математики(умножать, делить, и т.д.), Предварительные знания(функции) Модуль числа. Модуль числа - обозначается число-1 mod(число-2) (оператор % в C#) вычисляет остаток после деления первого операнда на второй. Пример: Теперь проделаем то же самое в C# (с выводом результатов на экран) Пример C#: Code: Console.WriteLine("{0} mod({1}) = {2} , так как {0} делим на {1}, остаток {2}", 5, 1, 5 % 1); Console.WriteLine("{0} mod({1}) = {2} , так как {0} делим на {1}, остаток {2}", 5, 2, 5 % 2); Console.WriteLine("{0} mod({1}) = {2} , так как {0} делим на {1}, остаток {2}", 5, 3, 5 % 3); Console.WriteLine("{0} mod({1}) = {2} , так как {0} делим на {1}, остаток {2}", 5, 4, 5 % 4); Console.WriteLine("{0} mod({1}) = {2} , так как {0} делим на {1}, остаток {2}", 5, 5, 5 % 5); Простое число. Простое число - число которое делится только на единицу и на саму себя. Ниже приведен пример поиска простого числа от 1 до 10. Пример: Пример C#: Code: bool b1 = true; for (int i = 1; i <= 10; i++) { for (int i1 = 2; i1 < i; i1++) { if (i % i1 == 0) { b1 = false; } } if (b1 == true) { Console.WriteLine(i.ToString()); } b1 = true; } Функция для возведения в числа степень по модулю. В связи с тем что при возведение в "большую" степень могут возникнуть проблемы при возведении стандартными методами, так как типы данных имеют свои ограничения. Поэтому и возникает необходимость в этой функции. Пример C#: Code: static uint Stepen(uint chislo, uint stepen, uint N) { uint n = 0; uint output = 1; while (n < stepen) { output = (output * chislo) % N; n++; } return output; } Функция Эйлера. Взаимно простые числа а и в если их НОД(а, в) = 1 Примеры: НОД(24,64) = 8 (не взаимно простые) НОД(4,9) = 1 (взаимно простые, хоть каждый из них не является простым, но друг с другом они простые) Функция Эйлера показывает сколько существуют взаимно простых чисел с числом a, в ряд чисел от 1..а-1 Пример C#: Code: static uint[] Eiler(uint a) { uint n = 1; uint k = 0; uint[] K1 = new uint[a]; while (n < a) { if (gcd(n, a) == 1) { K1[k] = n; k++; } n++; } uint[] V = new uint[k]; for (int i = 0; i < k; i++) { V[i] = K1[i]; } return V; } НОД НОД - Наибольший Общий Делитель - я не буду писать что это, думаю многие из читающих и так это знают, я лишь напишу, как его находить методом Эвклида. Формула и немножко теории: НОД (а, b) Далее разберу по шагам Если честно говорить то по формулам, я сам мало что понял, но когда показали на примере, то сразу все стало на свои места. Так что Пример № 1: Пример № 2: Пример C#: Code: static uint gcd(uint a, uint b) { uint c1, c2; if (a > b) { c2 = a; c1 = b; } else { c1 = b; c2 = a; } uint r = 1; while (r != 0) { r = c2 % c1; c2 = c1; c1 = r; } return c2; } Обратный элемент. Теория. Обратный элемент a группы G, это элемент b, при котором соблюдается условие a * b = e, где e единичный элемент. Практика нахождения обратных элементов руками. Пример: G = 19 Найдем вспомогательные элементы (по принципу 1+19+..+19) 1, 20, 39, 58, 77, 96, 115, 134, 153.(если этих значений не хватит, то продолжим список позже) теперь строим таблицу значений первая строка элементы группы, вторая обратные элементы. элемент 0 не учитывается, элементам 1-му и последнему присваиваем обратный элемент такой же как и сам элемент. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 1, 10, 13, 5, 4, 16, 11, 12, 17, 2, 7, 8, 3 , 15, 14, 6, 9, 18 теперь объясню на первом значение почему обратный элемент равен 10 начинаем элемент 2 умножаем на каждое значение в группе, если результат совпадет со вспомогательными элементами значит это и есть обратный элемент. 2*2=4 неподходит 2*3=6 неподходит 2*4=8 неподходит 2*5=10 неподходит 2*6=12 неподходит 2*7=14 неподходит 2*8=16 неподходит 2*9=18 неподходит 2*10=20 подходит число 20 присутствует в вспомогательных элементах, значит это и есть обратный элемент. Пример C#: Code: static uint inverse(uint e, uint N) { uint n = 1; uint d = 0; while (n < N) { if ((n * e) % N == 1) { d = n; break; } n++; } return d; } Все на этом предварительная часть завершена. Алгоритм шифрования/дешифрования RSA Итак начну с того что это один из известных асимметричных алгоритмов. Асимметричен потому, что ключи для шифрования и дешифрования разные. Реализация алгоритма (параллельно буду реализовывать в программе): Прежде чем приступать к самому алгоритму создадим новый проект ConsoleApplication (я использовал язык C#, среда Visual Studio 2010). И добавим все необходимые функции в наш проект как показано ниже. Code: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; using System.Threading; using System.Threading.Tasks; using System.Diagnostics; namespace ConsoleApplication2 { class Program { /* входные параметры: 1. число которое нужно возвести в степень. 2. число степени. 3. параметр N ниже он будет определен. */ static uint Stepen(uint chislo, uint stepen, uint N) { uint n = 0; uint output = 1; while (n < stepen) { output = (output * chislo) % N; n++; } return output; } /* входные параметры: 1. число. 2. число. */ static uint gcd(uint a, uint b) { uint c1, c2; if (a > b) { c2 = a; c1 = b; } else { c1 = b; c2 = a; } uint r = 1; while (r != 0) { r = c2 % c1; c2 = c1; c1 = r; } return c2; } /* входные параметры: 1. число для поиска с ним взаимо простых */ static uint[] Eiler(uint a) { uint n = 1; uint k = 0; uint[] K1 = new uint[a]; while (n < a) { if (gcd(n, a) == 1) { K1[k] = n; k++; } n++; } uint[] V = new uint[k]; for (int i = 0; i < k; i++) { V[i] = K1[i]; } return V; } /* входные параметры: 1. элемент для которого нужно найти обратный элемент. 2. параметр N ниже он будет определен. */ static uint inverse(uint e, uint N) { uint n = 1; uint d = 0; while (n < N) { if ((n * e) % N == 1) { d = n; break; } n++; } return d; } static void Main(string[] args) { } } } Алгоритм RSA состоит из следующих пунктов: 1. Выбрать простые числа p и q Code: uint p1 = 97; uint p2 = 89; 2. Вычислить N = p * q Code: uint N = p1 * p2; 3. Вычислить N1 = (p - 1) * (q - 1) Code: uint N1 = (p1 - 1) * (p2 - 1); Console.WriteLine("N = " + N); // Выводим на экран значения Console.WriteLine("N1 = " + N1); // Выводим на экран значения 4. Выбрать число e взаимно простое с N1 Code: [/B] uint[] K = Eiler(N1); for (int i = 0; i < K.Length; i++) { Console.WriteLine(K[i].ToString()); } Console.Write("e = "); uint e = Convert.ToUInt32(Console.ReadLine());// выбираем из списка любое значение и пишем его 5. Выбрать число d так, чтобы d * e = 1 (mod m) Code: uint d = inverse(e, N1);// ищем обратный элемент Console.WriteLine("d = " + d);// выводим его на экран Дальше самое интересное: Для зашифровки используем формулу. C=(M^e)mod N где М - это наше сообщение (в числовом виде) Теперь напишем функцию в нашей программе со всеми ранее вспомогательными (а если быть точнее, то только с одной): Code: static uint crypt(uint message, uint e, uint N) { uint c = 0; c = Stepen(message, e, N); return c; } Для дешифровки используем формулу: M = (C^d) mod N Code: static uint decrypt(uint c, uint d, uint N) { uint message = 0; message = Stepen(c, d, N); return message; } Ну вот собственно и все ниже привожу полный код программы, ее можно доработать, так как Вам удобней. Code: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; using System.Threading; using System.Threading.Tasks; using System.Diagnostics; namespace ConsoleApplication2 { class Program { static uint Stepen(uint chislo, uint stepen, uint N) { uint n = 0; uint output = 1; while (n < stepen) { output = (output * chislo) % N; n++; } return output; } static uint gcd(uint a, uint b) { uint c1, c2; if (a > b) { c2 = a; c1 = b; } else { c1 = b; c2 = a; } uint r = 1; while (r != 0) { r = c2 % c1; c2 = c1; c1 = r; } return c2; } static uint[] Eiler(uint a) { uint n = 1; uint k = 0; uint[] K1 = new uint[a]; while (n < a) { if (gcd(n, a) == 1) { K1[k] = n; k++; } n++; } uint[] V = new uint[k]; for (int i = 0; i < k; i++) { V[i] = K1[i]; } return V; } static uint inverse(uint e, uint N) { uint n = 1; uint d = 0; while (n < N) { if ((n * e) % N == 1) { d = n; break; } n++; } return d; } static uint crypt(uint message, uint e, uint N) { uint c = 0; c = Stepen(message, e, N); return c; } static uint decrypt(uint c, uint d, uint N) { uint message = 0; message = Stepen(c, d, N); return message; } static void Main(string[] args) { uint p1 = 97; // это то самое простое число uint p2 = 89; // это другое простое число uint N = p1 * p2; uint N1 = (p1 - 1) * (p2 - 1); Console.WriteLine("N = " + N); Console.WriteLine("N1 = " + N1); uint[] K = Eiler(N1); for (int i = 0; i < K.Length; i++) { Console.WriteLine(K[i].ToString()); } Console.Write("e = "); uint e = Convert.ToUInt32(Console.ReadLine()); uint d = inverse(e, N1); Console.WriteLine("d = " + d); Console.Write("M = "); uint M = Convert.ToUInt32(Console.ReadLine()); uint c = crypt(M, e, N); Console.WriteLine("c = " + c.ToString()); uint m = decrypt(c, d, N); Console.WriteLine("m = " + m.ToString()); Console.ReadLine(); } } } Всем спасибо за внимание. автор статьи cel1697i845 (то есть я)
Новички все равно не врубятся, а знающие поймут. Внимание вопрос: зачем тогда писать в начале статьи, зачем эта "лабудень"?
Внимание ответ: Я не говорил "зачем", я говорил "о чем", разницу чуешь? достаточно было в начале написать что-то вроде "реализация алгоритма RSA на шарпе", дабы не возникало ни у кого что это за статья
Приятно видеть кодеров на ачате), приятно знать, что кто то еще в теме и работает. Респект этим ребятам, респект ТС.
