Шифре и шпијуни

У данашњем Математичком кутку, погледаћу тему о којој сам разговарао на годишњем научном кампу за децу Националне дечје фондације. Фондација тражи децу и младе са научним интересовањима. Не морате да будете изузетно надарени, али морате да имате „научни траг“. Веома добре школске оцене нису потребне. Пробајте, можда ће вам се допасти. Ако сте виши ученик основне школе или средњошколац, пријавите се. Обично родитељи или школа састављају извештаје, али то није увек случај. Пронађите веб локацију Фондације и сазнајте.

У школи се све више говори о „кодирању“, при чему се мисли на активност која се раније звала „програмирање“. Ово је уобичајена процедура за теоријске едукаторе. Откопају старе методе, дају им ново име, а „напредак“ се прави сам од себе. Постоји неколико области у којима се таква циклична појава јавља.

Може се закључити да дидактику обезвређујем. Не. У развоју цивилизације, понекад се враћамо на оно што је било, напуштено и сада оживљава. Али наш кутак је математички, а не филозофски.

Припадност одређеној заједници значи и „заједничке симболе“, заједничка читања, изреке и параболе. Онај ко је савршено научио пољски језик „у Шчебжешину је велика шипражја, у трсци буба зуји“, одмах ће бити разоткривен као шпијун стране државе ако не одговори на питање шта ради детлић. Наравно да се гуши!

Ово није само шала. У децембру 1944. Немци су уз велике трошкове покренули последњу офанзиву у Арденима. Они су мобилисали војнике који су течно говорили енглески како би ометали кретање савезничких трупа, на пример тако што су их водили у погрешном правцу на раскрсници. После тренутка изненађења, Американци су војницима почели да постављају сумњива питања, чији би одговори били очигледни човеку из Тексаса, Небраске или Џорџије, а непојмљиви некоме ко није тамо одрастао. Непознавање стварности директно је довело до погубљења.

До тачке. Читаоцима препоручујем књигу Лукаша Бадовског и Заслава Адамашека „Лабораторија у фиоци стола – математика“. Ово је дивна књига која сјајно показује да је математика заиста корисна за нешто и да „математички експеримент” нису празне речи. Укључује, између осталог, и описану конструкцију „картонске енигме“ – уређаја за чије креирање ће нам требати само петнаестак минута и који ради као озбиљна машина за шифровање. Сама идеја је била толико позната, поменути аутори су је лепо разрадили, а ја ћу је мало променити и умотати у више математичку одећу.

ножне тестере

На једној од улица мог села дацха у предграђу Варшаве, тротоар је недавно демонтиран од „трлинке“ - шестоугаоне плоче за поплочавање. Вожња је била непријатна, али се душа математичара радовала. Покривање равни правилним (тј. правилним) полигонима није лако. То могу бити само троуглови, квадрати и правилни шестоуглови.

Можда сам се мало нашалио са овом духовном радошћу, али шестоугао је лепа фигура. Од њега можете направити прилично успешан уређај за шифровање. Геометрија ће помоћи. Шестоугао има ротациону симетрију - преклапа се када се ротира за више од 60 степени. Поље означено, на пример, словом А у горњем левом углу шипак. 1 након окретања кроз овај угао, такође ће пасти у поље А - и исто са другим словима. Дакле, хајде да изрежемо шест квадрата из мреже, сваки са различитим словом. Овако добијену решетку стављамо на лист папира. У слободних шест поља унесите шест слова текста које желимо да шифрујемо. Окренимо лист за 60 степени. Појавиће се шест нових поља - унесите следећих шест слова наше поруке.

Пиринач. 1. Трлинкови радости математике.

Десно шипак. 1 имамо овако кодиран текст: „На станици је огромна тешка парна локомотива.

Сада ће вам добро доћи мало школске математике. На колико начина се два броја могу поредати један у односу на други?

Какво глупо питање? За двоје: или један испред или други.

У реду. А три броја?

Такође није тешко навести сва подешавања:

КСНУМКС, КСНУМКС, КСНУМКС, КСНУМКС, КСНУМКС, КСНУМКС.

Па, то је за четири! Још увек се може јасно навести. Погодите правило редоследа које сам поставио:

1234, КСНУМКС4КСНУМКС, КСНУМКС4КСНУМКС, 4КСНУМКС, КСНУМКС4, КСНУМКС42,

14КСНУМКС, 4КСНУМКС, КСНУМКС4, КСНУМКС4КСНУМКС, КСНУМКС4КСНУМКС, 4КСНУМКС,

2314, КСНУМКС4КСНУМКС, КСНУМКС4КСНУМКС, 4КСНУМКС, КСНУМКС4, КСНУМКС42,

34КСНУМКС, 4КСНУМКС, КСНУМКС4, КСНУМКС4КСНУМКС, КСНУМКС4КСНУМКС, 4321

Када су цифре пет, добијамо 120 могућих подешавања. Хајде да их позовемо пермутације. Број могућих пермутација н бројева је производ 1 2 3 ... н, тзв јак и означено узвичником: 3!=6, 4!=24, 5!=120. За следећи број 6 имамо 6!=720. Искористићемо ово да наш хексагонални штит за шифровање учинимо сложенијим.

Бирамо пермутацију бројева од 0 до 5, на пример 351042. Наш хексагонални диск за шифровање има цртицу у средњем пољу - тако да се може ставити "у нулту позицију" - цртицу нагоре, као на сл. 1. Стављамо диск на овај начин на лист папира на коме треба да напишемо наш извештај, али га не пишемо одмах, већ га окрећемо три пута за 60 степени (тј. 180 степени) и уписујемо шест слова у празна поља. Враћамо се на почетну позицију. Окрећемо точкић пет пута за 60 степени, односно за пет "зуба" нашег бројчаника. Ми штампамо. Следећа позиција скале је позиција ротирана за 60 степени око нуле. Четврта позиција је 0 степени, ово је почетна позиција.

Да ли разумете шта се догодило? Имамо додатну прилику – да своју „машину” закомпликујемо више од седамсто пута! Дакле, имамо две независне позиције "аутомата" - избор мреже и избор пермутације. Мрежа се може изабрати на 66 = 46656 начина, пермутација 720. Ово даје 33592320 могућности. Преко 33 милиона шифара! Скоро мало мање, јер неке мреже се не могу исећи из папира.

У доњем делу шипак. 1 имамо поруку шифровану овако: „Шаљем вам четири падобранска одељења. Лако је разумети да непријатељу не треба дозволити да сазна за ово. Али да ли ће разумети ишта од овога:

ТПОРОПВМАНВЕОРДИЗЗ

ЈЈЛьОАКВМДЕЈЧЕШ,

чак и са потписом 351042?

Градимо Енигму, немачку машину за шифровање

Пиринач. 2. Пример почетног подешавања наше машине за шифровање.

Пермутације (АФ) (БЈ) (ЦЛ) (ДВ) (ЕИ) (ГТ) (ХО) (КС) (МКС) (НУ) (ПЗ) (РИ).

Као што сам већ поменуо, идеју о стварању овакве картонске машине дугујем књизи „Лабораторија у фиоци – математика“. Моја „конструкција“ је нешто другачија од оне коју су дали њени аутори.

Машина за шифровање коју су Немци користили током рата имала је генијално једноставан принцип, донекле сличан оном који смо видели са хексадецималном шифром. Сваки пут иста ствар: прекинути тешко додељивање писма другом писму. Мора бити заменљива. Како то учинити да бисте имали контролу над тим?

Хајде да изаберемо не било коју пермутацију, већ ону која има циклусе дужине 2. Једноставно речено, нешто попут „Гадериполука“ описаног овде пре неколико месеци, али покрива сва слова абецеде. Да се ​​договоримо око 24 слова - без а, е, ћ, о, н, с, о, з, з, в, к. Колико је таквих пермутација? Ово је задатак за матуранте (требало би да га одмах реше). Колико? Много? Неколико хиљада? Да:

1912098225024001185793365052108800000000 (да не покушавамо ни да читамо овај број). Постоји толико много могућности за постављање "нулте" позиције. И може бити тешко.

Наша машина се састоји од два округла диска. На једном од њих, који још увек стоји, исписана су слова. Помало личи на бирање старог телефона, где сте бирали број окретањем точкића до краја. Ротари је други са шемом боја. Најлакши начин је да их ставите на обичан чеп помоћу игле. Уместо плуте, можете користити танку плочу или дебели картон. Лукасз Бадовски и Засłав Адамасзек препоручују стављање оба диска у ЦД кутију.

Замислите да желимо да кодирамо реч АРМАТИЈА (Пиринач. 2 и 3). Поставите уређај на нулту позицију (стрелица нагоре). Слово А одговара Ф. Окрените унутрашње коло за једно слово удесно. Имамо слово Р да кодирамо, сада одговара А. После следеће ротације видимо да слово М одговара У. Следећа ротација (четврти дијаграм) даје кореспонденцију А - П. На петом бројчанику имамо Т - А. Коначно (шести круг) И – И Непријатељ вероватно неће претпоставити да ће наши ЦФЦФА бити опасни за њега. А како ће "наши" прочитати депешу? Морају имати исту машину, исту „програмирану“, односно са истом пермутацијом. Шифра почиње на позицији нула. Дакле, вредност Ф је А. Окрените точкић у смеру казаљке на сату. Слово А је сада повезано са Р. Окреће бројчаник удесно и испод слова У налази М итд. Шифрослужитељ трчи генералу: „Генерале, јављам, пушке долазе!“

Пиринач. 3. Принцип рада нашег рада Енигма.

Пиринач. 3. Принцип рада нашег рада Енигма.

Могућности чак и тако примитивне Енигме су невероватне. Можемо изабрати друге излазне пермутације. Можемо – а ту је још више могућности – не по једном „серифу“ редовно, већ у одређеном, свакодневно променљивом редоследу, сличном шестоугаонику (на пример, прво три слова, затим седам, па осам, четири... .. итд. .).

Како можеш да погодиш?! А ипак за пољске математичаре (Маријан Реевски, Хенрик Зигалски, Јерзи Рузицки) десило. Тако добијене информације биле су од непроцењиве вредности. Раније су имали подједнако важан допринос историји наше одбране. Вацлав Сиерпински i Станислав Мазуркевичкоји је прекршио кодекс руских трупа 1920. године. Пресретнути кабл дао је Пилсудском прилику да изведе чувени маневар са реке Вепс.

Сећам се Васслава Сјерпинског (1882-1969). Деловао је као математичар за кога спољашњи свет није постојао. О свом учешћу у победи 1920. није могао да говори и из војних и ... из политичких разлога (власти Пољске Народне Републике нису волеле оне који су нас бранили од Совјетског Савеза).

Пиринач. 4. Пермутација (АП) (БФ) (ЦМ) (ДС) (ЕВ) (ГИ) (ХК) (ИУ) (ЈКС) (ЛЗ) (НР) (ОТ).

Пиринач. 5. Лепа декорација, али није погодна за шифровање. Превише редовно.

Задатак КСНУМКС. Na шипак. 4 имате још једну пермутацију за стварање Енигме. Копирајте цртеж на ксерограф. Направи ауто, кодирај своје име и презиме. Мој ЦВОНУЕ ЈТРИГТ. Ако желите да ваше белешке буду приватне, користите Цардбоард Енигму.

Задатак КСНУМКС. Шифрујте своје име и презиме једног од „аутомобила“ које сте видели, али (пажња!) уз додатну компликацију: не скрећемо за један зарез удесно, већ према шеми {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - то јест, прво за један, затим за два, затим за три, затим за 2, па опет за 1, па за 2, итд., Такав „таласић“ . Уверите се да су моје име и презиме шифровани као ЦЗТТАК СДБИТХ. Сада разумете колико је била моћна машина Енигма?

Решавање проблема за матуранте. Колико опција конфигурације за Енигму (у овој верзији, како је описано у чланку)? Имамо 24 писма. Одаберемо први пар слова - то се може урадити даље

начина. Следећи пар се може изабрати на

начина, више

итд. Након одговарајућих прорачуна (сви бројеви се морају помножити), добијамо

151476660579404160000

Затим поделите тај број са 12! (12 факторијела), јер се исти парови могу добити различитим редоследом. Тако да на крају добијамо "укупно"

КСНУМКС,

то је нешто више од 300 милијарди, што не изгледа као запањујуће велики број за данашње суперкомпјутере. Међутим, ако се узме у обзир случајни редослед самих пермутација, овај број се значајно повећава. Можемо размишљати и о другим врстама пермутација.

Погледајте и: