Алгоритм шифрування з відкритим ключем RSA. Звіт до лабораторної роботи з Інші. Робота № 522563

Алгоритм шифрування з відкритим ключем RSA

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

КН

Кафедра:

Не вказано

Інформація про роботу

Рік:

2013

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Інші

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти та науки України Національний університет “Львівська політехніка” Звіт до лабораторної роботи № 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.

Звіт до лабораторної роботи Інші

31.03.2013 13:53

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись