Шыфры і шпіёны

У сённяшнім матэматычным кутку я разгледжу тэму, якую абмяркоўваў на штогадовым дзіцячым навуковым лагеры, арганізаваным Нацыянальным дзіцячым фондам. Фонд шукае дзяцей і моладзь з навуковымі інтарэсамі. Вы не павінны быць надзвычай адоранымі, але ў вас павінна быць "навуковая жылка". Вельмі добрыя школьныя адзнакі не абавязковыя. Паспрабуйце, можа вам спадабаецца. Калі вы вучань старэйшых класаў пачатковай школы ці старэйшай школы - падайце заяўку. Як правіла, справаздачы складаюць бацькі ці школа, але гэта не заўсёды так. Знайдзіце сайт Фонду і ўсё даведаецеся.

У школе ўсё больш і больш гавораць аб «кадаванні», маючы на ​​ўвазе дзейнасць, раней вядомую як «праграмаванне». Гэта частая працэдура педагогаў-тэарэтыкаў. Яны адкопваюць старыя метады, даюць ім новую назву, і "прагрэс" робіцца сам сабой. Ёсць некалькі абласцей, дзе адбываецца такая цыклічная з'ява.

Можна зрабіць выснову, што я абясцэньваю дыдактыку. Не. У развіцці цывілізацыі мы часам вяртаемся да таго, што было, было закінута і зараз адраджаецца. Але наш куток матэматычны, а не філасофскі.

Прыналежнасць да пэўнай супольнасці таксама азначае "агульныя сімвалы", агульныя чытанні, выказванні і прытчы. Той, хто бездакорна вывучыў польскую мову «ў Шчэбжэшыне вялікі гушчар, у чароце гудзе жук» — адразу ж будзе выкрыты як шпіён чужой дзяржавы, калі не адкажа на пытанне, што робіць дзяцел. Вядома, ён задыхаецца!

Гэта не проста жарт. У снежні 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 мы маем паведамленне, закадаванае такім чынам: "Я пасылаю вам чатыры парашутных дывізіі". Лёгка зразумець, што ворагу нельга паведаміць пра гэта. Але ці зразумее ён што-небудзь з гэтага:

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

ЫУУУУУУУУУУУУУУУУУУУУУУУУУУУУУУУУУУУУУЙ

нават з подпісам 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 мільярдаў, што не здаецца ашаламляльна вялікім лікам для сучасных суперкампутараў. Аднак калі прыняць да ўвагі выпадковы парадак саміх перастановак, гэты лік значна ўзрасце. Мы таксама можам думаць аб іншых тыпах перастановак.

Глядзі таксама: