Шифр ADFGVX
ADFGVX-шифр — один з найвідоміших шифрів часів Першої світової війни, який використовувався німецькою армією на Західному фронті. Особливість шифру полягає в тому, що він побудований на поєднанні базових операцій заміни та перестановки. Частина шифру, що відповідає заміні, ґрунтується на квадрат Полібія.
Історія[ред. | ред. код]
До кінця Першої світової війни, в той час як більша частина країн світу використовувала або шифр заміни, або шифр перестановки, Німеччина почала використовувати нову систему шифрування ADFGX, яка об'єднала риси обох. Свою назву ця система отримала через те, що її шифрограми містили тільки літери «A», «D», «F», «G» і «X». Ці літери були обрані не випадковим чином. Якщо їх представити у вигляді крапок і тире коду Морзе, то вони будуть суттєво відрізнятися одна від одної. Таким чином, вибір цих букв мінімізує ризик появи помилок під час телеграфної передачі. Фактично це був квадрат Полібія, в який вписувався латинський алфавіт в певному порядку. Цей шифр був розроблений офіцером зв'язку полковником Фріцем Небелем, який служив у штабі німецької армії, і введений в дію у березні 1918 року[1].
Повідомлення, зашифровані цим шифром, першими перехопили французи. Робота по «розкриттю» цього шифру була доручена криптоаналітику лейтенанту Жоржу Пенвену.
У червні 1918 року з метою ускладнення шифру, німці додали букву «V», тим самим збільшивши сітку шифрування до 36 символів. Це дозволило включити у відкритий текст цифри від 0 до 9 та букви I і J, які стали шифруватися по-різному. Розширення шифру значно скоротило розмір повідомлень, що містять велику кількість цифр. Шифр став називатися ADFGVX[1].
Запорука успіху німецьких бойових дій, як в іншому і будь-яких інших, ґрунтувався на факторові раптовості. Тому для забезпечення прихованості повідомлення був необхідний шифр, що володіє найвищою стійкістю. Німці вважали, що ADFGX і ADFGVX шифри були стійкими для злому. Однак, 2 червня 1918 року в результаті копіткої роботи французький офіцер Жорж Пенвен розшифрував шифрограму, де були визначені цілі майбутнього наступу німецьких військ. Успіх Пенвена дозволив французам зірвати атаку й зупинити просування німців[2].
Опис ADFGX шифру[ред. | ред. код]
Процес шифрування починається з малювання сітки розміру 5×5, кожна клітинка заповнюється 25 літерами латинського алфавіту (I та J шифруються однаково). Кожен рядок і стовпець сітки задається однією з 5 букв: «A», «D», «F», «G» і «X». Заповнення сітки здійснюється в довільному порядку, тому одержувач повинен знати розташування кожного елемента, щоб зробити дешифрування.
| A | D | F | G | X | |
|---|---|---|---|---|---|
| A | F | N | H | E | Q |
| D | R | D | Z | O | C |
| F | I/J | S | A | G | U |
| G | B | V | K | P | W |
| X | X | M | Y | T | L |
Крок перший — заміна[ред. | ред. код]
Розглянемо процес шифрування на прикладі невеликого повідомлення: «attack at dawn». На першому кроці кожен символ повідомлення замінюється на пару букв, що позначають рядок і стовпець відповідного символу в сітці. Наприклад, A буде замінено на FF, а B — на GA.
| Повідомлення: | attack at dawn | |||||||||||
| Відкритий текст: | a | t | t | a | c | k | a | t | d | a | w | n |
| Шифротекст на першому кроці: | FF | XG | XG | FF | DX | GF | FF | XG | DD | FF | GX | AD |
Досі ми використовували лише просту заміну, і частотного аналізу було б достатньо, щоб розгадати повідомлення.
Крок другий — перестановка[ред. | ред. код]
На другому кроці застосовується перестановка, що значно ускладнює криптоаналіз. Перестановка здійснюється в залежності від ключового слова, яке повинно бути відомо одержувачу. Нехай, у нашому прикладі, таким словом буде «BATTLE». Процес перестановки полягає в наступному. Спочатку створюється нова сітка, у верхній частині якої записуються літери ключового слова. Потім, під цим словом порядково записується, отриманий на першому кроці зашифрований текст.
| B | A | T | T | L | E |
|---|---|---|---|---|---|
| F | F | X | G | X | G |
| F | F | D | X | G | F |
| F | F | X | G | D | D |
| F | F | G | X | A | D |
Далі, літери ключового слова переставляються в алфавітному порядку разом з відповідними стовпцями сітки.
| A | B | E | L | T | T |
|---|---|---|---|---|---|
| F | F | G | X | X | G |
| F | F | F | G | D | X |
| F | F | D | D | X | G |
| F | F | D | A | G | X |
Після чого літери кожного стовпця виписуються по черзі зверху вниз. Отримана послідовність букв утворює остаточний вигляд шифротексту[1][3].
Остаточний вигляд шифротекста: F F F F F F F F G F D D X G D A X D X G G X G X
У цьому вигляді шифротекст буде потім переданий за допомогою коду Морзе.
Опис ADFGVX шифру[ред. | ред. код]
Шифр ґрунтується на 6 літерах: «A», «D», «F», «G», «V» і «X». Аналогічно шифру ADFGX малюється таблиця розміру 6x6 і випадковим чином заповнюється 26 літерами і 10 цифрами. Розташування елементів в таблиці є частиною ключа.
| A | D | F | G | V | X | |
|---|---|---|---|---|---|---|
| A | 1 | J | R | 4 | H | D |
| D | E | 2 | A | V | 9 | M |
| F | 8 | P | I | N | K | Z |
| G | B | Y | U | F | 6 | T |
| V | 5 | G | X | S | 3 | O |
| X | W | L | Q | 7 | C | 0 |
Крок перший — заміна[ред. | ред. код]
Крок другий — перестановка[ред. | ред. код]
Створюється нова таблиця з ключовим словом у верхньому рядку. В якості ключа візьмемо слово «SECRET». Зазвичай використовуються більш довгі ключові слова або фрази.
| S | E | C | R | E | T |
|---|---|---|---|---|---|
| D | F | G | X | G | X |
| D | F | X | V | F | V |
| X | A | F | F | X | D |
| X | D | G | A | D | A |
| V | D | F | F | F | G |
| F | F | F | G | A | A |
| A | A | D | F | D | X |
За аналогією з шифром ADFGX, стовпці таблиці сортуються в алфавітному порядку[1].
| C | E | E | R | S | T |
|---|---|---|---|---|---|
| G | F | G | X | D | X |
| X | F | F | V | D | V |
| F | A | X | F | X | D |
| G | D | D | A | X | A |
| F | D | F | F | V | G |
| F | F | A | G | F | A |
| D | A | D | F | A | X |
Після чого стовпці по черзі записуються в один рядок, утворюючи зашифрований текст.
Остаточний вигляд шифротексту: G X F G F F D F F A D D F A G F X D F A D X V F A F G F D D X X V F A X V D A G A X
Для відновлення вихідного тексту необхідно виконати дії, зворотні шифруванню. Володіючи ключовим словом, послідовність стовпчиків можна привести до первісного порядку. Знаючи розташування символів у вихідній таблиці, можна розшифрувати текст[4].
Криптоаналіз[ред. | ред. код]
Криптоаналіз ADFGX шифру проводив лейтенант французької армії Жорж Пенвен, який зламав його до початку червня 1918 року. Його метод рішення був заснований на пошуку повідомлень зі стандартним початком, які шифрувалися схожим чином, утворюючи схожі моделі в зашифрованому тексті, що відповідало назві стовпців в таблиці перестановок. По досягненню цього кроку потрібно провести значний статистичний аналіз, що було дуже складним завданням, адже все робилося вручну. Подібний підхід був ефективний тільки при перехопленні великої кількості повідомлень.
Однак це був не єдиний прийом, який Пенвен застосовував для злому шифру ADFGX. Він так само використав повторювані фрагменти шифротексту для отримання інформації про ймовірну довжину використовуваного ключа[5].
Оскільки в зашифрованому тексті використовувалося тільки 5 букв, стало ясно, що шифрування здійснювалося за шаховою схемою. Перший крок полягав в усуненні очевидного припущення. Він справив частотний аналіз пар букв, щоб переконатися, що це не проста заміна за допомогою квадрата Полібія. Результат дав випадковий розподіл пар, з якого Пенвен зробив висновок, що літери були замінені і перемішані.
Тепер він припустив, що шифр є результатом перестановки стовпців, які записувалися, замінені за шаховою схемою літери. Пенвен зміг придумати тонкий хід, щоб звузити можливості для перестановки порядку стовпців. Заміна в шифрі, як описано вище, здійснювалася на основі сітки з літерами «A», «D», «F», «G» та «X» вздовж стовпців і тих же букв вздовж рядків. Він знав, що кожній букві ставилися у відповідність 2, які визначають становище в сітці. Це означало, що після заміни, але перед перестановкою, букви, що позначають стовпець, будуть стояти на парних позиціях, а рядок — на непарних. Тепер згадаємо, що результат заміни записується порядково один під одним, утворюючи колонки. Якщо число таких колонок було парним, то вони будуть складатися або з літер, які задають стовпці, або — що задають рядки. Цей метод дозволив Пенвену попередньо визначити, які стовпці були парними, а які-непарними. Потім він міг об'єднати парні і непарні стовпці пари й виконати частотний аналіз для пар букв, щоб побачити, чи є вони результатом заміни символу відкритого тексту. Після знаходження правильних пар, Пенвен здійснював частотний аналіз для виявлення замінених букв. Залишалося тільки розпізнати принцип транспозиції. Після того, як він визначив схему перестановки для одного повідомлення, він міг зламати будь-яке інше повідомлення з тим же ключем транспозиції[6].
Нарешті, у квітні 1918 року Пенвену вдалося розшифрувати деякі повідомлення. У ці дні німці посилали велику кількість шифровок. До кінця травня, з огляду на досить великий потік повідомлень, він міг зламувати шифрограми кожен день.
1 червня 1918 року в зашифрованих повідомленнях раптом стала з'являтися літера «V». Німці змінили шифр. Пенвен не знав, чи просто додана нова буква для розширення існуючої системи або ж вони повністю змінили схему шифрування, знищивши всю важку праця французького офіцера. Пенвен продовжив роботу, спираючись на найпростіше припущення, що новий шифр є розширенням старого. І по мірі дослідження зашифрованих текстів, Пейнвен все більше переконувався у правильності своєї гіпотези. Адаптувавши свою роботу над ADFGX до шифру ADFGVX, увечері 2 червня він розгадав вдосконалений німцями код.
Примітки[ред. | ред. код]
- ↑ а б в г Richard E. Klima, Neil P. Sigmon. Cryptology: Classical and Modern with Maplets : [] // CRC Press. — 2012. — 1 червня. — С. 55-57. — ISBN 978-1-4398-7241-3.
- ↑ John F. Dooley. A Brief History of Cryptology and Cryptographi Algorithms : [] // Springer Science & Business Media. — 2013. — 2 вересня. — С. 57. — ISBN 978-3-319-01628-3.
- ↑ Chris Christensen. ADFGVX Cipher : [арх. 27 квітня 2018] : []. — С. 4-8.
- ↑ Саймон Сингх. Книга Шифров:Тайная история шифров и их расшифровки // АСТ: Астрель. — 2009. — 1 липня. — С. 416-417. — ISBN 978-5-271-14453-0.
- ↑ Codes & Codebreakers In World War 1 : [арх. 3 травня 2010] : [].
- ↑ Craig P. Bauer. Secret History: The Story of Cryptology : [] // CRC Press. — 2013. — 2 березня. — С. 191-207. — ISBN 978-1-4665-6186-1.
Література[ред. | ред. код]
General Solution of the ADFGVX Cipher System, J. Rives Childs, Aegean Park Press, ISBN 0-89412-284-3 David Kahn The Codebreakers: The Story of Secret Writing (англ.) // New York: Macmillan. — 1967. — С. 340—347. Rob Curley Cryptography: Cracking Codes (англ.) // Britanncia Educational Publishing. — 2013. — 1 июня. — С. 28-30, 54-56. — ISBN 978-1-62275-036-8. Craig P. Bauer. Secret History: The Story of Cryptology. — CRC Press, 2013. — P. 188—207. — 575 p. — ISBN 978-1-4665-6187-8.