Міністерство освіти і науки України Національний університет «Львівська Політехніка» Інститут комп’ютерних технологій автоматики та метрології Кафедра Безпеки Інформаційних Технологій
Звіт Про виконання лабораторної роботи № 4 “Криптографічні системи та протоколи” Львів 2012 Мета роботи: Навчитися практично використовувати алгоритми шифрування рюкзака і розробляти програмне забезпечення для реалізації цих алгоритмів. Теоретичні відомості Алгоритми рюкзака. Безпека алгоритму рюкзака полягає в проблемі рюкзака, NP-повну проблему. Дано багато предметів різної маси. Необхідно поскладати деякі з цих предметів в рюкзак так, щоб маса рюкзака дорівнювала певному значенню. У формалізованому вигляді задача виглядає так: дано набір значень M1, M2, … , Mn і сума S; обчислити значення bi такі, що S=b1M1+b2M2+…+bnMn (1) де bi може бути або нулем , або одиницею; одиниця означає, що предмет складають в рюкзак, а нуль – що не складають. Наприклад маси предметів можуть бути 1, 5, 6, 11, 14, 20. Можна запакувати рюкзак так, щоб його маса була 22, використавши маси 5, 6 і 11. Проте неможливио одержати результуючу масу 24. Час, необхідний для вирішення цієї проблеми із збільшенням кількості предметів зростає експонентно. Ідеєю алгоритму Меркла-Хелмана є шифрування повідомлення як розв’язку набору проблем рюкзака. Предмети вибираються за допомогою блоку відкритого тексту, який за довжиною дорівнює кількості предметів (біти відкритого тексту відповідають значенням b), а шифротекст є одержаною сумою. Приклад шифрування: Відкритий текст 111001 010110 000000 011000  Рюкзак 1 5 6 11 14 20 1 5 6 11 14 20 1 5 6 11 14 20 1 5 6 11 14 20  Шифротекст 1+5+6+20=32 5+11+14=30 0=0 5+6=11  Насправді існує дві різні проблеми рюкзака, одна з яких розв’язується протягом лінійного часу, а друга – ні. Відкритий ключ є важкою проблемою, яку можна використати для шифрування, але не можна для розшифрування повідомлень. Закритий ключ є легкою проблемою, даючи простий спосіб розшифрувати повідомлення. Тому, хто не знає закритого ключа доведеться розв’язати важку проблему рюкзака. ЗАВДАННЯ 1) Вивчити основні характеристики алгоритмів шифрування з відкритими ключами та теоретичні основи побудови алгоритмів шифрування рюкзака. 2) Скласти блок-схеми алгоритмів та програму для реалізації зашифрування та розшифрування відкритого тексту за допомогою шифру рюкзака із надзростаючою послідовністю з 12 елементів. Блок-схема: Остаточна версія програми: private void jButton2ActionPerformed(java.awt.event.ActionEvent evt) { Text2.setText(null); if (code.isSelected() == true) { int klucin[] = new int[6]; klucin[0] = 62; klucin[1] = 93; klucin[2] = 81; klucin[3] = 88; klucin[4] = 102; klucin[5] = 37; String intext = this.Text1.getText(); StringBuilder sb = new StringBuilder(intext); for (;;) { if (sb.length() % 6 != 0) { sb.append(0); } else { break; } } String inter = sb.toString(); char textchd[] = inter.toCharArray(); int textint[] = new int[6]; for (int k = 0; k < 13; k += 6) { if (k > textchd.length - 1) { break; } int textout = 0; int l = 0; for (int i = k; i < k + 6; i++) { textint[l] = textchd[i] - 48; l++; } for (int i = 0; i < 6; i++) { if (textint[i] == 1) { textout = textout + klucin[i]; } } String aString = Integer.toString(textout); this.Text2.append(aString + " "); } } else { Text2.setText(null); int klucout[] = new int[6]; klucout[0] = 2; klucout[1] = 3; klucout[2] = 6; klucout[3] = 13; klucout[4] = 27; klucout[5] = 52; String intext = this.Text1.getText(); char vhidch[] = intext.toCharArray(); int vhidin; int vhidinprom; int k = 0; for (int j = 0; j < intext.length(); j = k) { for (int i = j;;) { vhidin = vhidch[i] - 48; k++; k++; if (vhidch.length > 1) { if (vhidch[i + 1] != ' ') { vhidin = vhidin * 10 + vhidch[i + 1] - 48; k++; } else { break; } } if (vhidch.length > 2) { if (vhidch[i + 2] != ' ') { vhidin = vhidin * 10 + vhidch[i + 2] - 48; k++; } } break; } vhidinprom = (vhidin * 61) % 105; int vyh[] = new int[6]; for (int i = 5; i > -1; i--) { if (vhidinprom > klucout[i]) { vyh[i] = 1; vhidinprom -= klucout[i]; } else if (vhidinprom == klucout[i]) { vyh[i] = 1; break; } } for (int i = 0; i < 6; i++) { vyh[i] += 48; } StringBuilder v = new StringBuilder(); for (int i = 0; i <= vyh.length - 1; i++) { v.append((char) vyh[i]); } String vv = v.toString(); this.Text2.append(vv + " "); } } } Результати роботи програми: Приклад за шифрування тексту:
Приклад розшифрування тексту: