Шифри та шпигуни

У сьогоднішньому математичному куточку я розгляну тему, яку обговорював на щорічному дитячому науковому таборі, який організував Національний дитячий фонд. Фонд шукає дітей та молодь із науковими інтересами. Ви не повинні бути надзвичайно обдарованими, але у вас має бути «наукова жилка». Дуже хороші шкільні оцінки не є обов'язковими. Спробуйте, може, вам сподобається. Якщо ви учень старших класів початкової школи або старшої школи – подайте заявку. Як правило, звіти складають батьки чи школа, але це не завжди так. Знайдіть сайт Фонду і все дізнаєтесь.

У школі дедалі більше говорять про «кодування», маю на увазі діяльність, раніше відому як «програмування». Це часта процедура педагогів-теоретиків. Вони відкопують старі методи, дають їм нову назву і «прогрес» робиться сам собою. Існує кілька областей, де відбувається таке циклічне явище.

Можна зробити висновок, що знецінюю дидактику. Ні. У розвитку цивілізації ми іноді повертаємося до того, що було, було занедбано і зараз відроджується. Але наш куточок математичний, а не філософський.

Приналежність до певної спільноти також означає «спільні символи», спільні читання, висловлювання та притчі. Того, хто бездоганно вивчив польську мову «в Щебжешині велика гущавина, в очереті гуде жук» — зараз же буде викрито як шпигун чужої держави, якщо не відповість на запитання, що робить дятел. Звичайно, він задихається!

Це не просто жарт. У грудні 1944 року німці з великими витратами розпочали останній наступ в Арденнах. Вони мобілізували солдатів, які вільно розмовляли англійською, щоб дезорганізувати пересування союзних військ, наприклад, відводячи їх у неправильному напрямку на перехрестях доріг. Після хвилинного здивування американці почали ставити солдатам підозрілі питання, відповіді на які були б очевидні людині з Техасу, Небраски чи Джорджії та немислимі для того, хто там не виріс. Незнання реалій призвело до розстрілу.

До точки. Рекомендую читачам книгу Лукаша Бадовського та Заслава Адамашека "Лабораторія в ящику столу - математика". Це чудова книга, яка блискуче показує, що математика справді для чогось корисна і що «математичний експеримент» – це не пусті слова. Він включає в себе, серед іншого, описана конструкція «картонної енігми» — пристрою, на створення якого нам знадобиться всього п'ятнадцять хвилин і яке працює як серйозна шифрувальна машина. Сама ідея була настільки добре відома, згадані автори чудово її пропрацювали, і я трохи зміню її і оберну на більш математичний одяг.

Шифрувальні ножівки

На одній із вулиць мого дачного селища у передмісті Варшави нещодавно розібрали бруківку із “трлінки” – шестикутної тротуарної плитки. Їхати було незручно, але душа математика раділа. Покрити площину правильними (тобто правильними) багатокутниками непросто. Це можуть бути лише трикутники, квадрати та правильні шестикутники.

Може, я трохи пожартував із цією душевною радістю, але шестикутник — гарна постать. З нього можна зробити досить успішний шифрувальний пристрій. Геометрія допоможе. Шестикутник має обертальну симетрію — він перекриває сам себе при повороті на кратність 60 градусів. Поле, позначене, наприклад, літерою А у лівій верхній частині рис. 1 після повороту на цей кут вона також потрапить у поле А - і те саме з іншими літерами. Отже, давайте виріжемо із сітки шість квадратів, кожен із окремою літерою. Отриману таким чином сітку покладемо на аркуш паперу. У вільні шість полів введемо шість букв тексту, який хочемо зашифрувати. Повернемо лист на 60 градусів. З'явиться шість нових полів – введіть наступні шість літер нашого повідомлення.

Рис. 1. Трлінки радості математика.

справа рис. 1 ми маємо текст, закодований таким чином: "На станції стоїть величезний важкий паровоз".

Тепер трохи шкільної математики знадобиться. Скільки способами можна розмістити два числа один щодо одного?

Що за дурне запитання? На двох: або попереду, або інший.

Чудово. І три числа?

Також не складно перерахувати всі налаштування:

123, 132, 213, 231, 312, 321.

