МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ І СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
/
Лабораторна робота №3
на тему:
“Криптоаналіз шифрів моноалфавітної заміни”
з дисципліни:
“Захист інформації в комп'ютерних мережах”
Мета роботи: ознайомитись з основними методами, що використовуються для криптоаналізу шифрів моноалфавітної заміни та, зокрема, з основами частотного аналізу зашифрованого тексту.
Теоретичні відомості
При наявності всього 25 можливих варіантів ключів шифр Цезаря далекий від того, щоб вважатися надійно захищеним. Істотного розширення простору ключів можна домогтися, дозволивши використання довільних підстановок. Давайте ще раз згадаємо шифр Цезаря.
/
Рис. 1 Приклад зашифрованого тексту
Відкритий текст: a b c d e f g h I j k l m n o p q r s t u v w y z
Шифрований текст: D E F G H I J K L M N O P Q R S T U W Y Z
Якщо в рядку "Шифрований текст" допустити використання кожної з перестановок 26 символів алфавіту, то ми одержимо 26!, або більш ніж 4 х 1026 можливих ключів. Це на 10 порядків більше, ніж розмір простору ключів DES, і це здається достатнім для того, щоб унеможливити успішне застосування криптоаналізу на основі методу послідовного перебору.
Однак для криптоаналітика існує й інша лінія атаки. Якщо криптоаналітик має уявлення про природу відкритого тексту (наприклад, про те, що це зашифрований текст англійською мовою), можна використати відому інформацію про характерні ознаки, властиві текстам відповідною мовою. Щоб показати, як цей підхід застосовується на практиці, розглянемо невеликий приклад. Припустимо, нам потрібно розшифрувати наступний зашифрований текст.
/
На першому етапі можна визначити відносну частоту появи в тексті різних букв і порівняти їх із середньостатистичними даними для букв англійської мови, показаними на рис. 2.
Якщо повідомлення досить довге, цієї методики вже може бути досить для розпізнавання тексту, але в нашому випадку, коли повідомлення невелике, точного відповідності очікувати не доводиться. У нашому випадку відносна частота входження букв у шифрованому тексті (у відсотках) виявляється наступною.
/
Рис. 2. Відносна частота появи букв в англійському тексті
Порівнюючи ці результати з даними, показаними на рис. 2, можна припустити, що, швидше за все, букви Р и Z шифрованого тексту є еквівалентами букв е и t відкритого тексту, хоча важко сказати, якій саме букві - Р або Z - відповідає е, а який - t. Букви S, U, ПРО, М и Н, що володіють відносно високою частотою появи в тексті, швидше за все, відповідають буквам з множини {г, n, i, о, a, s}.. Букви з низькою частотою появи (а саме А, В, G, Y, I, J), очевидно, відповідають буквам множини {w,v,b,k,x,q,j,z}.
Далі можна піти декількома шляхами. Можна, наприклад, прийняти якісь припущення про відповідності й на їхній основі спробувати відновити відкритий текст, щоб побачити, чи виглядає такий текст схожим на що-небудь змістовне. Більш систематизований підхід полягає в продовженні пошуку в тексті нових характерних закономірностей. Наприклад, може бути відомо, що в розглянутому тексті обов'язково повинні бути присутнім деякі слова. Або ж можна шукати повторювані послідовності букв шифрованого тексту й намагатися визначити їхні еквіваленти у відкритому тексті.
Хід роботи
Для розробки програми криптоаналізу шифру використано середовище розробки Eclipce.
Частота появи літер в завданні. (рис. 1)
/
Рис. 1. Кількість появи літер
/
/
Рис. 2. Результат виконання роботи
Висновок: В даній лабораторній роботі я ознайомився з основними методами, що використовуються для криптоаналізу шифрів моноалфавітної заміни та, зокрема, з основами частотного аналізу зашифрованого тексту.
Лістинг програми
Cesar.java import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class Cesar{
Map <Character,Integer> map = new HashMap<Character,Integer> ();
private int key;
publ...
