Криптографія в Стародавньому світі
Криптографія в Стародавньому світі
Є свідчення, що криптографія як техніка захисту тексту виникла разом з писемністю, і способи таємного листа були відомі вже древнім цивілізаціям Індії, Єгипту та Месопотамії. У давньоіндійських текстах серед 64-х мистецтв названі способи зміни тексту, деякі з них можна віднести до криптографічних. Автор таблички з рецептом для виготовлення глазурі для гончарних виробів з Месопотамії використовував рідкісні позначення, пропускав букви, а імена заміняв на цифри, щоб сховати написане . Першим згадкою про використання криптографії прийнято вважати використання спеціальних ієрогліфів близько 3900 років тому в Стародавньому Єгипті. Хоча метою було не утруднити читання тексту - скоріше навпаки, за допомогою незвичайності та загадковості привернути увагу читача і прославити вельможу Хнумхотепа Другого (англ. Khnumhotep II) . Надалі зустрічаються різні згадки про використання криптографії, велика частина відноситься до використання у військовій справі.
Атбаш
Приклади використання криптографії можна зустріти в священних іудейських книгах, у тому числі в книзі пророка Єремії (VI століття до н. Е.), Де використовувався простий метод шифрування під назвою атбаш .
Скитала
Скитала, також відома як «шифр стародавньої Спарти», також є одним з найдавніших відомих криптографічних пристроїв.
Безперечно відомо, що скитала використовувалася у війні Спарти проти Афін в кінці V століття до н. е.. Можливо також, що її згадують поети Архілох (VII століття до н. е..) і Піндар , хоча найімовірніше, що в їхніх віршах слово «скитала» використано у своєму первинному значенні «посох».
Принцип її дії виклали Аполлоній Родоський (середина III століття до н. Е.) І Плутарх (близько 45-125 н. Е.), Але збереглося лише опис останнього .
Скитала представляла собою довгий стрижень, на який намотувалася стрічка з пергаменту. На стрічку наносився текст вздовж осі скіталу, так, що після розмотування текст ставав нечитабельним. Для його відновлення потрібна скитала такого ж діаметру.
Вважається, що автором способу злому шифру скіталу є Аристотель, який намотував стрічку на конусоподібну палицю до тих пір, поки не з'являлися читаються уривки тексту.
Диск Енея, лінійка Енея, книжковий шифр
З ім'ям Енея Тактика, полководця IV століття до н. е.., пов'язують декілька технік шифрування і тайнопису. Диск Енея представляв собою диск діаметром 10-15 см з отворами по числу букв алфавіту. Щоб створити нитка простягалася через отвори в диску, відповідним буквам повідомлення. При читанні одержувач витягав нитку, і отримував літери, правда, в зворотному порядку. Хоча недоброзичливець міг прочитати повідомлення, якщо перехопить диск, Еней передбачив спосіб швидкого знищення повідомлення -. Для цього було достатньо висмикнути нитку, закріплену на котушці в центрі диска Першим дійсно криптографічним інструментом можна назвати лінійку Енея, що реалізує шифр заміни. Замість диска використовувалася лінійка з отворами по числу букв алфавіту, котушкою і прорізом. Для шифрування нитка простягалася через проріз і отвір, після чого на нитки зав'язувався черговий вузол. Для дешифрування необхідно було мати саму нитку і лінійку з аналогічним розташуванням отворів. Таким чином, навіть знаючи алгоритм шифрування, але не маючи ключа (лінійки), прочитати повідомлення було неможливо [14]. У своєму творі «Про перенесення облоги» Еней описує ще одну техніку тайнопису, пізніше названу «книжковий шифр». Він запропонував робити малопомітні дірки поряд з літерами в книзі або іншому документі . Значно пізніше, аналогічний шифр використовували німецькі шпигуни у Першій світовій війні.
Квадрат Полібія
1 2 3 4 5 1 Α Β Γ Δ Ε
2 Ζ Η Θ Ι Κ
3 Λ Μ Ν Ξ Ο
4 Π Ρ Σ Τ Υ
5 Φ Χ Ψ Ω
Квадрат Полібія з грецьким алфавітом. Для передачі, наприклад, літери «Θ» спочатку показували два факела, потім три. У II столітті до н. е.. в Стародавній Греції був винайдений Квадрат Полібія. У ньому букви алфавіту записувалися в квадрат 5 на 5 (при використанні грецького алфавіту один осередок залишалася порожньою), після чого за допомогою оптичного телеграфу передавалися номер рядка і стовпця, відповідні символу вихідного тексту (на кожну букву доводилося два сигнали: число факелів позначало розряд літери по горизонталі і вертикалі). Деякі дослідники вважають, що це можна розглядати як першу систему, зменшується (стискала) вихідний алфавіт, і, в деякому розумінні, як прообраз сучасної системи двійковій передачі даних . Шифр Цезаря Згідно свідченням Светонія, Цезар використовував в листуванні моноалфавитной шифр, який увійшов в історію як Шифр Цезаря . Книгу про шифрі написав граматик Проб . У шифрі Цезаря кожна буква алфавіту циклічно зсувається на певне число позицій. Величину зсуву можна розглядати як ключ шифрування. Сам Цезар використовував зсув на три позиції.
Тайнописом
Лист царя Олексія Михайловича, писаний тайнописом (тарабарщиною) Крім примітивних шифрів в історії використовувався і інший підхід - повна заміна одного алфавіту (наприклад, кирилиці) на інший (наприклад, грецький). Не маючи ключа, сопоставляющего вихідний і використовуваний алфавіти, прочитати напис було неможливо. Крім цього використовувалися спеціальні техніки записи символів алфавіту таким чином, щоб ускладнити його читання. Прикладом такої техніки є «в'язані руни», коли руни записуються таким чином, що окремі їхні елементи (наприклад, вертикальні риси) збігаються. Подібні системи часто використовувалися жерцями Північно-Західної Європи аж до пізнього Середньовіччя. Безліч варіантів тайнопису використовувалося і на Русі. Серед них і прості моноалфавитной шифри (проста літорея, лист в квадратах), заміна алфавіту - тайнопис глаголицею, тайнопис грецької абеткою, а також особливі прийоми письма, наприклад, моноконділ. Найбільш ранні тексти з використанням тайнопису відносяться до XII століття. Існує думка [25] [26], що в більш пізній період тайнопис використовувалася для іконографії, наприклад, при написання ікони XIV століття «Донська Богоматір». Відповідно до іншої точки зору, літерний ряд є лише шрифтовим декором, який був широко поширений як у давньоруській, так і, наприклад, в візантійського іконопису .
Шифр Цезаря
Шифр Цезаря, також відомий як шифр зсуву, код Цезаря або зсув Цезаря - один з найпростіших і найбільш широко відомих методів шифрування.
Шифр Цезаря - це вид шифру підстановки, в якому кожен символ у відкритому тексті замінюється буквою знаходиться на деяке постійне число позицій лівіше або правіше нього в алфавіті. Наприклад, в шифрі зі зрушенням 3, А була б замінена на Г, Б стане Д, і так далі.
Шифр названий на честь римського імператора Гая Юлія Цезаря, який використав його для секретного листування зі своїми генералами.
Крок шифрування, що виконується шифром Цезаря, часто включається як частина більш складних схем, таких як шифр Віженер, і все ще має сучасне додаток в системі ROT13. Як і всі моноалфавитной шифри, шифр Цезаря легко зламується і не має практично ніякого застосування на практиці.
•
Математична модель
Якщо зіставити кожному символу алфавіту його порядковий номер (нумеруючи з 0), то шифрування і дешифрування можна виразити формулами модульної арифметики:
де - символ відкритого тексту, - символ шифрованого тексту, - потужність алфавіту, а - ключ.
З точки зору математики шифр Цезаря є окремим випадком аффинного шифру.
Приклад
Шифрування з використанням ключа к = 3. Буква «С» «зрушується» на три букви вперед і стає буквою «Ф». Твердий знак, переміщений на три букви вперед, стає буквою «Е», і так далі:
Оригінальний алфавіт: АБВГДЕЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ
Зашифрований: ГДЕЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯАБВ
Оригінальний текст:
З'їж ж ще цих м'яких французьких булок, та випий чаю.
Зашифрований текст виходить шляхом заміни кожної букви оригінального тексту відповідною буквою шифрованого алфавіту:
Фезия йз зьі ахлш пвенлш чугрщцкфнлш дцосн, жг еютзм'гб.
Історія та застосування
Шифр Цезаря названий на честь Гая Юлія Цезаря, який використовував його з лівим зрушенням на 3.
Шифр Цезаря називають на честь Юлія Цезаря, який згідно з «Життя дванадцяти цезарів» Светонія використовував його зі зрушенням 3, щоб захищати військові повідомлення. Хоча Цезар був першим зафіксованим людиною використовують цю схему, інші шифри підстановки, як відомо, використовувалися і раніше.
Якщо у нього було щось конфіденційне для передачі, то він записував це шифром, тобто так змінював порядок букв алфавіту, що не можна було розібрати жодне слово. Якщо хто-небудь хотів дешифрувати його і зрозуміти його значення, то він повинен був підставляти четверту букву алфавіту, а саме, D, для, і так далі, з іншими буквами.
Гай Светоній Транквилл Життя дванадцяти цезарів 56
Його племінник, Август, також використовував цей шифр, але зі зрушенням вправо на один, і він не повторювався до початку алфавіту:
Всякий раз, коли він записував шифром, він записав для B, C для B, і решти букв на тому ж самому принципі, використовуючи для А. А. X.
Гай Светоній Транквилл, життя Августа 88
Є докази, що Юлій Цезар використовував також і більш складні схеми. Невідомо, наскільки ефективним шифр Цезаря був у той час, але мабуть він був розумно безпечний, не в останню чергу завдяки тому, що більшість ворогів Цезаря були неписьменними, і багато хто припускав, що повідомлення були написані на невідомому іноземною мовою. [2] Немає ніяких свідоцтв того часу щодо методів злому простих шифрів підстановки. Найбільш ранні збереглися записи про частотному аналізі -. Це роботи Ал-Кінді дев'ятого століття про відкриття частотного аналізу Шифр Цезаря із зсувом на один використовується на зворотному боці мезузи, щоб зашифрувати імена Бога. Це може бути пережитком з раннього часу, коли єврейському народу не дозволили мати мезузи. У 19-му сторіччі особиста секція рекламних оголошень в газетах іноді використовувалася, щоб обмінюватися повідомленнями, зашифрованими з використанням простих шифрів. Кан (1967) описує випадки коли любителі брали участь у секретних комунікаціях, зашифрованих з використанням шифру Цезаря в «Таймс» Навіть пізніше, в 1915 році, шифр Цезаря знаходив застосування. Російська армія використовувала його як заміну для більш складних шифрів, які опинилися занадто складними для військ;. у німецьких та австрійських криптоаналітиків були лише невеликі труднощі в розшифровці цих повідомлень Шифр Цезаря з сдвігм тринадцять також використовується в алгоритмі ROT13, простому методі заплутування тексту, широко іспольуемого в Usenet, і використовується скоріше як спосіб приховування спойлерів, ніж як метод шифрування . Шифр Віженер використовує шифр Цезаря з різними зрушеннями в кожній позиції в тексті ; значення зсуву визначається за допомогою повторюваного ключового слова. Якщо ключове слово таке ж довге як і повідомлення, тоді цей шифр стає невзламиваемим до тих пір поки користувачі підтримують таємницю ключового слова. Ключові слова коротше ніж повідомлення (наприклад, «повної перемоги», що використовується Конфедерацією під час громадянської війни в США), вводять циклічний зразок, який міг би бути виявлений за допомогою покращеної версії частотного аналізу . У квітні 2006 року, побіжний бос мафії Бернардо Провенцано був спійманий в Сицилії частково через криптоаналізу його повідомлень, написаних з використанням варіації шифру Цезаря. Шифр Провенцано використовував числа, так, щоб «А» була написана як «4», «Б» як «5», і так далі.
Диск з шифром Цезаря
Часто для зручність використання шифру Цезаря використовують два диски різного діаметру з намальованими по краях дисків алфавітами, насаджених на загальну вісь. Спочатку диски повертаються так, щоб напроти кожної букви алфавіту зовнішнього диска знаходилася та сама буква алфавіту малого диска. Якщо тепер повернути внутрішній диск на декілька символів, то ми отримаємо відповідність між символами зовнішнього диска і внутрішнього - шифр Цезаря. Одержаний диск можна використовувати як для шифрування, так і для розшифровки.
Наприклад, якщо внутрішнє колесо повернути так, щоб символу зовнішнього диска соответсвовала символ D внутрішнього диска, то ми отримаємо шифр із зсувом вліво 3.
Злом шифру
Розшифровка
Кандидат зсув тексту
0 exxegoexsrgi
1 dwwdfndwrqfh
2 cvvcemcvqpeg
3 buubdlbupodf
4 attackatonce
5 zsszbjzsnmbd
6 yrryaiyrmlac
...
23 haahjrhavujl
24 gzzgiqgzutik
25 fyyfhpfytshj
Шифр Цезаря може бути легко зламаний навіть у випадку, коли зломщик знає тільки зашифрований текст. Можна розглянути дві ситуації:
1. зломщик знає (або припускає), що використовувався простий шифр підстановки, але не знає що це - схема Цезаря;
2. зломщик знає, що використовувався шифр Цезаря, але не знає значення зсуву.
У першому випадку шифр може бути зламаний, використовуючи ті ж самі методи що і для простого шифру підстановки, такі як частотний аналіз і т. д, Використовуючи ці методи зломщик ймовірно швидко помітить регулярність у вирішенні і зрозуміє, що використовується шифр -. це шифр Цезаря.
У другому випадку, злом шифру є навіть простішим. Існує не так багато варіантів значень зсуву (26 для англійської мови), всі вони можуть бути перевірені методом грубої сили Один зі способів зробити це -. Виписати уривок зашифрованого тексту в стовпець всіх можливих зрушень - техніка, іноді звана як «завершення простого компоненту » Розглянемо приклад для зашифрованого тексту« EXXEGOEXSRGI »;. відкритий текст негайно розпізнається оком в четвертому рядку.
Інший спосіб застосування цього методу - це написати алфавіт під кожною буквою зашифрованого тексту, починаючи з цієї літери. Метод може бути прискорений, якщо використовувати заздалегідь підготовлені смужки з алфавітом. Для цього потрібно скласти смужки так, щоб в одному рядку утворився зашифрованих текст, тоді в деякої іншої рядку ми побачимо відкритий текст.
Для звичайного тексту на природній мові, швидше за все, буде тільки один варант декодування. Але, якщо використовувати дуже короткі повідомлення, то можливі випадки, коли можливі декілька варіантів розшифровки з різними зрушеннями. Наприклад зашифрований текст MPQY може бути розшифрований як «Аден» так і як «ноу» (припускаючи що відкритий текст написаний англійською мовою). Точно також «ALIIP» можна розшифрувати як «ляльки» або як «колесо», «AFCCP» як «веселий» або як «ура».
Багаторазове шифрування ніяк не покращує стійкість, так як застосування шифрів із зсувом і б еквівалентно застосування шифру із зсувом + b. У математичних термінах шифрування з різними ключам утворює групу .