Ну, це на чотирьох! Його ще можна чітко прописати. Вгадайте правило порядку, в якому я поставив:

1234, 1243, 1423, 4123, 1324, 1342,

1432, 4132, 2134, 2143, 2413, 4213,

2314, 2341, 2431, 4231, 3124, 3142,

3412, 4312, 3214, 3241, 3421, 4321

Коли цифр п'ять, ми отримуємо 120 можливих налаштувань. Давайте подзвонимо їм перестановки. Кількість можливих перестановок n чисел є добуток 1 · 2 · 3 · … · n, зване сильний і позначені окликом: 3!=6, 4!=24, 5!=120. Для наступного числа 6 маємо 6! = 720. Ми будемо використовувати це, щоб ускладнити наш шестикутний шифрувальний щит.

Вибираємо перестановку чисел від 0 до 5, наприклад 351042. Наш шестикутний диск, що скремблює, має риску в середньому полі — щоб його можна було поставити «в нульове положення» — рискою вгору, як на рис. 1. Ставимо диск таким чином на аркуш паперу, на якому ми повинні писати наш звіт, але пишемо його не відразу, а повертаємо тричі на 60 градусів (тобто на 180 градусів) і в порожні поля вписуємо шість літер. Повертаємося у вихідне становище. Повертаємо циферблат п'ять разів на 60 градусів, тобто на п'ять зубців нашого циферблату. Ми друкуємо. Наступне положення шкали - це положення, повернене на 60 градусів довкола нуля. Четверта позиція – 0 градусів, це початкова позиція.

Ви знаєте, що сталося? У нас з'явилася додаткова можливість – ускладнити нашу машину більш ніж у сімсот разів! Отже, ми маємо дві незалежні позиції «автомата» — вибір сітки та вибір перестановки. Сітка може бути обрана 66 = 46656 способами, перестановка 720. Це дає 33592320 можливостей. Понад 33 мільйони шифрів! Майже трохи менше, т.к. деякі сітки не можна вирізати з паперу.

У нижній частині рис. 1 ми маємо повідомлення, закодоване таким чином: «Я посилаю вам чотири парашутні дивізії». Легко зрозуміти, що ворогові не можна дати знати про це. Але чи зрозуміє він щось із цього:

ТПОРОПВМАНВЕОРДІСЗ

YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY

навіть із підписом 351042?

Ми будуємо Enigma - німецьку шифрувальну машину

Рис. 2. Приклад початкового налаштування нашої шифрувальної машини.

Перестановки (AF) (BJ) (CL) (DW) (EI) (GT) (HO) (KS) (MX) (NU) (PZ) (RY).

Як я вже згадував, ідеєю створення такої картонної машини я завдячую книзі «Лабораторія в ящику столу — математика». Моя "конструкція" дещо відрізняється від тієї, яку дають її автори.

Шифрувальна машина, що використовується німцями під час війни, мала геніально простий принцип, чимось схожий на той, який ми бачили з шестигранним шифром. Щоразу одне й те саме: зламати жорстке присвоєння літери до іншої літери. Він має бути змінним. Як це зробити, щоб мати над ним контроль?

Виберемо не будь-яку перестановку, а таку, що має цикли довжини 2. Простіше кажучи, щось на кшталт «Гадері-напівки», описаної тут кілька місяців тому, але покриває всі літери алфавіту. Умовимося на 24 літери – без ?, ?, ?, ?, ?, ?, ?, ?, ?, v, q. Скільки таких перестановок? Це завдання для випускників середньої школи (вони мають уміти її вирішувати одразу). Скільки? Багато? Декілька тисяч? Так:

1912098225024001185793365052108800000000 (навіть не намагатимемося прочитати цей номер). Є так багато можливостей встановити нульове положення. І це може бути складно.

Наша машина складається із двох круглих дисків. На одному з них, який досі стоїть, написано букви. Це трохи нагадує циферблат старого телефону, де ви набирали номер, повертаючи циферблат до упору. Rotary - другий з колірною схемою. Найпростіше одягти їх на звичайну пробку, використовуючи шпильку. Замість корка можна використовувати тонку дошку або щільний картон. Лукаш Бадовскі та Заслав Адамашек рекомендують поміщати обидва диски в коробку для компакт-дисків.

Уявімо, що ми хочемо закодувати слово ARMATY (Рис. 2 та 3). Встановіть пристрій у нульове положення (стрілка вгору). Літера А відповідає F. Повертаємо внутрішню схему однією букву вправо. У нас є буква R для кодування, тепер вона відповідає A. Після наступного обертання ми бачимо, що буква M відповідає U. Наступне обертання (четверта діаграма) відповідає A – P. На п'ятому циферблаті ми маємо T – А. Нарешті (шосте коло ) Д - Д Противник напевно не здогадається, що наші ФАПЕ будуть для нього небезпечні. А як “наші” читатимуть депешу? У них має бути та сама машина, однаково «запрограмована», тобто з однією і тією ж перестановкою. Шифр починається з нульової позиції. Таким чином, значення F дорівнює A. Поверніть циферблат за годинниковою стрілкою. Літера А тепер асоціюється з Р. Він повертає циферблат вправо і під буквою У знаходить М і т. д. Шифрувальник біжить до генерала: «Генерал, доповідаю, гармати йдуть!».

Рис. 3. Принцип роботи нашої паперової Енігми.

Рис. 3. Принцип роботи нашої паперової Енігми.

Можливості навіть такої примітивної Енігми вражають. Ми можемо вибрати інші вихідні перестановки. Ми можемо – і тут можливостей ще більше – не на одну “засічку” регулярно, а в певному порядку, щоденно змінюється, подібному до шестикутника (наприклад, спочатку на три літери, потім на сім, потім на вісім, на чотири… .. та ін. .).

Як можна здогадатися? І все-таки для польських математиків (Мар'ян Реєвський, Генрика Зигальського, Ежі Ружицький) Вийшло. Інформація, отримана в такий спосіб, була безцінною. Раніше вони мали не менш важливий внесок у історію нашої оборони Вацлав Серпінський i Станіслав Мазуркевичхто порушив кодекс російських військ у 1920 році. Перехоплений кабель дав Пілсудському можливість зробити знаменитий маневр із річки Вепш.

Я пам'ятаю Вацлава Серпінського (1882–1969). Він здавався математиком, котрого зовнішній світ не існував. Про свою участь у перемозі в 1920 році він не міг говорити як з військових, так і з політичних причин (влада Польської Народної Республіки не любила тих, хто захищав нас від Радянського Союзу).

Мал. 4. Перестановка (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).

Рис. 5. Гарна прикраса, але не підходяща для шифрування. Занадто регулярно.

Завдання 1. Na рис. 4 Ви маєте іншу перестановку для створення Enigma. Скопіюйте малюнок на ксерограф. Побудуйте машину, закодуйте своє ім'я та прізвище. Мій CWONUE JTRYGT. Якщо вам потрібно зберегти свої нотатки у секреті, використовуйте картонну Енігму.

Завдання 2. Зашифруйте своє ім'я та прізвище однієї з побачених «машин», але (увага!) з додатковим ускладненням: повертаємо не на одну насічку вправо, а за схемою {1, 2, 3, 2, 1, 2, 3, 2, 1, ….} - тобто спочатку на один, потім на два, потім на три, потім на 2, потім знову на 1, потім на 2 і т.д., такий "вейвлет". Переконайтеся, що моє ім'я та прізвище будуть зашифровані як CZTTAK SDBITH. Тепер ви розумієте, наскільки потужною була машина "Енігма"?

Вирішення завдання для випускників середньої школи. Скільки варіантів налаштування Enigma (у цій версії, як описано у статті)? У нас 24 літери. Вибираємо першу пару букв - це можна зробити на

Методи. Наступна пара може бути обрана на

способи, далі

і т.д. Після відповідних обчислень (усі числа треба перемножити) отримаємо

151476660579404160000

Тоді поділіть це число на 12! (12 факторіал), тому що ті самі пари можуть бути отримані в різному порядку. Так що в результаті отримуємо "всього"

316234143225,

це трохи більше 300 мільярдів, що не здається приголомшливо великою кількістю для сучасних суперкомп'ютерів. Однак якщо взяти до уваги випадковий порядок самих перестановок, це значно зросте. Ми також можемо думати про інші види перестановок.

Дивіться також: