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

В днешния Математически кът ще разгледам една тема, която обсъждах на годишния научен лагер за деца на Националната детска фондация. Фондацията търси деца и младежи с научни интереси. Не е нужно да сте изключително надарени, но трябва да имате „научна жилка“. Не се изискват много добри оценки от училище. Опитайте, може да ви хареса. Ако сте ученик в начално училище или гимназия, кандидатствайте. Обикновено родителите или училището правят докладите, но това не винаги е така. Намерете уебсайта на фондацията и разберете.

Все повече и повече се говори в училище за "кодиране", позовавайки се на дейността, известна преди като "програмиране". Това е обичайна процедура за преподавателите по теория. Те изкопават стари методи, дават им ново име и "напредъкът" се прави от само себе си. Има няколко области, в които се среща подобно циклично явление.

Може да се заключи, че обезценявам дидактиката. Не. В развитието на цивилизацията понякога се връщаме към това, което е било, е било изоставено и сега се възражда. Но нашият ъгъл е математически, а не философски.

Принадлежността към определена общност означава също „общи символи“, общи четива, поговорки и притчи. Този, който перфектно научи полския език „в Шчебжешин има голям гъсталак, бръмбар бръмчи в тръстиките“, веднага ще бъде разкрит като шпионин на чужда държава, ако не отговори на въпроса какво прави кълвачът. Разбира се, че се задушава!

Това не е просто шега. През декември 1944 г. германците започват последната си офанзива в Ардените с големи разходи. Те мобилизираха войници, които говореха свободно английски, за да пречат на движението на съюзническите войски, например като ги водят в грешна посока на кръстопът. След момент на изненада американците започнаха да задават на войниците подозрителни въпроси, отговорите на които биха били очевидни за човек от Тексас, Небраска или Джорджия и немислими за някой, който не е израснал там. Непознаването на реалностите доведе директно до екзекуцията.

Към основния въпрос. Препоръчвам на читателите книгата на Лукаш Бадовски и Заслав Адамашек „Лаборатория в чекмеджето на бюрото – математика“. Това е прекрасна книга, която брилянтно показва, че математиката наистина е полезна за нещо и че „математически експеримент“ не е празна дума. Включва, наред с други неща, описаната конструкция на "картонената енигма" - устройство, чието създаване ще ни отнеме само петнадесет минути и което работи като сериозна машина за шифроване. Самата идея беше толкова добре позната, споменатите автори са я разработили прекрасно, а аз ще я променя малко и ще я облека в по-математически дрехи.

ножовки

На една от улиците на моето селско селище в предградията на Варшава настилката наскоро беше демонтирана от „trlinka“ - шестоъгълни тротоарни плочи. Пътуването беше неудобно, но душата на математика се радваше. Покриването на равнината с правилни (т.е. правилни) многоъгълници не е лесно. Това могат да бъдат само триъгълници, квадрати и правилни шестоъгълници.

Може би малко се пошегувах с тази духовна радост, но шестоъгълникът е красива фигура. От него можете да направите доста успешно устройство за криптиране. Геометрията ще помогне. Шестоъгълникът има ротационна симетрия - той се припокрива, когато се завърти на 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 имаме съобщение, кодирано така: „Изпращам ви четири парашутни дивизии“. Лесно е да се разбере, че на врага не трябва да се позволява да знае за това. Но дали той ще разбере нещо от това:

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

ЙЙЛЬОАКВМДЕЙЧЕШ,

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

Ние изграждаме Enigma, немска машина за шифроване

Ориз. 2. Пример за първоначалната настройка на нашата машина за криптиране.

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

Както вече споменах, дължа идеята за създаване на такава картонена машина на книгата "Лаборатория в чекмедже - математика". Моята „конструкция” е малко по-различна от тази, дадена от нейните автори.

Машината за шифроване, използвана от германците по време на войната, имаше гениално прост принцип, донякъде подобен на този, който видяхме с шестнадесетичния шифър. Всеки път едно и също нещо: прекъсване на трудното присвояване на писмо към друго писмо. Тя трябва да бъде сменяема. Как да го направя, за да има контрол над него?

Нека изберем не каквато и да е пермутация, а такава, която има цикли с дължина 2. Просто казано, нещо като "Гадериполука", описан тук преди няколко месеца, но обхващащ всички букви от азбуката. Да се ​​споразумеем за 24 букви - без ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Колко такива пермутации? Това е задача за абитуриенти (трябва да я решат веднага). Колко? Много? Няколко хиляди? Да:

1912098225024001185793365052108800000000 (нека дори да не се опитваме да четем този номер). Има толкова много възможности за задаване на позиция "нула". И може да е трудно.

Нашата машина се състои от два кръгли диска. На една от тях, която все още стои, са изписани букви. Това е малко като набиране на стар телефон, където сте набрали номер, като завъртите циферблата докрай. Rotary е вторият с цветова схема. Най-лесният начин е да ги поставите върху обикновен корк с щифт. Вместо корк можете да използвате тънка дъска или дебел картон. Лукаш Бадовски и Заслав Адамашек препоръчват поставянето на двата диска в CD кутия.

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

Ориз. 3. Принципът на действие на нашата хартия Enigma.

Ориз. 3. Принципът на действие на нашата хартия Enigma.

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

Как можеш да познаеш?! И все пак за полските математици (Мариан Реевски, Хенри Зигалски, Йежи Ружицки) се случи. Така получената информация беше безценна. Преди това те имаха също толкова важен принос в историята на нашата отбрана. Вацлав Серпински 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. Ако трябва да запазите бележките си поверителни, използвайте Cardboard Enigma.

Задача 2. Шифровайте вашето име и фамилия на една от „автомобилите“, които сте видели, но (внимание!) с допълнително усложнение: завъртаме не една степен надясно, а според схемата {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - тоест първо с едно, след това с две, след това с три, след това с 2, след това отново с 1, след това с 2 и т.н., такава „вълна“ . Уверете се, че моето име и фамилия са криптирани като CZTTAK SDBITH. Сега разбирате ли колко мощна е била машината Енигма?

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

начини. Следващата двойка може да бъде избрана

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

и т.н. След съответните изчисления (всички числа трябва да се умножат), получаваме

151476660579404160000

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

316234143225,

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

Вижте също: