Алгоритм RSA

Отчет по лабораторной работе № 1

По дисциплине: Методы и средства защита информации

На тему: Алгоритм RSA

Выполнил: студент группы

2020

Цель работы: Разработать программное обеспечение позволяющее осуществлять шифрование и дешифрование информации.

1. Алгоритм RSA

Метод RSA(Rivest Shamir Adlemar)

Суть метода RSA:

1. Выбирается 2 очень больших простых числа p,q
2. Определяется число n=pq
3. Выбирается большое случайное число d, которое должно быть взаимно простым с числом (p-1)(q-1)
4. Определяется число e, для которого является истинным соотношение [pic 1]

[pic 2] - открытый ключ

[pic 3] - закрытый ключ

Для того чтобы шифровать данные с помощью [pic 4] необходимо:

1. Разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа [pic 5]
2. Зашифровать текст рассматриваемый как последовательность чисел [pic 6] по формуле:

[pic 7]

1. Для расшифровки этих данных используется секретный ключ [pic 8]. Расшифровка производится по следующей формуле:

[pic 9]

2.  Алгоритмы

1.  Алгоритм нахождения простого числа

1. Алгоритм Миллера — Рабина

Ввод: m > 2, нечётное натуральное число, которое необходимо проверить на простоту;

       r — количество раундов.

Вывод: составное, означает, что m является составным числом;

       вероятно простое, означает, что m с высокой вероятностью является простым числом.

Представить m − 1 в виде 2s·t, где t нечётно, можно сделать последовательным делением m - 1 на 2.

цикл А: повторить r раз:

   Выбрать случайное целое число a в отрезке [2, m − 2]

   x ← at mod m, вычисляется с помощью алгоритма возведения в степень по модулю

   если x = 1 или x = m − 1, то перейти на следующую итерацию цикла А

   цикл B: повторить s − 1 раз

      x ← x2 mod m

      если x = 1, то вернуть составное

      если x = m − 1, то перейти на следующую итерацию цикла A

   вернуть составное

вернуть вероятно простое

2.  Алгоритм нахождения взаимно простых чисел

Алгоритм Евклида

1. Исходные числа a и b
2. Вычислить r - остаток от деления a на b: a = b * q + r
3. Если r = 0, то b - искомое число (наибольший общий делитель), конец
4. Заменить пару чисел парой , перейти к пункту 2

3.  Алгоритм нахождения остатка от деления

x=a(a(ad (mod m))(mod m))(mod m)...

4.  Исходный текст программы

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.Windows.Forms;

namespace lab1

{

    public partial class Form1 : Form

    {

        public Form1()

        {

            InitializeComponent();

        }

        private int VzaipProst(int a) //Взаимно простые числа

        {

            Random R = new Random();

            while (true)

            {

                a = 20;

                int b = R.Next(100, 250);

                int m = b;

                while (true)