ДОСЛІДЖЕННЯ ШИФРІВ ПІДСТАНОВКИ. Методичні вказівки до лабораторної роботи з Криптографічні системи та протоколи. Робота № 518625

ДОСЛІДЖЕННЯ ШИФРІВ ПІДСТАНОВКИ

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

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

Рік:

2013

Тип роботи:

Методичні вказівки до лабораторної роботи

Предмет:

Криптографічні системи та протоколи

Завантажити

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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” ДОСЛІДЖЕННЯ ШИФРІВ ПІДСТАНОВКИ. МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ № 1 З ДИСЦИПЛІНИ “КРИПТОГРАФІЧНІ СИСТЕМИ ТА ПРОТОКОЛИ” для студентів базового напряму 6.170101 “Безпека інформаційних і комунікаційних систем” Затверджено на засiданнi кафедри “Безпека інформаційних технологій”, протокол № від 2012 р. Львів – 2012 Дослідження шифрів підстановки: Методичні вказівки до лабораторної роботи №1 з дисципліни “Криптографічні системи та протоколи” для студентів базового напряму 6.170101 “Безпека інформаційних і комунікаційних систем” /Укл.: А.Е.Лагун, А.В.Петришин - Львів: НУЛП 2012. - 00 с. Укладачі: А.Е.Лагун, к.т.н., доцент А.В.Петришин, асистент Відповідальний за випуск: Л.В. Мороз, к.т.н., доцент. Рецензент: В.М.Максимович, д.т.н., професор. Мета роботи - вивчити основні характеристики шифрів підстановки і навчитися розробляти програмне забезпечення для реалізації алгоритмів шифрування з використанням шифрів підстановки на комп’ютері. 1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ 1.1. МОНОАЛФАВІТНІ ПІДСТАНОВКИ Нехай Zm = {z1, z2,…, zm}- алфавіт відкритого та шифрованого текстів. Підстановкою на алфавіті Zm називається взаємно-однозначне відображення . Інакше кажучи, будь-яка перестановка елементів Zm визначає підстановку на Zm . Множина підстановок на Zm утворює групу відносно операції множення. Одиницею цієї групи є тотожна підстановка; для кожної підстановки π існує обернена підстановка π -1 : π π -1 = 1. Ця група називається симетричною і позначається SYM(Zm). Кількість всіх підстановок на Zm дорівнює m! Якщо задана підстановка π на Zm , то можна згідно з нею букві відкритого тексту співставити букву шифротексту. Але криптографічне перетворення повинно задавати правило шифрування тексту будь-якої довжини n. Позначимо - множину n-грам над алфавітом Zm. Криптографічним перетворенням Т називається сімейство перетворень , де . Підстановка (як криптосистема) – це криптографічне перетворення Т, де . Тобто, при шифруванні шифром підстановки тексту довжини n перша буква шифротексту одержується з першої букви відкритого тексту за допомогою π1, друга – за допомогою π2 , ..., остання – за допомогою πn. Таким чином, криптографічне перетворення Т задається ключем - нескінченною послідовністю підстановок. Букви при підстановці шифруються незалежно одна від одної і кожна, взагалі кажучи, є своєю підстановкою. Підстановка називається моноалфавітною, якщо πі = π , і=1,2,... (тобто всі букви шифруються тією ж самою підстановкою). Якщо ж у послідовності не всі підстановки однакові, то таке криптографічне перетворення називається поліалфавітною підстановкою. Моноалфавітну підстановку ще називають шифром простої заміни. При моноалфавітній підстановці одна й та ж сама буква алфавіту, що зустрічається у відкритому тексті, шифрується тією ж самою буквою шифротексту незалежно від її місця у тексті. Наприклад, якщо підстановка π переводить букву „а” в букву „м”, то де б не зустрілась буква „а” у відкритому тексті, вона буде зашифрована як „м”. У разі ж поліалфавітної підстановки одна й та сама буква алфавіту може шифруватись по-різному в залежності від її місця у відкритому тексті. 1.1.1. Шифр Цезаря Найпростіша моноалфавітна підстановка – це шифр Цезаря. Ототожнимо букви алфавіту Zm з цифрами від 0 до m-1 і позначимо x – довільну букву відкритого тексту, а y – відповідну букву шифротексту. Тоді в шифрі Цезаря , де - ключ (Цезар використовував ключ b=3). В цьому випадку підстановка на алфавіті є циклічним зсувом алфавіту на позицій вправо. Для того, щоб знайти ключ, маючи лише шифротекст, знайдемо y* - букву, що найчастіше зустрічається у шифротексті. Нехай x* - буква алфавіту, що має найбільшу частоту у мові, якою написаний відкритий текст. Тоді, якщо текст достатньо довгий, щоб у ньому проявилися закономірності мови, найвірогідніше, що x* зашифровано y*. Отже, маємо , звідки ключ . Звичайно, при цьому можна помилитися і розшифровуючи шифротекст за допомогою ключа b , одержимо беззмістовний набір букв. Тоді можна взяти y**- другу за частотою букву шифротексту і спробувати ключ і т.д., доки не одержиться змістовний текст. 1.1.2. Шифр афінної підстановки У шифрі Цезаря ключ може набувати всього m значень (малий ключовий простір), і всі ключі можна просто перебрати. Розглянемо трохи складніший шифр – шифр афінної підстановки: (1) Тут ключем є пара , причому повинно бути взаємно простим з m. З (1) одержуємо (2) де - обернений до елемент в кільці лишків за модулем m, Вираз (2) має ткакий самий вигляд, що й (1), отже шифрування і розшифрування здійснюються за тим самим алгоритмом, тільки з різними параметрами. Умова взаємної простоти з m потрібна для того, щоб існував обернений елемент і рівняння (1) при фіксованому y мало єдиний розв’язок x , тобто можливо було однозначно розшифрувати шифротекст. В іншому випадку рівняння (1) має не єдиний розв’язок x або взагалі його немає. Афінна підстановка також легко надається криптоаналізу, хоча кількість ключів в цьому шифрі значно більша, ніж у шифрі Цезаря, а саме φ (m) · m , де φ (m) – функція Ейлера (кількість чисел менших за m і взаємно простих з ним). Нехай і - перша і друга за частотою букви шифротексту, і - відповідно найчастіша і наступна за нею букви мови. Нехай при шифруванні перейшла в , а - в . Складемо систему рівнянь: (3) В цій системі невідомими є і , а x і y – відомі. З (3) маємо: (4) Якщо пари підібрані вірно, то рівняння (4) має розв’язок . Знаючи , з (3) знаходимо . Якщо ж ці пари не відповідають дійсності, то (4) або не має розв’язку, або при всіх розв’язках (3), розшифровуючи, одержимо беззмістовний текст. Тоді можна розглянути пари і спробувати знайти потрібну пару серед невеликої кількості найчастіших букв шифротексту і відкритого тексту. 1.1.3. Шифр Плейфера Букви алфавіту розміщують у квадратній таблиці. Таблицю заповнюють по рядках: спочатку пишуть ключове слово (воно може мати довжину від 1 до к2 , де к2 – кількість букв у таблиці). Далі записують букви алфавіту, що не входять у ключове слово, в алфавітному порядку. Наприклад, якщо в латинському алфавіті об’єднати букви I та J і вибрати ключовим словом „LIBERTY”, то квадрат Плейфера буде мати вигляд: L I B E R T Y A C D F G H K M N O P Q S U V W X Z У ключовому слові букви не повинні повторюватися. При шифруванні відкритий текст розбивається на біграми, що не перетинаються. Попередньо між буквами, що повторюються, вставляють деяку букву, яка має малу частоту і ніколи не зустрічається двічі підряд, наприклад Q. Тобто замість слова, скажімо, BUTTER треба записати BUTQTER, а замість слів SENT TO - SENTQ TO. Отже, при розбитті на біграми не зустрінеться біграма з двох однакових букв. Можна замість Q використати деякий спеціальний символ, ввівши його до алфавіту. Кожна біграма відкритого тексту шифрується таким чином: якщо букви біграми стоять в одному рядку, то відповідна біграма шифротексту складається з букв, що стоять в тому ж рядку справа від даних. При цьому вважається, що перший стовпчик стоїть справа від останнього. Наприклад, біграма YC зашифрується як AD, а біграма FM як GF; якщо букви біграми стоять в одному стовпці, то вона шифрується біграмою, що складається з букв, які стоять в тому ж стовпці під даними; при цьому вважається, що перший рядок знаходиться під останнім; якщо букви біграми стоять у різних рядках і стовпцях, то відповідна шифрована біграма складається з букв, що стоять у протилежних кутах прямокутника, заданого даними буквами. Наприклад, біграма TQ буде зашифрована як NC. Кількість ключів у шифрі Плейфера дорівнює к2!, але деякі з них є еквівалентними, тобто однаково шифрують однакові відкриті тексти. Шифр Плейфера також надається частотному аналізу. При криптоаналізі використовують як частоти біграм, так і деякі обмеження і закономірності, що випливають з правил шифрування. 1.1.4. Шифрування за Хіллом Можна узагальнити шифр афінної підстановки на n-грами (шифрування за Хіллом). N-грами відкритого тексту і шифротексту розглядаються як n-вимірні вектори над кільцем лишків Zm, а шифрування відбувається за правилом , де А – невироджена матриця , а - довільний вектор довжини n над Zm ; всі операції виконуються за . На цьому прикладі видно, що границя між потоковими та блоковими шифрами досить умовна: шифр Хілла можна розглядати і як потоковий, де елементи алфавіту n-грами, і як блоковий з довжиною блока n. При цьому істотною відмінністю блокового шифру від потокового є те, що в блоковому шифрі всі блоки шифруються однаково і незалежно один від одного, в потоковому ж, взагалі кажучи, кожна буква може шифруватися залежно від її місця в тексті і від інших букв тексту, а також від того, як вони шифруються. 1.2. ПОЛІАЛФАВІТНІ ПІДСТАНОВКИ 1.2.1. Моделі вибору ключа В загальному випадку поліалфавітна підстановка визначається ключем – нескінченною послідовністю підстановок на алфавіті {. Розглянемо три моделі вибору підстановок в цій послідовності. В усіх трьох вважається, що підстановки вибираються незалежно одна від одної. 1) , - довільні підстановки на . , тобто всі підстановки рівноймовірні. 2) Кожна з підстановок є шифром Цезаря із своїм ключем і одержуємо рівномірний розподіл на множині шифрів Цезаря. 3) , - шифри Цезаря, де - ймовірність букви з номером у мові. 1.2.2. Шифр Віженера Розглянемо поліалфавітну підстановку в тому випадку, коли послідовність є періодичною. Нехай період її дорівнює , а кожна з підстановок є шифром Цезаря. Зазвичай ключ є деяким відрізком змістовного тексту – словом або фразою. Його підписують під відкритим текстом, повторюючи стільки разів, скільки потрібно. Додаючи номери букви відкритого тексту і букви ключа, що стоїть під ним, за , одержують номер букви шифротексту. Наприклад: ВТ п о л і а л ф а в і т н а п і д с т а н О в к а Ключ ц е з а р ц е з а р ц е з а р ц е з а р Ц е з а ШТ й ф ф і р з ь з в ю м у з п ю ю ч ю а д Ї ж у а В українській абетці 32 букви, номер букви «п» 19, номер букви «ц» 26: 19+26(32)=13 – номер букви «й» і так далі. Така поліалфавітна підстановка називається шифром Віженера. Криптоаналіз шифру Віженера є досить простим, якщо відома довжина періоду . В цьому випадку шифротекст розбивають на фрагментів: тобто з шифротексту вибирають букви, що лежать на відстані , починаючи з першої, другої і т.д. Кожен з фрагментів зашифрований шифром Цезаря з певним ключем, і тому легко розшифровується. Таким чином, одержуємо ключ . Щоб ускладнити криптоаналіз, застосовують багатоконтурну систему Віженера: відкритий текст шифрують спочатку шифром Віженера з періодом , одержаний шифротекст знову шифрують іншим шифром Віженера з періодом ,... і так разів. Якщо періоди взаємно прості, то результуючий шифр еквівалентний шифру Віженера з періодом . 1.2.3. Шифр з автоключем Розглянемо ще один потоковий шифр, в якому кожна буква шифрується в залежності не тільки від її місця у відкритому тексті, але й від інших букв відкритого тексту. Такий шифр називається шифром з автоключем. Під відкритим текстом підписують ключове слово , а далі – сам відкритий текст (зсунутий на позицій вправо) і ці дві послідовності додають за : При криптоаналізі спочатку знаходять довжину ключового слова . Якщо деяка -грама двічі зустрічається у відкритому тексті на відстані 2, то в шифротексті на відстані також будуть однакові -грами. Наприклад: Таким чином, аналізуючи відстані між однаковими -грамами у шифротексті, можна знайти . Для визначення першої букви ключового слова розглядають фрагмент шифротексту Перебирають значення і для кожного підраховують . Ці рівності будуть вірними, коли збігається з істинним. При цьому частоти букв у зазначеній послідовності близькі до частот букв у відкритому тексті, а при невірному частоти згладжені. Так само знаходять і решту букв ключового слова. 2. ЗАВДАННЯ 2.1. Домашня підготовка до роботи 1) Вивчити основні алгоритми шифрування, що використовують моноалфавітні та поліалфавітні підстановки. 2) Скласти блок-схеми алгоритмів та програму для реалізації шифру Плейфера. 3) Скласти блок-схеми алгоритмів та програму для реалізації зашифрування та розшифрування відкритого тексту величиною приблизно два аркуші формату А4 за допомогою шифру з автоключем і багатоконтурної системи Віженера з періодом n=5. Забезпечити введення ключа шифрування з клавіатури. 2.2. Робота в лабораторії 1) Ввести в комп'ютер програми згідно із завданням. 2) Відлагодити програми. При необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками. 3) Остаточні версії блок-схем, програм та отримані результати оформити у звіті з лабораторної роботи. 4) Здати звіт з лабораторної роботи. 3. ЗМІСТ ЗВІТУ 1) Номер і назва лабораторної роботи. 2) Повний текст завдання. 3) Остаточні версії блок-схем алгоритмів. 4) Список ідентифікаторів констант, змінних, процедур і функцій, використаних у блок-схемах алгоритмів і програм, та їх пояснення. 5) Остаточні версії програм. 6) Результати роботи програм. 4. КОНТРОЛЬНІ ЗАПИТАННЯ 1. Що таке підстановка, криптографічне перетворення? 2. Особливості та характеристика моноалфавітних підстановок. 3. Які операції використовуються для зашифрування та розшифрування в шифрі Цезаря? 4. Поясніть суть операції зашифрування в шифрі Плейфер. 5. В чому суть поліалфавітних підстановок? 6. В чому відмінність між шифрами Віженера та шифром з автоключем? СПИСОК ЛІТЕРАТУРИ О.Н.Василенко, Теоретико-числовые алгоритмы в криптографии. – М.: Изд-во МГУ, 2000 К.Шеннон. Теория связи в секретных системах. В Работы по теории информации и кибернетике, стр. 333-402. М., Изд. Иностр. Лит., 1963. М.Вельшенбах. Криптография на Си и С++ в действии. М., Триумф, 2004. Б.Шнайер. Прикладная криптография, 2-е издание: протоколы, алгоритмы, исходные тексты на языке Си. М., Триумф, 2002. Навчальне видання Дослідження шифрів підстановки: Методичні вказівки до лабораторної роботи №1 з дисципліни “Криптографічні системи та протоколи” для студентів базового напряму 6.170101 “Безпека інформаційних і комунікаційних систем”. Укладачі: Лагун Андрій Едуардович Петришин Андрій Васильович

Методичні вказівки до лабораторної роботи Криптографічні системи та протоколи

sergiwez

19.01.2013 21:18

Коментарі

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

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

поділитись