Міністерство освіти і науки України Національний університет «Львівська Політехніка» Інститут комп’ютерних технологій автоматики та метрології Кафедра Безпеки Інформаційних Технологій
Звіт Про виконання лабораторної роботи № 5 “Криптографічні системи та протоколи” Львів 2012 Мета роботи: Вивчити математичні основи побудови алгоритму шифрування RSA, методи криптоаналізу та вимоги до стійкості алгоритму RSA, навчитися розробляти програмне забезпечення для шифрування та цифрового підпису з використанням алгоритму RSA. Теоретичні відомості Безпека RSA базується на складності розкладу на множники великих чисел. Відкритий та закритий ключі є функціями двох великих (більше двохсот десяткових розрядів) простих чисел. Відновлення відкритого тексту за шифротекстом і відкритим ключем еквівалентне розкладу на множники двох великих чисел. Для генерації двох ключів використовуються два великих випадкових простих числа p і q однакової довжини. Розширений алгоритм Евкліда використовується для обчислення ключа розшифрування d такого, що ed=1(mod(p-1)(q-1)). (1) Іншими словами d=e-1mod((p-1)(q-1)) (2) d і n=pq є взаємно простими числами. Числа e і n – це відкритий ключ, а число d – закритий. Для шифрування повідомлення m воно спочатку розбивається на цифрові блоки, які менші за n (для двійкових даних вибирається найбільший степінь числа 2, менший за n). А саме, якщо p і q – 100-розрядні прості числа, то n буде мати приблизно 200 розрядів і кожен блок повідомлення mi повинен мати також приблизно 200 розрядів. Зашифроване повідомлення c буде складатися з блоків ci такої ж довжини. Формула шифрування має вигляд: ci=mie mod n (3) Для розшифрування повідомлення береться кожен зашифрований блок ci і обчислюється mi=cid mod n (4) Оскільки cid=(mie)d=mied=mik(p-1)(q-1)+1=mimik(p-1)(q-1)=mi*1=mi то формула відновлює повідомлення. Для піднесення до степеня за модулем n використовується бінарний алгоритм: Задано:
. Обчислити:
. Вважається, що d < n. Алгоритм у вигляді прямолінійної програми для обчислення функції
має вигляд. Показник
подається у двійковій системі числення:
, де
і
. Присвоюється
. Тоді
-та команда задається так:
Всього команд
. Результатом виконання останньої є
Всього витрачається
множень. Нехай p=47, q=71. Тоді N=pq=3337. Ключ e не повинен мати спільних множників (p-1)(q-1)=46*70=3220 Вибираємо випадково e, наприклад, 79. Тоді d=79-1mod 3220=1019. Під час обчислення використаний розширений алгоритм Евкліда. Зробимо e і n загальнодоступними, а d збережемо в секреті. Відкидаємо p і q. Для шифрування повідомлення m=6882326879666683 спочатку розбиваємо його на малі блоки. Для розглянутого випадку використовуємо трибуквенні блоки. Повідомлення розіб’ється на шість блоків mi. m1=688 m2=232 m3=687 m4=966 m5=668 m6=003 Перший блок шифрується 68879 mod 3337=1570=c1. Виконуючи такі самі операції для наступних бітів, одержимо шифротекст повідомлення: c=1570 2756 2091 2276 2423 158 Для розшифрування потрібно виконати операцію піднесення до степеня, використовуючи ключ розшифрування 1019: 15701019 mod 3337 =688 =m1 Аналогічно відновлюється інша частина повідомлення. ЗАВДАННЯ 1) Вивчити математичні основи, принципи побудови та вразливості алгоритму шифрування RSA. 2) Скласти блок-схеми алгоритмів та програму для реалізації шифрування та розшифрування відкритого тексту за допомогою алгоритму шифрування RSA. Забезпечити введення ключів з клавіатури. Для виконання операції піднесення до степеня за модулем використати бінарний алгоритм. Блок-схема: Остаточна версія програми: outtext.setText(null); if (code.isSelected() == true) { String intexts = this.intext.getText(); StringBuilder sb = new StringBuilder(intexts); for (;;) { if (sb.length() % 3 != 0) { sb.append(0); } else { break; } } String inter = sb.toString(); char textchd[] = inter.toCharArray(); int textint[] = new int[3]; for (int k = 0;; k += 3) { if (k > textchd.length - 1) { break; } int l = 0; for (int i = k; i < k + 3; i++) { textint[l] = textchd[i] - 48; l++; } // String sss = textint.toString(); // int textout = 0;// = Integer.parseInt(sss); int textit = textint[0] * 100 + textint[1] * 10 + textint[2]; String rrr = Integer.toString(textit); BigInteger bgi = new BigInteger(rrr); rrr = "79"; BigInteger step = new BigInteger(rrr); rrr = "3337"; BigInteger modul = new BigInteger(rrr); bgi = bgi.modPow(step, modul); String aString = bgi.toString(); // this.Text2.setText(aString); this.outtext.append(aString + " "); } } else { String intexts = this.intext.getText(); StringBuilder sb = new StringBuilder(intexts); String inter = sb.toString(); char textchd[] = inter.toCharArray(); int textint[] = new int[4]; for (int k = 0;; k += 5) { if (k > textchd.length - 1) { break; } int l = 0; for (int i = k; i < k + 4; i++) { textint[l] = textchd[i] - 48; l++; } // String sss = textint.toString(); // int textout = 0;// = Integer.parseInt(sss); int textit = textint[0] * 1000 + textint[1] * 100 + textint[2] * 10 + textint[3]; String rrr = Integer.toString(textit); BigInteger bgi = new BigInteger(rrr); rrr = "1019"; BigInteger step = new BigInteger(rrr); rrr = "3337"; BigInteger modul = new BigInteger(rrr); bgi = bgi.modPow(step, modul); String aString = bgi.toString(); // this.Text2.setText(aString); this.outtext.append(aString + " "); } } // TODO add your handling code here: Результати роботи програми: Приклад за шифрування тексту:
Приклад розшифрування тексту:
Висновок: На даній лабораторній роботі я вивчив математичні основи побудови алгоритму шифрування RSA, методи криптоаналізу та вимоги до стійкості алгоритму RSA, навчився розробляти програмне забезпечення для шифрування та цифрового підпису з використанням алгоритму RSA..