Шифри и шпиони

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

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

Може да се заклучи дека ја обезвреднувам дидактиката. бр. Во развојот на цивилизацијата, понекогаш се враќаме на она што било, било напуштено и сега повторно оживува. Но, нашето катче е математичко, а не филозофско.

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

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

До точка. На читателите им ја препорачувам книгата на Лукаш Бадовски и Заслав Адамашек „Лабораторија во фиока на маса - математика“. Ова е прекрасна книга која брилијантно покажува дека математиката е навистина корисна за нешто и дека „математичкиот експеримент“ не се празни зборови. Во него, меѓу другото, е вклучена и опишаната конструкција на „картонската енигма“ - уред за кој ќе ни бидат потребни само петнаесет минути за да го создадеме и кој работи како сериозна машина за шифрирање. Самата идеја беше толку добро позната, споменатите автори убаво ја разработија, а јас малку ќе ја сменам и ќе ја завиткам во поматематичка облека.

ножовки

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

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

Ориз. 1. Trlinks на радоста на математиката.

На десната страна сл. 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 имаме вака шифрирана порака: „Ви испраќам четири падобрански дивизии“. Лесно е да се разбере дека на непријателот не треба да му се дозволи да знае за ова. Но, дали ќе разбере нешто од ова:

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

YYLOAKVMDEYCHESH,

дури и со потпис 351042?

Градиме Енигма, германска машина за шифрирање

Ориз. 2. Пример за првично поставување на нашата машина за шифрирање.

Пермутации (AF) (BJ) (CL) (DW) (EI) (GT) (HO) (KS) (MX) (NU) (PZ) (RY).

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

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

Да не избереме каква било пермутација, туку онаа што има циклуси со должина 2. Едноставно кажано, нешто како „Гадериполук“ опишан овде пред неколку месеци, но ги опфаќа сите букви од азбуката. Ајде да се договориме за 24 букви - без ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Колку такви пермутации? Ова е задача за матурантите (треба да можат веднаш да ја решат). Колку? Многу? Неколку илјади? Да:

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

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

Замислете дека сакаме да го шифрираме зборот ARMATY (Ориз. 2 и 3). Поставете го уредот на нулта позиција (стрелка нагоре). Буквата A одговара на F. Завртете го внатрешното коло една буква надесно. Имаме буквата R за кодирање, сега одговара на A. По следната ротација, гледаме дека буквата M одговара на U. Следната ротација (четвртата шема) ја дава кореспонденцијата A - P. На петтото бирање имаме Т - A. Конечно (шести круг) Y – Y Непријателот веројатно нема да погоди дека нашите CFCFA ќе бидат опасни за него. И како „нашите“ ќе го читаат испраќањето? Мора да имаат иста машина, иста „програмирана“, односно со иста пермутација. Шифрата започнува на позицијата нула. Значи, вредноста на F е A. Свртете го бирачот во насока на стрелките на часовникот. Буквата А сега се поврзува со R. Тој го врти бројчаникот надесно и под буквата U го наоѓа М итн. Службеникот за шифрирање трча до генералот: „Генераре, известувам, пиштолите доаѓаат!“

Ориз. 3. Принципот на работа на нашиот труд Енигма.

Ориз. 3. Принципот на работа на нашиот труд Енигма.

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

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

Се сеќавам на Васлав Сиерпински (1882-1969). Изгледаше како математичар за кого надворешниот свет не постоеше. Тој не можеше да зборува за неговото учество во победата во 1920 година и од воени и од ... од политички причини (на властите на Полската Народна Република не им се допаднаа оние што не бранеа од Советскиот Сојуз).

Сл. 4. Пермутација (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).

Ориз. 5. Прекрасна декорација, но не е погодна за шифрирање. Премногу редовно.

Работа на 1. Na сл. 4 имаш уште една пермутација за создавање Енигма. Копирајте го цртежот на ксерографот. Направете автомобил, кодирајте го вашето име и презиме. Мојот CWONUE JTRYGT. Ако треба да ги чувате вашите белешки приватни, користете Cardboard Enigma.

Работа на 2. Шифрирајте го вашето име и презиме на еден од „автомобилите“ што ги видовте, но (внимание!) со дополнителна компликација: не вртиме еден засек надесно, туку според шемата {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - тоа е, прво по еден, потоа по два, потоа по три, потоа за 2, потоа повторно за 1, потоа за 2, итн., Таков „бранови“ . Проверете дали моето име и презиме се шифрирани како CZTTAK SDBITH. Сега разбирате колку моќна била машината Енигма?

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

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

начини, повеќе

итн. По соодветните пресметки (сите броеви мора да се помножат), добиваме

151476660579404160000

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

316234143225,

тоа е нешто повеќе од 300 милијарди, што не изгледа како неверојатно голема бројка за денешните суперкомпјутери. Меѓутоа, ако се земе предвид случајниот редослед на самите пермутации, овој број значително се зголемува. Можеме да размислуваме и за други видови пермутации.

Видете исто така: