Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
🚀 Вийди на новий рівень крипто-торгівлі!
Easy Trade Bot — автоматизуй свій прибуток уже зараз!
Ми пропонуємо перелік перевірених прибуткових стратегій на такі пари як BTC, DOT, TRX, AAVE, ETH, LINK та інші. Ви можете підключити автоматичну торгівлю на своєму акаунті Binance або отримувати торгові рекомендації на email у режимі реального часу. Також можемо створити бота для обраної вами монети.
Всі результати торгів ботів доступні для перегляду у зручних таблицях на головній сторінці. Швидко, динамічно та прозоро!
Алгоритм шифрування з відкритим ключем RSA
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2008
Тип роботи:
Звіт
Предмет:
Інші
Група:
КС-33
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Звіт до лабораторної роботи № 3
На тему:
“Алгоритм шифрування з відкритим ключем RSA”
Варіант №4
Мета роботи: вивчити принцип функціонування асиметричних криптосистем з відкритими ключами на прикладі 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. Тест Лемана.
Файл #6
Алг: 1.4; 2.1; 3.1;
Теоретичні відомості
Метод вікна.
У більшості випадках, піднесення до квадрату виконується швидше, аніж загальне множення. І відповідно, для того щоби ще більше скоротити час обчислень, варто спробувати зменшити кількість загальних добутків. Це є можливим при використанні техніки вікон, яка використовує наперед обчислені значення.
Ідея методу базується на виборі для показника степеню осно ви системи числення більшої 2. З практичної точки зору основа вибирається рівною степеню двійки: .
У віконному методі за один раз враховується символів вказівника степеню. Спершу обчислюється та запам’ятовується таблиця значень , , … ,
, для
де – ширина вікна.
Далі записуємо число у системі числення за основою
,
де – кількість розрядів у системі числення за основою .
Алгоритм Евкліда.
В основі алгоритму лежить повторне ділення із залишком: обчислюємо залишок , потім і так далі, поки залишок на стане рівним нулю.
Загальний алгоритм Евкліда обчислення НСД (,) для
Мовою С++ цей алгоритм виглядає так:
// обчислення НСД (,)
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
Остаточна версія програми
#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^ 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->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);
//
// button3
//
this->button3->Location = System::Drawing::Point(231, 236);
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->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,base,w,n_x,worker,f;
// обчислення
// заповнення значень
base =1; // основа системи числення для вікна w
for (int i=0; i<w; i++)
base *= 2;
unsigned long long *A = new unsigned long long [base];
A[0] = 1; // обчислення таблиці значень
for (int i=1; i<base; i++)
A[i] = (A[i-1]*a)%n;
// визначення к-сті розрядів числа x за основою base
worker = x; n_x = 1;
while (worker > base-1)
{ worker = worker / base; n_x++; }
// перевід з 10 системи числення у систему з основою base
int *x_base = new int [n_x];
for (int i=0; i<n_x; i++)
{ x_base[i] = x % base; x /= base; }
// основний алгоритм
m = 1;
for (int i=n_x-1; i>=0; i--)
{
for (int j=0; j<w; j++)
m = (m*m)%n;
f = x_base[i];
m = (m*A[f])%n;
}
delete [ ] A; delete [ ] x_base;
return m ;
}
unsigned long long NSD (unsigned long long a, unsigned long long b)
{
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)
{
// обчислення
// вхід: числа 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, i = 3;
E = Convert::ToUInt64(textBox4->Text);
n = Convert::ToUInt64(textBox3->Text);
while(i <= n)
{
if (n%i == 0) break;
i += 2;
}
p = i; q = n/p;
D = Inverse (E, (p-1)*(q-1)); // ф-ція обчислення оберненого за mod
// далі виконуємо вивід чисел p, q, D
// у відповідні їм елементи керування textBox
textBox1->Text=p.ToString();
textBox4->Text=E.ToString();
textBox5->Text=D.ToString();
textBox2->Text=q.ToString();
textBox3->Text=n.ToString();
}
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 ();
}
};
}
Результат виконання програми:
Програма успішно розшифрувала вміст файлу #6:
Прості числа
p=42397
q=44179
Відкритий ключ
E=572802311
Секретний ключ
D=69245735
Основа
n=1873057063
А слово – струм.
А слово – зброя.
А віще слово – вічове.
Ліна КОСТЕНКО
Висновок: вивчивши принцип функціонування асиметричних криптосистем з відкритими ключами на прикладі RSA, дослідив числові алгоритми, що використовуються у криптографії та реалізувати алгоритмічною мовою С++ алгоритм шифрування RSA.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора