Файл: Лабораторная работа 1 Тема Алгоритм rsa Выполнили Молчанов А. Д. Пивоваров К. Д. Бакерина Е. И. Принял Хабаров А. Р.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.01.2024
Просмотров: 50
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение
высшего образования
«Тверской государственный технический университет»
(ТвГТУ)
Кафедра ЭВМ
Дисциплина «Методы и средства защиты информации»
Лабораторная работа №1
Тема: «Алгоритм RSA»
Выполнили: Молчанов А.Д.
Пивоваров К.Д.
Бакерина Е.И.
Принял: Хабаров А. Р.
____________________
Тверь, 2022
Оглавление
Цель работы 1
Теоретическая часть 1
Ход работы 3
Результат работы программы 3
Вывод 3
Цель работы
Разработать программу, имитирующую шифрование и расшифрование по алгоритму RSA.
Задачи
-
Составить алгоритм программы, включающий в себя
-
алгоритм определения простоты числа; -
алгоритм определения взаимной простоты двух чисел; -
алгоритм возведения числа в степень по модулю.
-
Написать программу по алгоритму; -
Получить результаты работы программы.
Теоретическая часть
Алгоритм RSA (Rivest, Shamir и Adleman) основан на использовании двух ключей – открытого (публичного) и закрытого (секретного). Его криптостойкость основывается на сложности разложения на множители больших чисел, а именно - на исключительной трудности задачи определить секретный ключ на основании открытого, так как для этого потребуется решить задачу о существовании делителей целого числа. Наиболее криптостойкие системы используют 1024-битовые и большие числа.
Суть алгоритма RSA:
-
Выбираются два очень больших простых числа p и q. -
Рассчитывается
. -
Выбирается большое случайное число d, взаимно простое
. -
Определяется число
, для которого выполняется условие 
. -
В результате генерируются ключи: открытый
и закрытый 
. Чтобы зашифровать данные необходимо: -
Разбить шифруемый текст на блоки, каждый из которых может быть представлен как
. -
Зашифровать текст как последовательность чисел
по формуле 
. -
Расшифровка с помощью секретного ключа по формуле 
.
Ход работы
Рисунок 1. Алгоритм проверки на простоту методом перебора делителей
Рисунок 2. Алгоритм Евклида для нахождения НОД для определения взаимной простоты двух чисел
Рисунок 3. Алгоритм возведения в степень по модулю методом понижения порядка
Результат работы программы
Рисунок 1. Запуск программы
Рисунок 2. Ввод текста, который нужно зашифровать
Рисунок 3. Ввод простых чисел
Рисунок 11. Зашифрованная фраза
Рисунок 12. Расшифровка полученных значений в текст
Исходный код
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Windows.Forms;
using System.Numerics;
namespace Laba1
{
public partial class Form1 : Form
{
char[] characters = new char[] {'#', 'А', 'Б', 'В', 'Г', 'Д', 'Е', 'Ё', 'Ж',
'З', 'И', 'Й', 'К', 'Л', 'М', 'Н', 'О', 'П',
'Р', 'С', 'Т', 'У', 'Ф', 'Х', 'Ц', 'Ч', 'Ш',
'Щ', 'Ь', 'Ы', 'Ъ', 'Э', 'Ю', 'Я', ' ', '1',
'2', '3', '4', '5', '6', '7', '8', '9', '0' };
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
Process.Start("in.txt");
}
//зашифровать
private void buttonEncode_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 (ProstoeChislo(p) && ProstoeChislo(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
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!");
}
//расшифровать
private void buttonDecode_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
StreamReader sr = new StreamReader("out1.txt");
while (!sr.EndOfStream)
{
input.Add(sr.ReadLine());
}
sr.Close();
string result = RSA_Decode(input, d, n);
StreamWriter sw = new StreamWriter("out2.txt");
sw.WriteLine(result.ToLower());
sw.Close();
Process.Start("out2.txt");
}
else
MessageBox.Show("Введите секретный ключ!");
}
//проверка: простое ли число?
private bool ProstoeChislo(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;
}
//зашифровать
private List
{
List
BigInteger chislo;
for (int i = 0; i < s.Length; i++)
{
int index = Array.IndexOf(characters, s[i]);
chislo = new BigInteger(index) + (i * characters.Length);
chislo = BigInteger.Pow(chislo, (int)e);
BigInteger n_ = new BigInteger((int)n);
chislo = chislo % n_;
result.Add(chislo.ToString());
}
return result;
}
//расшифровать
private string RSA_Decode(List
{
string result = "";
BigInteger chislo;
int i = 0;
foreach (string item in input)
{
chislo = new BigInteger(Convert.ToDouble(item));
chislo = BigInteger.Pow(chislo, (int)d);
BigInteger n_ = new BigInteger((int)n);
chislo = chislo % n_;
int index = Convert.ToInt32(chislo.ToString()) - (i * characters.Length);
result += characters[index].ToString();
i++;
}
return result;
}
//вычисление параметра d. d должен быть взаимно простым с m = (p - 1) * (q - 1)
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
private long Calculate_e(long d, long m)
{
long e = d+1;
while (true)
{
if ((e * d) % m == 1)
break;
else
e++;
}
return e;
}
}
}
Вывод
Построена блок-схема алгоритма работы программы. Написан исходный код и показана работа программы.