Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгоритм шифрування з відкритим ключем RSA
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Звіт до лабораторної роботи № 3
На тему:
“Алгоритм шифрування з відкритим ключем RSA”
Варіант №16
Мета роботи: вивчити принцип функціонування асиметричних криптосистем з відкритими ключами на прикладі RSA, дослідити числові алгоритми, що використовуються у криптографії та реалізувати алгоритмічною мовою С++ алгоритм шифрування RSA.
Завдання
На основі інструментарію Visual C++ 2005 розробити Windows Forms програму CLR для реалізації вказаного проекту алгоритму криптографічної системи з відкритими ключами RSA.
Усі окремі алгоритми (наприклад, обчислення НСД бінарним алго ритмом Евкліда) реалізувати у вигляді підпрограм (функцій).
З метою компактності у завданні вказуються лише номери алгоритмів, на основі яких потрібно реалізувати загальний проект програ ми RSA. Розшифрування номерів подаються тут:
1. Алгоритм піднесення до степеню: 1.1. Метод справа-наліво двійкового потенціювання; 1.2. Метод зліва-направо двійкового потенціювання; 1.3. Рекурсивний метод двійкового потенцію вання; 1.4. Метод вікна; 1.5. Метод змінного вікна.
2. Обч. найбільшого спільного дільника: 2.1. Алгоритм Евклі да; 2.2. Бінарний алгоритм Евкліда.
3. Обч. оберненого значення за модулем: 3.1. Розширений ал горитм Евкліда; 3.2. Розширений бінарний алгоритм Евкліда.
4. Тести визначення простоти числа: 4.1. Тест Рабіна-Мілера; 4.2. Тест Соловея-Штрасена; 4.3. Тест Лемана.
=
Алг: 1.2; 2.1; 3.1; 4.1
Теоретичні відомості
Метод зліва-направо двійкового потенціювання.
Цей метод схожий до попереднього, з тією лиш різницею, що пе ребір символів вказівника степеню він виконує, починаючи зі старшо го розряду. Якщо представити вказівник у двійковому вигляді
, , (2.11)
де – кількість розрядів , то загальний алгоритм виглядатиме так:
Мовою С++ цей алгоритм виглядає так:
// обчислення
//визначення к-сті розрядів числа x
worker = x; n_x = 1;
while (worker > 1)
{ worker = worker >> 1; n_x++; }
//маска з "1" для старшого розрдяду x
mask = 1;
mask = mask << (n_x-1);
m = 1;
while (mask)
{
m = (m*m) % n;
if (x & mask)
m = (m*a) % n;
mask = mask >> 1;
}
У цьому алгоритмі за кожен прохід циклу обробляється один біт степеню. При цьому кількість піднесень до квадрату рівна кількості розрядів числа , а загальна кількість добутків визначається кількістю його одиничних розрядів. Отже чим менша вага (кількість “1”) числа , тим алгоритм двійкового потенціювання працює швидше.
Алгоритм Евкліда.
В основі алгоритму лежить повторне ділення із залишком: обчислюємо залишок , потім і так далі, поки залишок на стане рівним нулю.
Загальний алгоритм Евкліда обчислення НСД (,) для
Мовою С++ цей алгоритм виглядає так:
// обчислення НСД (,)
while (a != 0)
{
temp = b %a;
b = a;
a = temp;
}
nsd = b;
Розширений алгоритм Евкліда.
Звичайний алгоритм Евкліда для знаходження НСД (,) зводився до послідовного ділення із залишком
, , (2.30)
де , , НСД (,).
Якщо для послідовності (2.30) провести ряд перетворень та виразити усі залишки через та , тоді
,
,
,
,
(2.31)
Таким чином, ми отримали рекурентну формулу (2.31) для зна ходження НСД (,) у вигляді лінійної комбінації чисел та з цілими числами та . Якщо числа та взаємно прості, тоді НСД (,) = 1, і відповідно
1 = НСД (,) =. (2.32)
З формули (2.32) випливає, що обернене значення .
Загальний розширений алгоритм Евкліда
обчислення оберненого значення
Мовою С++ цей алгоритм виглядає так:
// обчислення
// вхід: числа a та n, для яких треба знайти nsd= НСД (,)
long long n1, c, k, nsd, c1, c2, k1, k2, q, r;
n1 = n; //резервуємо значення n
c2 = 1; c1 = 0; k2 = 0; k1 = 1;
while(n != 0)
{
q = a/n; r = a - q*n; c = c2 - q*c1; k = k2 - q*k1;
a = n; n = r; c2 = c1; c1 = c; k2 = k1; k1 = k;
}
nsd = a; c = c2; k = k2;
// якщо аглоритм дав від’ємне значення с, тоді с = с (mod n)
if (c < 0) c += n1;
// вихід: числа nsd, c, k
// с – обернене значення за модулем n
Тест Рабіна-Мілера (Rabin-Miller).
Цей тест є модифікацією тесту Ферма та приймає складене чис ло за просте з ймовірністю 0,25 для будь-якої випадкової основи . Тому багатократне повторення тесту дає можливість зменшити ймовірність похибки до визначеної наперед.
Припустимо, що число просте. Тоді згідно малої теореми Ферма для всіх цілих чисел , не кратних , виконується рівність
. (2.33)
Квадратний корінь з може приймати лише значення 1 та -1, оскільки це єдині розв’язки рівняння . Обчислимо послідовно квадратні корені
, , … , ,
поки не отримаємо непарне число . Якщо на деякому кроці ми отримаємо залишок не рівний 1, тоді він повинен бути рівним -1, інакше число не може бути простим.
Загальний алгоритм тесту Рабіна-Мілера
Якщо отримуємо результат «число ймовірно просте», то пов торю ємо перевірку з іншою основою , а якщо – «число складене», то одразу завер шу ємо тест. Зазначимо, що після повторів цього тесту ймовірність похибки становитиме (якщо алгоритм видасть відповідь «число ймовірно є простим числом»).
Мовою С++ цей алгоритм виглядає так:
bool Test (unsigned long long p, int t) // p – вхідне число, t – к-сть тестів
{
Random^ autoRand = gcnew Random; // ств. генер-ра випадк. чисел
int m = 0;
unsigned long long s = p-1, a, b;
while (s%2 == 0)
{ s = s/2; m++; }
for (int i=0; i < t; i++)
{
a = autoRand->Next(2, p-1);
if (NSD(a, p) != 1) return true; // true -- число p складене
// NSD (a, p) – ф-ція знаходження НСД (,)
b = StepMOD(a, s, p); // ф-ція піднесення до степеню за mod
if (b == 1 || b == p-1) continue; // число p ймовірно просте
for (int l=1; l<m; l++)
{
b=StepMOD(b,2,p);
if (b == p-1) { BooL = 1; break; } // p ймовірно просте
}
if (BooL == 0) return true; // true -- число p складене
}
return false; // число p ймовірно просте
}
// якщо функція повертає false – тоді число p є ймовірно простим,
// а якщо true – число p є складеним
Остаточна версія програми
#pragma once
using namespace System::IO;
namespace Laba3 {
using namespace System;
using namespace System::ComponentModel;
using namespace System::Collections;
using namespace System::Windows::Forms;
using namespace System::Data;
using namespace System::Drawing;
/// <summary>
/// Summary for Form1
///
/// WARNING: If you change the name of this class, you will need to change the
/// 'Resource File Name' property for the managed resource compiler tool
/// associated with all .resx files this class depends on. Otherwise,
/// the designers will not be able to interact properly with localized
/// resources associated with this form.
/// </summary>
public ref class Form1 : public System::Windows::Forms::Form
{
public:
Form1(void)
{
InitializeComponent();
//
//TODO: Add the constructor code here
//
}
protected:
/// <summary>
/// Clean up any resources being used.
/// </summary>
~Form1()
{
if (components)
{
delete components;
}
}
private: System::Windows::Forms::Button^ button1;
protected:
private: System::Windows::Forms::Button^ button2;
private: System::Windows::Forms::Button^ button3;
private: System::Windows::Forms::Label^ label1;
private: System::Windows::Forms::Label^ label2;
private: System::Windows::Forms::Label^ label3;
private: System::Windows::Forms::TextBox^ textBox1;
private: System::Windows::Forms::TextBox^ textBox2;
private: System::Windows::Forms::TextBox^ textBox3;
private: System::Windows::Forms::TextBox^ textBox4;
private: System::Windows::Forms::Label^ label4;
private: System::Windows::Forms::TextBox^ textBox5;
private: System::Windows::Forms::Label^ label5;
private: System::Windows::Forms::OpenFileDialog^ openFileDialog1;
private:
/// <summary>
/// Required designer variable.
/// </summary>
System::ComponentModel::Container ^components;
#pragma region Windows Form Designer generated code
/// <summary>
/// Required method for Designer support - do not modify
/// the contents of this method with the code editor.
/// </summary>
void InitializeComponent(void)
{
this->button1 = (gcnew System::Windows::Forms::Button());
this->button2 = (gcnew System::Windows::Forms::Button());
this->button3 = (gcnew System::Windows::Forms::Button());
this->label1 = (gcnew System::Windows::Forms::Label());
this->label2 = (gcnew System::Windows::Forms::Label());
this->label3 = (gcnew System::Windows::Forms::Label());
this->textBox1 = (gcnew System::Windows::Forms::TextBox());
this->textBox2 = (gcnew System::Windows::Forms::TextBox());
this->textBox3 = (gcnew System::Windows::Forms::TextBox());
this->textBox4 = (gcnew System::Windows::Forms::TextBox());
this->label4 = (gcnew System::Windows::Forms::Label());
this->textBox5 = (gcnew System::Windows::Forms::TextBox());
this->label5 = (gcnew System::Windows::Forms::Label());
this->openFileDialog1 = (gcnew System::Windows::Forms::OpenFileDialog());
this->SuspendLayout();
//
// button1
//
this->button1->Location = System::Drawing::Point(231, 198);
this->button1->Name = L"button1";
this->button1->Size = System::Drawing::Size(124, 23);
this->button1->TabIndex = 0;
this->button1->Text = L"Генератор ключів";
this->button1->UseVisualStyleBackColor = true;
this->button1->Click += gcnew System::EventHandler(this, &Form1::button1_Click);
//
// button2
//
this->button2->Location = System::Drawing::Point(231, 236);
this->button2->Name = L"button2";
this->button2->Size = System::Drawing::Size(124, 23);
this->button2->TabIndex = 1;
this->button2->Text = L"Шифрування RSA";
this->button2->UseVisualStyleBackColor = true;
this->button2->Click += gcnew System::EventHandler(this, &Form1::button2_Click);
//
// button3
//
this->button3->Location = System::Drawing::Point(231, 276);
this->button3->Name = L"button3";
this->button3->Size = System::Drawing::Size(124, 23);
this->button3->TabIndex = 2;
this->button3->Text = L"Розшифрування RSA";
this->button3->UseVisualStyleBackColor = true;
this->button3->Click += gcnew System::EventHandler(this, &Form1::button3_Click);
//
// label1
//
this->label1->AutoSize = true;
this->label1->Location = System::Drawing::Point(204, 9);
this->label1->Name = L"label1";
this->label1->Size = System::Drawing::Size(13, 13);
this->label1->TabIndex = 3;
this->label1->Text = L"p";
//
// label2
//
this->label2->AutoSize = true;
this->label2->Location = System::Drawing::Point(204, 42);
this->label2->Name = L"label2";
this->label2->Size = System::Drawing::Size(13, 13);
this->label2->TabIndex = 4;
this->label2->Text = L"q";
//
// label3
//
this->label3->AutoSize = true;
this->label3->Location = System::Drawing::Point(204, 69);
this->label3->Name = L"label3";
this->label3->Size = System::Drawing::Size(35, 13);
this->label3->TabIndex = 5;
this->label3->Text = L"n=p*q";
//
// textBox1
//
this->textBox1->Location = System::Drawing::Point(255, 6);
this->textBox1->Name = L"textBox1";
this->textBox1->Size = System::Drawing::Size(283, 20);
this->textBox1->TabIndex = 6;
//
// textBox2
//
this->textBox2->Location = System::Drawing::Point(255, 34);
this->textBox2->Name = L"textBox2";
this->textBox2->Size = System::Drawing::Size(283, 20);
this->textBox2->TabIndex = 7;
//
// textBox3
//
this->textBox3->Location = System::Drawing::Point(255, 69);
this->textBox3->Name = L"textBox3";
this->textBox3->Size = System::Drawing::Size(283, 20);
this->textBox3->TabIndex = 8;
//
// textBox4
//
this->textBox4->Location = System::Drawing::Point(255, 105);
this->textBox4->Name = L"textBox4";
this->textBox4->Size = System::Drawing::Size(283, 20);
this->textBox4->TabIndex = 9;
//
// label4
//
this->label4->AutoSize = true;
this->label4->Location = System::Drawing::Point(204, 105);
this->label4->Name = L"label4";
this->label4->Size = System::Drawing::Size(14, 13);
this->label4->TabIndex = 10;
this->label4->Text = L"E";
//
// textBox5
//
this->textBox5->Location = System::Drawing::Point(255, 132);
this->textBox5->Name = L"textBox5";
this->textBox5->Size = System::Drawing::Size(283, 20);
this->textBox5->TabIndex = 11;
//
// label5
//
this->label5->AutoSize = true;
this->label5->Location = System::Drawing::Point(204, 135);
this->label5->Name = L"label5";
this->label5->Size = System::Drawing::Size(15, 13);
this->label5->TabIndex = 12;
this->label5->Text = L"D";
//
// openFileDialog1
//
this->openFileDialog1->FileName = L"openFileDialog1";
//
// Form1
//
this->AutoScaleDimensions = System::Drawing::SizeF(6, 13);
this->AutoScaleMode = System::Windows::Forms::AutoScaleMode::Font;
this->ClientSize = System::Drawing::Size(627, 311);
this->Controls->Add(this->label5);
this->Controls->Add(this->textBox5);
this->Controls->Add(this->label4);
this->Controls->Add(this->textBox4);
this->Controls->Add(this->textBox3);
this->Controls->Add(this->textBox2);
this->Controls->Add(this->textBox1);
this->Controls->Add(this->label3);
this->Controls->Add(this->label2);
this->Controls->Add(this->label1);
this->Controls->Add(this->button3);
this->Controls->Add(this->button2);
this->Controls->Add(this->button1);
this->Name = L"Form1";
this->Text = L"Form1";
this->ResumeLayout(false);
this->PerformLayout();
}
#pragma endregion
unsigned long long StepMOD(unsigned long long a, unsigned long long x,unsigned long long n)
{
unsigned long long m,mask,w=2,worker,n_x,f;
// обчислення
//визначення к-сті розрядів числа x
worker = x; n_x = 1;
while (worker > 1)
{ worker = worker >> 1; n_x++; }
//маска з "1" для старшого розрдяду x
mask = 1;
mask = mask << (n_x-1);
m = 1;
while (mask)
{
m = (m*m) % n;
if (x & mask)
m = (m*a) % n;
mask = mask >> 1;
}
return m;
}
unsigned long long Generator (Random^ autoRand)
{
unsigned long long p,mask;
int t=30; // t – кількість повторів тесту на простоту
bool BOOL;
do
{
BOOL = false;
p = autoRand->Next(1, 65535); // генерування наступного випадк.числа
mask = 1; p = p|1; p = p|(mask<<15); // встановл. ст. та мол. бітів в "1"
for (int i=3; i<2000; i+=2) //перевірка діленням на прості числа
if (p%i == 0) { BOOL = true; break; }
if ( !BOOL ) BOOL= Test(p,t); // ф-ція Test – тест на простоту числа p
}
while(BOOL);
return p;
}
// L
bool Test (unsigned long long p, int t) // p – вхідне число, t – к-сть тестів
{
bool Bool;
Random^ autoRand = gcnew Random; // ств. генер-ра випадк. чисел
int m = 0;
unsigned long long s = p-1, a, b;
while (s%2 == 0)
{ s = s/2; m++; }
for (int i=0; i < t; i++)
{
a = autoRand->Next(2, p-1);
if (NSD(a, p) != 1) return true; // true -- число p складене
// NSD (a, p) – ф-ція знаходження НСД ( , )
b = StepMOD(a, s, p); // ф-ція піднесення до степеню за mod
if (b == 1 || b == p-1) continue; // число p ймовірно просте
for (int l=1; l<m; l++)
{
b=StepMOD(b,2,p);
if (b == p-1) { Bool = 1; break; } // p ймовірно просте
}
if (Bool == 0) return true; // true -- число p складене
}
return false; // число p ймовірно просте
}
// якщо функція повертає false – тоді число p є ймовірно простим,
// а якщо true – число p є складеним
unsigned long long NSD (unsigned long long a, unsigned long long b)
{//ev
unsigned long long temp,nsd;
while (a != 0)
{
temp = b %a;
b = a;
a = temp;
}
nsd = b;
return nsd;
}
unsigned long long Inverse(unsigned long long a,unsigned long long n)
{// обчислення ev r
// вхід: числа a та n, для яких треба знайти nsd= НСД ( , )
long long n1, c, k, nsd, c1, c2, k1, k2, q, r;
n1 = n; //резервуємо значення n
c2 = 1; c1 = 0; k2 = 0; k1 = 1;
while(n != 0)
{
q = a/n; r = a - q*n; c = c2 - q*c1; k = k2 - q*k1;
a = n; n = r; c2 = c1; c1 = c; k2 = k1; k1 = k;
}
nsd = a; c = c2; k = k2;
// якщо аглоритм дав від’ємне значення с, тоді с = с (mod n)
if (c < 0) c += n1;
// вихід: числа nsd, c, k
// с – обернене значення за модулем n
return c;
}
private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e)
{
unsigned long long p,q,n,E,D;
Random ^ autoRand = gcnew Random;
p=Generator(autoRand);
q=Generator(autoRand);
n=p*q;
do
E=autoRand->Next(3,(p-1)*(q-1)>>1);
while (NSD (E,(p-1)*(q-1))!=1);
D=Inverse(E,(p-1)*(q-1));
textBox1->Text=p.ToString();
textBox4->Text=E.ToString();
textBox5->Text=D.ToString();
textBox2->Text=q.ToString();
textBox3->Text=n.ToString();
}
private: System::Void button2_Click(System::Object^ sender, System::EventArgs^ e)
{
String^ filename;
unsigned char p;
unsigned int m;
unsigned long long m1, c, n, E;
n = Convert::ToUInt64 (textBox3->Text);
E = Convert::ToUInt64 (textBox4->Text);
openFileDialog1->ShowDialog (); //викликаємо діалогове вікно вибору файлу
filename = openFileDialog1->FileName; //зчитуємо шлях до файлу
BinaryReader^ binReader = gcnew BinaryReader ( File::Open( filename,
FileMode::Open ) ); // створюємо об’єкт для бінарного читання з файлу
BinaryWriter^ binWriter = gcnew BinaryWriter ( File::Open( filename+".rsa",FileMode::Create ) ); // створюємо об’єкт для бінарного запису у файл
try
{
do
{
p = binReader->ReadByte(); // зчитуємо 16-бітний блок даних
m1 = static_cast<unsigned long long>(p);
c=StepMOD(m1,E,n); // обчислюємо
m = static_cast<unsigned int>(c);
binWriter->Write( m ); // запис 32-бітн. зашифр.блоку даних
}
while(1);
}
catch(...) { }
binReader->Close(); //закриваємо файл з вх.даними
binWriter->Close();
}
private: System::Void button3_Click(System::Object^ sender, System::EventArgs^ e)
{
String^ filename;
unsigned char p;
unsigned int c1;
unsigned long long m, c, n, D;
n = Convert::ToUInt64(textBox3->Text);
D = Convert::ToUInt64(textBox5->Text);
openFileDialog1->ShowDialog ();
filename = openFileDialog1->FileName;
BinaryReader^ binReader = gcnew BinaryReader ( File::Open( filename,
FileMode::Open ) );
BinaryWriter^ binWriter = gcnew BinaryWriter ( File::Open( filename->
Replace(".rsa",""), FileMode::Create ) );
try
{
do
{
c1 = binReader->ReadUInt32(); // зчит. 32-бітн.блок шифр. даних
c = static_cast<unsigned long long>(c1);
m=StepMOD(c,D,n); // обчислюємо
p = static_cast<unsigned char>(m);
binWriter->Write( p ); // запис 16-бітного блоку розшифр.даних
}
while(1);
}
catch(...) { }
binReader->Close ();
binWriter->Close ();
}
};
}
Результат виконання програми:
Висновок: вивчивши принцип функціонування асиметричних криптосистем з відкритими ключами на прикладі RSA, дослідив числові алгоритми, що використовуються у криптографії та реалізувати алгоритмічною мовою С++ алгоритм шифрування RSA.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора