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