NoZDR - Перестановочні шифри
Це опис перестановочних шифрів для початківців головоломок.
Проста перестановка
Проста перестановка без ключа – один із найпростіших методів шифрування. Літери перемішуються за будь-якими правилами, але ці правила можуть бути різними – і простими та складними.
Транспозиція
Припустимо, у нас є фраза: «8, можна, але не можна». І ми хочемо її зашифрувати. Найпростіший спосіб - це записати всю фразу задом наперед: «8. Можна порядок слів у реченні залишити вихідним, але кожне слово записати задом наперед:«ОНЖОМ, ВІН ВИРОЖЕНИЙ». А можна міняти місцями кожні дві літери: «ОМНЖ, ООНЕНЬЛЯЗ». Це називається "транспозиція" або проста перестановка у чистому вигляді.
Транспонування
У цьому шифрі використовується таблиця. Повідомлення записується у таблицю по рядках, а освіти шифрованого тексту зчитується по стовпцям. Ну чи навпаки - записується на стовпчиках, а зчитується рядками. Ми хіба що перевертаємо таблицю щодо її діагоналі, що проходить через верхній лівий і нижній правий кути. Математики називають такий спосіб перевороту таблиці транспонування.
Для шифрування потрібно намалювати відповідного розміру таблицю, вписати туди рядковий текст, що шифрується, а потім виписати його по стовпцях в один рядок. Для розшифровки потрібно лише повідомити ключ шифру як розмір таблиці. На малюнку нижче зABCDEFGHIJKL виходитьADGJBEHKCFIL. Погодьтеся, зрозуміти без картинки, що це був алфавіт, практично неможливо.
Отже, наприклад, нам потрібно зашифрувати текст «Я пам'ятник собі спорудив нерукотворний, до нього не заросте народна стежка». У ньому 72 символи. 72 - зручне число, воноділиться без залишку на 2,4,6,8,12,18,24,36, тому можна використовувати таблиці 2х36, 3х24, 4х18, 6х12, 8х9, 9х8, 12х6, 18х4, 24х3, 36х2:). Визначаємось з ключем (розміром таблиці), вписуємо текст по рядках, а потім переписуємо його по стовпцям.
На малюнку вище показані варіанти з таблицями 9×8, 8×9, 4×18 та 18×4. Для третього варіанту (таблиця 4×18) вийде такий текст:
«Яміївкою в атрарі якбоієор, н з ояопт езгртн енатнд панс д увыкмереанта (4:18) »
У цьому випадку я взяв текст «як є», тобто з перепустками між словами та зі розділовими знаками. Але якщо текст осмислений, то розділові знаки і пропуски між словами можна і не використовувати.
Спрощений варіант транспонування (з дворядковою таблицею) – «штакетник». Нагадує «за конструкцією» паркан-шахівницю.
Це дуже простий спосіб шифрування, що часто застосовується школярами. Фраза записується у два рядки: у верхній пишуться непарні літери, у нижній - парні. Потім потрібно виписати поспіль спочатку верхній рядок, потім нижній. Таке шифрування легко зробити і в умі, не виписуючи спочатку два рядки.
«Я пам'ятник собі спорудив нерукотворний» перетворюється на «ЯАЯНКЕЕОДИНРКТОНЙ ПМТИСБВЗВГЕУОВРИ».
Відомо, що у V столітті до н.
Шифрування виконувалося так. На стрижень циліндричної форми, який і називався «блукала», намотували спіраллю (виток до витка) смужку пергаменту і писали на ній уздовж стрижня кілька рядків текступовідомлення. Потім знімали зі стрижня смужку пергаменту з написаним текстом. Літери на цій смужці опинялися хаотично. Для відновлення тексту була потрібна поневіряння такого ж діаметра.
По суті блукала - це наша звичайна плоска таблиця, обгорнута навколо циліндра.
Поодинока перестановка по ключу
Більш практичний метод шифрування, що називається одиночною перестановкою по ключу, дуже схожий на попередній. Він відрізняється лише тим, що колонки таблиці не зсуваються, а переставляються за ключовим словом, фразою або набором чисел завдовжки рядок таблиці. Кодована фраза записується у відповідну таблицю рядково. Потім над таблицею вставляється порожній рядок і до неї вписується ключове слово/фраза/послідовність чисел. Потім це ключове слово/фраза/послідовність сортується за алфавітом/значенням, разом із нею сортуються стовпці, тим самим перемішуючи всю таблицю. Потім зашифрована фраза виписується рядково з цієї таблиці.
Наприклад, можна зробити головоломку на основі судок. Розгадуючому дається текст «-УРОМКУЛО ЬУЕЗЕБЯДЛ НЗЯАТЛИЙ ЦЬБАДНЕПУ ЕММДНИТОЕ ИЧТЮКНОО УНЕЙВЫЧЕС ХІЕПОТОДЦ ПРМГОУИК-» і пропонується вирішити судоку, у якій одна з рядків позначена.
Вирішувати цю головоломку доведеться так: спочатку потрібно записати текст у таблицю 9×9, потім розгадати судоку, намалювати порожню таблицю 9×9, надписати над нею ключовий рядок із позначеного рядка, а потім у таблицю під номерами вписати стовпці відповідно до їх порядкових номерів у вихідній таблиці.
Для дітей можна використовувати цей самий метод, але простіше, навіть без цифр, а відразу намалювавши порядок перестановки у вигляді шляхів.
Подвійна перестановка
Для додаткової скритності можна повторношифрувати повідомлення, яке вже було зашифровано. Цей спосіб відомий під назвою подвійна перестановка. І тому розмір другої таблиці підбирають те щоб довжини її рядків і стовпців були такі, як у першій таблиці. Найкраще, якщо вони будуть взаємно простими. Крім того, в першій таблиці можна переставляти стовпці, а в другому рядку.
Маршрутна перестановка
Звичайне транспонування таблиці (заповнюємо рядками, читаємо по стовпцям) можна ускладнити і зчитувати не стовпцями, а змійкою, зигзагом, по спіралі чи якимось іншим способом, тобто. задавати маршрут обходу таблиці. Такі способи заповнення таблиці якщо й не посилюють стійкість шифру, роблять процес шифрування набагато більш цікавим. Щоправда, процес розшифровки ускладнюється, особливо, якщо маршрут невідомий, і його ще треба дізнатися.
На малюнку зверху послідовність символів «АБВГДЕЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ. » вписана рядково таблицю 6×6, а потім лічена за маршрутом, вказаним лініями. Виходять такі шифрування:
А тут потрібно обходити таблицю «ходом коня», причому маршрут вже намальований, тож це зовсім для маленьких :)
Але якщо подати цю головоломку так, як показано нижче, то буде вже зовсім не просто, так як варіантів обходу конем ходом може бути багато, і потрібно буде знайти з усіх цих варіантів єдиний правильний.
Зашифровано «Пушкін. Мідний вершник".
Перестановка "Чарівний квадрат"
Чарівними (або магічними) квадратами називаються квадратні таблиці з вписаними в їх клітини послідовними натуральними числами від 1 до n 2 (де n - розмірність квадрата), які дають у сумі по кожному стовпцю, кожному рядку та кожній діагоналі одне й те саме число.
У відомому ще у Стародавньому Китаї квадраті Ло-Шу третього порядку (3×3) константа квадрата 15 повторюється 8 разів:
До речі, константу непарного квадрата легко порахувати, помноживши середнє число ряду, з якого складено квадрат, на порядок квадрата. Для квадрата 3-го порядку (3×3) константа дорівнює 12345 6789*3=15.
Далі, щоб зашифрувати якесь послання, потрібно спочатку підібрати або скласти відповідний за розміром чарівний квадрат, потім намалювати порожню таблицю такого ж розміру і вписати букви тексту по черзі в таблицю відповідно до номерів у чарівному квадраті. Потім просто виписуємо рядково букви з таблиці в один довгий рядок. Порядок квадрата повинен дорівнювати округленому у велику сторону кореню з довжини рядка, що шифрується, щоб рядок повністю увійшов у квадрат. Якщо рядок коротший, залишок можна заповнити довільними літерами або цифрами.
На перший погляд, здається, ніби магічних квадратів дуже мало. Проте їх число дуже швидко зростає зі збільшенням розміру квадрата. Так, існує лише один магічний квадрат розміром 3х3, якщо не брати до уваги його повороти та відображення. Рахунок чарівним квадратам 4-го порядку вже йде на сотні, 5-го - на сотні тисяч. Тому магічні квадрати великих розмірів могли бути гарною основою для надійної системи шифрування на той час, оскільки ручний перебір всіх варіантів ключа для цього шифру був немислимий.
Є дуже простий спосіб складання непарних чарівних квадратів, тобто. розміром 3×3, 5×5, 7×7 тощо. Це метод «терас» чи «пірамідок».
Малюється квадрат потрібного розміру і до нього намальовуються ступінчасті тераси (позначені пунктиром). Далі по діагоналях зверху донизу праворуч квадрат заповнюється послідовними числами. Після цього«тераси» переносяться всередину квадрата: праві – ліворуч, ліві – праворуч, верхні – вниз, а нижні – вгору. Виходить чарівний квадрат!
На основі цього можна складати різні головоломки. Якщо використовувати метод безпосередньо, то вийде така головоломка:
Щоб вирішити цю головоломку, потрібно літери з «терас» перенести до квадрата, тоді в квадраті прочитається повне повідомлення. Тут зашифрована фраза "За мостом засідка, пройти не можна, переходьте річку в брід."
А якщо використовувати метод навпаки, то вийде головоломка на кшталт такий.
Щоб її вирішити, треба витягнути відповідні літери із квадрата в «тераси».
Для квадратів 4×4, 6×6 тощо. таких простих способів їх складання немає, тому простіше використовувати готові. Наприклад, квадрат Дюрера.
Решітка, що обертається
Класична гратка Кардано дозволяє приховати шифрування всередині сміттєвого тексту і є гарним прикладом стеганографії. Але якщо грати Кардано використовувати як ключ для перестановочного шифру, то отримаємо новий метод шифрування - решітка, що обертається, або сітку.
Решітка - це квадрат розміром NxN клітин, деякі з яких вирізані. Вирізані клітини можуть торкатися одна одної, зокрема вершинами, і навіть сторонами. В одній клітці одна літера. Вирізані клітини повинні розташовуватися таким чином, щоб жодні дві з них не виявлялися в тому самому місці при поворотах решітки.
За допомогою конструктора, зображеного нижче, можна виготовити 4 16 (4 294 967 296) таких ґрат. Для цього потрібно вирізати строго одне з чотирьох чисел, що повторюються. Для шифрування без сміття потрібно вирізати всі номери від 1 до 16, всього 16 клітинок. Для шифрування зі сміттям деякі числа не можнаВирізати місця, що залишилися після шифрування заповнити будь-якими довільними літерами, це і буде сміття.
Використовувати отримані ґрати треба в такий спосіб. Покласти грати на папір і у вирізані клітини по одній літері почати вписувати текст, що шифрується. Як тільки 16 букв буде вписано, грати повертаються на 90 °, і вписуються наступні 16 букв, і так ще двічі. В результаті буде вписано 64 літери. Якщо текст був коротшим, то в порожні місця, що залишилися на папері, потрібно вписати довільні літери. Довший текст можна розбити на частини по 64 і шифрувати кожну окремо. А можна вписувати у віконця і дві літери.
Є другий спосіб перекладання решітки під час шифрування - не повертати грати на 90 ° три рази, а вперше повернути її на 180 °, вдруге перевернути зворотним боком щодо горизонтальної осі, втретє - знову повернути на 180 °.
То були перестановочні шифри. А тепер можна почитати про Шифри заміни.