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

Перехід до торгівельного партнера Binance

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

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

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

Рік:

2012

Тип роботи:

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

Предмет:

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

Завантажити

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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” ДОСЛІДЖЕННЯ ШИФРІВ ПІДСТАНОВКИ. МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ № 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:01-

Коментарі

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

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

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись