Крекинг на простия шифър за замяна

Първо, ще разгледаме начин, при който не е необходимо да разбивате обикновен шифър за замяна - начин да изброите напълно всички опции. Буквата A с открит текст може да бъде съчетана с всяка от 26-те латински букви, буквата B с която и да е от останалите 25, буквата C с която и да е от останалите 24 и т.н. Следователно броят на всички възможни прости азбучни букви е

26 25 24 23. 3 2 1,

което за удобство е обозначено в математически текстове 26! и се чете „двадесет и шест факториал“. Това е огромен брой, повече от 10 до 26-та степен (обикновено се записва 10 26), така че дори компютър, който може да проверява хиляда милиона (т.е. 10 9) азбуки всяка секунда, ще трябва да отдели няколкостотин милиона години за това задача. ... Ясно е, че изчерпателният метод на търсене, който дава задоволителни резултати с шифъра на Юлий Цезар (в него има само 25 варианта), е напълно неподходящ тук.

Практически метод за разбиване на този тип шифър е както следва:

(1) Направете таблица с честотите на знаците, намерени в шифъртекста, т.е. пребройте колко пъти всяка буква се среща там

(2) Опитайте се да определите кой знак в шифъртекста съответства на интервал. Ако криптираното съобщение не е много кратко, тогава това е лесно да се направи, тъй като интервалите и другите пунктуационни знаци представляват 15% до 20% от символите в обикновен английски текст, като повечето от тези знаци всъщност са интервали. Много е вероятно най-често срещаният символ на шифротекст да съответства на интервал. Освен това, ако това предположение е вярно, тогава символите, съответстващи на интервалите, трябва да се появяват в шифъртекста на всеки няколко букви, без значителни пропуски между тях.

(3) След като определите характера на заместващата азбука, съответстваща на интервал, пренапишете шифъртекста, като замените тези знаци в него с интервали. Сега тя се състои от много отделни „думи“ със същата дължина и структура като думите с открит текст. Така например, ако някоя буква се повтаря в думата с открит текст, същото ще се случи и в нейната криптирана "версия".

(4) Опитайте се да дефинирате кодове на шифри за някои често срещани букви като E, T, A, I, O и N. Заедно те обикновено представляват повече от 40% от текста, като E е значително по-напред от останалите в повечето текстове. На този етап таблицата с честотите на поява на знаци в английския език ще бъде от голяма помощ. Такава таблица е предоставена тук (вж. Таблица 2.4); друга таблица, базирана на много по-голяма извадка, се съдържа в глава 7. Всяка е подходяща за разбиване на прост заместващ шифър. Тези таблици трябва да се тълкуват само като подсказки: ако за честите букви честотите им варират малко от пробата до пробата, тогава честотите на редките букви носят малко информация. Таблицата по-долу

Честотата на знаците на английски език за всяка от буквите J, X и Z е с честота 1 на 1000 знака, но в определен текст от 1000 знака всяка от тези букви може да се появи няколко пъти или може да отсъства съвсем. Подобни забележки са валидни за знаковите честоти на повечето езици.

(5) Когато някои фрагменти от думи са възстановени по този начин, потърсете кратки думи, в които една или две букви са неизвестни. Например, ако буквите T и E са вече известни и ако една дума е с дължина три знака с неизвестна буква между буквите T и E, тогава това най-вероятно е думата THE и съответно неизвестната буква H. След това можете да поставите думи като ТОВА, ТОВА, ТАМ и ТОГАВА, получавайки нови съвпадения между символите на открития текст и шифъртекста.

(6) Завършете разбиването на шифъра, като използвате граматическа и контекстуална информация.

Таблица 2.4 Таблица на честотата на поява на английски символи на 1000 знака текст (въз основа на селекция от стихотворения, истории и научни текстове)

Пример 2.2 Прихванато е криптирано съобщение от 53 петцифрени групи. Известни,

че системата за криптиране е обикновен заместващ шифър, интервалите в обикновения текст се заменят с буквата Z, а всички други препинателни знаци се игнорират. Искате да възстановите обикновения текст на съобщението.

Текстът на шифъра е:

MJZYB LGESE CNCMQ YGXYS PYZDZ PMYGI IRLLC PAYCK YKGWZ MCWZK YFRCM ZYVCX XZLZP MYXLG WYTJS MYGPZ YWCAJ MYCWS ACPZY XGLYZ HSWBN ZYXZT YTGRN VYMJC POYMJ SMYCX YMJZL ZYSLZ YMTZP MQYMJ LZZYB ZGBNZ YCPYS YLGGW YMJZP YMJZL ZYCKY SPYZD ZPKYI JSPIZ YMJSM YMJZL ZYSLZ YMTGY GXYMJ ZWYTC MJYMJ ZYKSW ZYECL MJVSQ YERMY MJCKY CKYKG

(1) Първо, съставяме таблица на честотите на поява на знаци (вижте Таблица

(2) Тъй като буквата Y се среща 49 пъти в текст с 265 знака, тоест много по-често от другите (тя представлява около 18% от текста), можем да заключим, че знакът Y на текста на шифъра съответства на космически персонаж

. След Y по честота са буквите Z и M, така че ги отбелязваме като добри кандидати за буквите E и T, или T и E.

(3) В целия шифротекст заменете Y с интервали, като пропуснете интервали между петцифрени групи (те не носят никаква информация) и по този начин получаваме текст с известни дължини на думите. Общият брой думи в съобщението е 50. Нека ги номерираме, за да е по-удобно да се отнасят към тях по-късно.

15 16 17 18 19 20 21 22 23

Полученият текст съдържа голям брой кратки думи и средната дължина на думата е в диапазона от 4 до 5, а разпределението на дължините на думите като цяло изглежда повече или по-малко подходящо за обикновен език. Така че нашето предположение, че буквата Y съвпада с интервал, се потвърждава.

(4) След разглеждане на кратки думи става ясно следното:

- Има само една дума с дължина 1 (номер 29), състояща се от буквата S, така че можем да приемем, че тя е или A, или I *) .

- Имаше само 10 думи с дължина 2; един от тях (CK) се среща три пъти, номерирани 33 и 49, а двама се срещат два пъти - GX номерирани 3 и 41 и SP номерирани 4 и 34.

- Има само 11 думи с дължина 3, от които две се срещат два пъти: MJZ номерирани 1 и 44 и SLZ номерирани 24 и 39.

(5) Тъй като вече направихме предположението, че знаците M и Z съответстват на буквите E и T (или T и E), то триграфът MJZ става или

в E? T или в T? E. Тъй като това се е случило два пъти, е много вероятно това да е THE думата, така че символите M, J и Z са съответно буквите T, H и E. В текста на шифъра има още няколко думи, съдържащи символите M, Z и J, включително:

(23) MJZLZ, който става THE? E, така че L съвпада с R или S;

(26) MJLZZ, който се превръща в TH? EE, откъдето следва, че L е R;

(42) MJZW, което се превръща в THE?, Така че знакът W

съвпада с М или N;

(37) MJSM, което става THAT, ако S съвпада с A, и THIT, ако S съвпада с I.

Следователно заключаваме, че буквата L съответства на буквата R, буквата S съответства на буквата A, а буквата W съответства на буквата M или буквата N.

Тъй като дума 26 е ТРИ *), струва си да проверите дали думата под номер 25 не е цифра. В криптиран вид изглежда като MTZPMQ и благодарение на вече познатите букви се изписва с ясен текст като T? E? T ?, което е много подобно на TWENTY **). Ако това предположение е вярно, тогава знаците T, P и Q са съответно буквите W, N и Y и по този начин неяснотата за знака W е елиминирана - това е буквата M.

(6) Вече установихме открити еквиваленти за девет символа за шифротекст: J, L, M, P, Q, S, W, Y и Z. На тях се отговаря в обикновен текст, съответно H, R, T, N, Y, A, M, интервал и E. Тези девет знака заедно обхващат над 60% от текста, така че ние отново изписваме текста, като отваряме еквивалентите на вече известните символи на шифъртекст и поставяме точки (), където буквите на открития текст все още не са установени.

*) неопределената статия и местоимението "I" на английския език (приблизително превод).

*) номер три - (приблизително превод).

**) номер двадесет - (приблизително превод).

След като направите това, можете да установите още няколко съответствия между символите на отворения и шифров текст. Word 30, вече частично дешифриран като R.M, съдържа двойка еднакви символи в средата и по този начин може да бъде само ROOM, така че G съответства на буквата O. Следователно думата под номер 50 (в шифров текст KG) в ясен текст сега изглежда като .O и следователно знакът K съответства или на S или D, тъй като вече знаем, че не е N или T. Думите с номер 48 и 49 (MJCK и CK) са частично декриптирани като TH.S и .S и от това заключаваме, че знакът C е буквата I. Тъй като символите C и G се срещат в шифъртекста съответно 18 и 14 пъти, те трябва отговаряйте на чести писма. Следователно буквите I и O са подходящи тук, което вече забелязахте от горното.

Замествайки I, O и S вместо C, G и K в частично възстановения текст, получаваме:

MJZáBLGESECNCMQáGXáSPáZDZPMáGIIRLLCPAáCK THEá.RO.A.I.IT.áO.áANáE.ENTáO. RRIN.áIS

8 9 10 11 12 13 14

15 16 17 18 19 20 21 22 23

24 25 26 27 28 29 30 31 32 33

34 35 36 37 38 39 40 41 42 43

44 45 46 47 48 49 50

Сега останалите букви се възстановяват лесно. Пълната азбука за дешифриране (ако обозначавате интервал с ^) изглежда така:

Азбуката на шифъра, използвана от подателя за получаване на шифър текст от обикновен текст, е, разбира се, неговата обратна:

Както за простия шифър за замяна, така и за системата на Юлий Цезар азбуките за криптиране и дешифриране обикновено ще бъдат различни. Освен това за шифъра на Юлий Цезар те ще бъдат еднакви само за стойност на смяна от 13. За прост шифър за замяна това може да се постигне чрез групиране на повечето букви (ако не всички) по двойки, така че вътре във всяка двойка буквите преминават една в друга по време на криптиране, а останалите не се променят. Някои машини за шифроване, включително Enigma и Hagelin, автоматично генерират такива взаимни азбуки, така че процесите на криптиране и дешифриране да са идентични за тях. Това е удобно за потребителя, но в същото време намалява трайността на системата. В прост заместващ шифър, базиран на 26-буквена азбука, броят на възможните заместващи азбуки е намален от 10 26 на по-малко от 10 13 (подробни изчисления могат да бъдат намерени в M2). Въпреки че този брой остава много голям, от криптоаналитична гледна точка това е значително намаляване на силата.

Въпреки това, подобни реципрочни прости заменящи шифри

от време на време те се използват, главно от частни лица, за да попречат на неупълномощени лица да четат съдържанието на своите дневници. Например философът Лудвиг Витгенщайн по време на войната от 1914-1918 г., бидейки в австрийската армия, криптира дневника си по подобен начин.

Анализирайки горния пример, ние отбелязваме, че в шифъртекста липсва буквата U, а буквите J и Z не са в чистия текст. Z се използва в него вместо интервал и в шифъртекста става Y, а буквата J е отвореният еквивалент на шифъртекста U и отсъства в оригиналното съобщение, което изглежда така:

На тази основа ще ви покажа как куп ярки млади хора намериха шампион; мъж със собствени момчета и момичета; мъж на

*) Превод на обикновения текст: „Вероятността да се случи дадено събитие понякога е драстично различна от това, което можем да си представим. Например, малцина биха се съгласили, че ако в една стая бяха събрани двадесет и трима души, то в половината случаи сред тях има двама с един и същи рожден ден. Въпреки това, точно такъв е случаят. " .

Тези, които се интересуват от обяснението на този, на пръв поглед, значителен факт, ние се позоваваме на доказателството към математическото приложение, M3.