Криптоанализът на Енигма (Част I)

Част I. Зъболекари и шифри или няколко думи за скромното начало на модерната криптография

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

До момента, шифрирането и дешифрирането бяха инхерентно обвързано с проблеми изкуство. Сега можем да Ви предложим нашата машина "Енигма", която е универсално решение на тези проблеми.

Рекламна брошура на Енигма машина, средата на 20-те години на 20-ти век

Всяка история има своето начало. Наистина добрите истории обикновено имат няколко. Историята на криптоанализа на Енигма, повлиял на изхода на най-ожесточения сблъсък в историята на човечеството, е именно такава. Поради това нейното начало може да бъде отнесено към няколко различни момента от време.

Едно необичайно начало може да бъде събитие от много далечната 1854 година. Тогава зъболекарят от Бристол Джон Холл Брок Твейтс пише до Journal Of Society and Arts за да представи свое откритие. Откритието е нов шифър, който зъболекарят възнамерява да патентова. Това събитие привлича вниманието на един от изтъкнатите английски учени по това време - Чарлз Бабидж. В писмо до списанието, Чарлз Бабидж отбелязва, че патентните претенции на г-н Твейтс са неоснователни, тъй като неговият шифър се оказва вариант на вече добре известен шифър. Това е шифърът, станал известен като "Шифър на Виженер".

Преоткриван много пъти в историята, описан като идея за пръв път през 1553 година от Джован Батиста Беласо и усъвършенстван от Блез де Виженер, шифърът до този момент е обгърнат от аура на непобедимост, тъй като за 3 столетия не е намерен универсален начин за пробиването му. Малкото успехи при разшифроването му до тогавашния момент разчитат на това, че криптоаналитикът има някаква предварителна информация за съдържанието на съобщението, което е шифрирано с помощта на шифъра.

Шифърът на Виженер много скоро изправил Бабидж пред интересен проблем, тъй като доста обиденият зъболекар му отправил публично предизвикателство - да пробие два последователни пъти "неговия" шифър. Оказало се, както се уверили и читателите на списанието, че Бабидж успял. За съжаление той никога не разкрил методите си, оставяйки славата на майора от пруската армия Фридрих Касиски (да, фамилията е полска), който през 1863 година публикува "Тайнопис и изкуството на дешифрирането". В книгата е изложена обща атака срещу шифъра на Виженер. По същото време тече Американската гражданска война и юнионистите редовно четат съобщения на Конфедерацията, които се шифрират с вариант на същия шифър.

Шифърът на Виженер и моментът на неговото пробиване са важна част от нашата история, тъй като от опитите за "поправяне" на този доста елементарен от днешна гледна точка шифър водят до две важни открития, случили се по почти едно и също време.

Първото от тези открития са роторните машини за шифриране, които доминират криптографията до появата и внедряването на цифровата електроника през 70-те и 80-те години на миналия век. Най-популярният, но далеч не единствен, представител на тези машини е именно Енигма.

Второто откритие е алгоритъм за шифриране, за чиято теоретична непробиваемост имаме безспорни доказателства. Всъщност ние знаем, че използван правилно, този шифър би устоял и дори на атака от извънземни, които евентуално биха го атакували с техните безкрайно напреднали компютърни технологии и математически знания. (При условие, разбира се, че тези извънземни не могат някак мистериозно да прекосят времето и пространството назад към момента и мястото, в което даденото съобщение е било шифрирано или дешифрирано) ^[1].

Блез де Виженер (1523-1596) и Чарлз Бабидж (1791-1871)

Шифърът на Виженер също възниква като доста елементарно, но ефективно, подобрение на Шифъра на Цезар, който е известен от античността. Последният замества всяка буква от азбуката с друга буква, която се намира на определен брой фиксирани позиции напред или назад в естествения ред на буквите. Така например, според историческите източници, Цезар замествал A с D, B с Е, C с F и т.н. Тоест, той замествал всяка буква с третата след нея буква в азбуката. Този подход има фатален недостатък, известен ни поне от средновековието. Шифърът на Виженер възниква именно като опит за премахване на този недостатък. (Изпробвайте Шифъра на Цезар тук).

Въпреки че Шифърът на Цезар замества буквите, всяка буква се замества всеки път с една и съща друга буква. Това позволява извършването на лесна атака - т.нар. "честотен анализ". В думите на реалните езици, някои букви се срещат по-често от останалите. Така например, най-често срещаните букви в английския език са гласните е,а,o,i,u ("e" е най-често срещаната буква, следвана от "а" и т.н. в указания ред). Независимо с коя буква се замества "е", подходът на Шифъра на Цезар ще доведе до това, че тази буква ще бъде най-често срещаната в шифрираното съобщение, ако то е на английски език. Криптоаналитик тогава би преброил колко пъти се среща всяка буква в шифрираното съобщение и с няколко проби би открил местата на всички гласни, което на свой ред би довело до дешифрирането на цели думи. От тези думи на свой ред ще се получи информация за това как се заместват и много от съгласните, което ще доведе до разшифроването на цялото съобщение.

Шифърът на Виженер разчита на ключ, тоест някаква стойност, която е известна само на автора на съобщението и на неговия получател. Този ключ е обикновен текст - дума или цяло изречение, без интервалите. Ключът определя с каква буква ще бъде заменена всяка следваща буква от съобщението. За да извърши заместването, шифърът използва помощно средство, наречено Таблица на Виженер или, ако трябва да използваме оригиналното понятие, "tabula recta".

	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
A	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
B	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A
C	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B
D	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C
E	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D
F	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E
G	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F
H	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G
I	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H
J	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I
K	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J
L	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K
M	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L
N	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M
O	O	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N
P	P	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O
Q	Q	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P
R	R	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q
S	S	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R
T	T	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S
U	U	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T
V	V	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U
W	W	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V
X	X	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W
Y	Y	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X
Z	Z	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y

За да шифрира едно съобщение, авторът измисля ключ, например "SQRTLTAF" и го повтаря толкова пъти, колкото е необходимо, за да достигне същия брой букви, колкото е съобщението. Т.е. ако съобщението е "ATTACKATNOONTOMORROW" (20 букви), горният ключ ще бъде "допълнен" до 20 букви чрез повторение - "SQRTLTAFSQRTLTAFSQRT".

По този начин, след като съобщението и ключът се поставят един под други, се формират двойки буви - една от съобщението и една от ключа. След това, авторът търси тези двойки в Таблицата на Виженер. Буквата от съобщението се търси в заглавието на колоните (първият ред на поместената по-горе таблица, изписан с удебелен шрифт), а буквата от ключа се търси в заглавието на редовете (първата колона на таблицата, изписана с удебелен шрифт). Там където колоната, избрана от буквата на съобщението, и редът, избран от буквата на ключа, се пресекат, се намира буквата, която се записва в шифрираното съобщение.

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

На този етап читателят е приканен да забележи, че при ключ "DDDDDDDD...", Шифърът на Виженер би бил еквивалентен на Шифъра на Цезар, а ключ "ABCDEFGHIJKLMNOPQRSTUVWXYZ" би отговарял на използването редовете на tabula recta в последователен ред. Въщност tabula recta възниква преди шифъра на Виженер и опосредства множество схеми, при които няма ключ, а редовете на таблицата се използват в някакъв фиксиран ред, например последователно.

Голямото нововъведение при Шифъра на Виженер е използването на ключ вместо фиксирана последователност от редове. Разбира се, тъй като фиксираните последователности от редове могат да бъдат идентифицирани с даден ключ от Шифъра на Виженер, това означава, че този шифър за пръв път в историята е направил прехода от фиксиран ключ за всички ползватели към индивидуален ключ, който може да се подели само между две страни! Бихме могли да опишем този забележителен факт и по друг начин - тайната на комуникацията за пръв път в историята не зависи от опазването на шифриращия алгоритъм в тайна от потенциалните опоненти! Днес това е известно като Принцип на Керкхоф и е основно изискване към всеки модерен шифър.

Горните факти могат да бъдат обобщени с на малко по-математизиран език. Шифърът на Цезар прилага една и съща пермутация - (DEFGHIJKLMNOPQRSTUVWXYZABC) - към буква от текста на съобщението, докато Шифърът на Виженер позволява буквата от ключа да определи коя от 26 пермутации да бъде използвана към дадената буква от съобщението.

Много често вместо tabula recta във втората половина на 19-ти век се е използвал шифродиск, като показания тук диск на Конфедерацията от гражданската война в САЩ. Шифродискът се състои от два концентрични кръга с букви, които се въртят един спрямо друг. Той е по-компактно средство от таблицата, като на всяка следваща стъпка нужният ред (пермутация) се получава, като се завърти дискът на нужната позиция.

Какво би видял криптоаналитик, ако се опита да приложи честотния анализ към съобщение, кодирано с Шифъра на Виженер? Накратко, честотният анализ няма да работи без модификация, защото броят на различните букви в кодираното съобщение ще е приблизително еднакъв. Нека да опитаме да илюстрираме това свойство на шифъра с пример. Нека приемем, че съобщението е "ALOHA". Ако ключът е избран произволно, това означава, че на позиция 1 на ключа ще има случайно избрана буква, която ще избере с равна вероятност една от 26-те пермутации в tabula recta. Ако на позиция 1 на ключа се намира буквата "A", това ще избере първата пермутация (ред), която ще превърне "A" от съобщението в "В". Ако на позиция 1 обаче има буквата "B", това е втората пермутация, която ще превърне "А" от съобщението в "C" и т.н.

Не е трудно да се види, че независимо коя буква е на първа позиция в съобщението, една от 26-те възможни пермутации, определени от първата буква на ключа, може да превърне буквата от съобщението във всяка друга буква. Нещо повече, тъй като пермутациите са еднакво вероятни, това означава, че независимо каква е буквата на съобщението, ключът ще я превърне с равна вероятност във всяка друга възможна буква. Това е вярно и за всяка друга позиция в съобщението. Читателят може да проследи например колона F на Таблицата на Виженер, за да види коя пермутация превръща F във A,B,C,D и пр. букви в азбуката.

На пръв поглед това е доста безнадеждно. Ако имаме само шифротекста, ние сме пред тежка задача. Да речем, че той е "FEZE". Ако ключът е бил "SQLR", съобщението е гласяло "NOON". Ако ключът е бил "NELA", съобщението е гласяло "STOP". Ако ключовете са произволно избрани, всеки от тях е еднакво вероятен, а вероятността нашето съобщение да е произлязло от която и да било четирибуквена дума е напълно еднаква с вероятността на която и да било друга четирибуквена дума. Можем да мислим за шифрирането като процес, който "маскира" структурата на текста до пълна неузнаваемост. Този процес може да бъде "обърнат" само ако знаем ключа.

И така, как Касиски успява да разбие шифъра? Той прави много просто наблюдение. Тъй като типично съобщенията са много по дълги от ключа (за разлика от горния четирибуквен пример), ключът се повтаря многократно. Това нарушава напълно случайния му характер, което се отразява катастрофално върху сигурността за шифъра. Касиски забелязал, че повторението на ключа позволява Шифъра на Виженер да се разглежда като множество отделни копия на Шифъра на Цезар. Така например, ако ключът (без повторенията) е дълъг 7 символа, всеки символ от шифрирания текст на позиция 1, 8, 15, 22, 29, 26, 33 и т.н. е шифриран с една и съща пермутация (не много различно от Шифъра на Цезар). Същото е вярно за позиции 2,9,16,23,30,27,34 и т.н., макар тук пермутацията да е различна от тази на предните позиции. Също така 3,9,17,24,31,28,35 и т.н. са шифрирани с една и съща пермутация. Тоест, Шифърът на Виженер "вплита" няколко Шифъра на Цезар, чиито брой зависи от дължината на ключа.

Aко вместо преброяване на всички символи от съобщението ние изброим честотата на символите само на позиции 1,8,15,22,29,26,33 и т.н., ние ще имаме Шифър на Цезар (една единствена пермутация, макар и не точно такава, заместваща всеки символ с третия след него). Честотният анализ на тази последователност от символи ще работи без проблеми, което ще ни позволи за отгатнем множество букви. След това ще преминем към броенето на честотите на символите от позиции 2,9,16,23 и т.н. Процедурата ще се повтори за всички възможни групи позиции. Колкото по-дълго е съобщението и по-кратък е ключа, толкова по-лесно ще се справим със задачата на дешифрирането.

По този начин за да разбием Виженер и всички други "позиционни" схеми преди него, на нас ни трябва просто да знаем дължината на ключа. Това разбира се, може да се установи с проба, особено когато говорим за кратки ключове. При всички грешни дължини, броенето само на първите групи, формирани от символите на позиции 1, 1+предполагаема_дължина,1+2*предполагаема_дължина,1+3*предполагаема дължина и т.н. няма да дава някаква отчетлива тенденция и броят на буквите от всеки вид ще е приблизително еднакъв. При успешно отгатване на дължината на ключа обаче, ще видим ситуация, при която едни букви ще се срещат значително по-често от останалите.

БЕЛЕЖКИ:

1. Авторът си позволи да "открадне" тази ярка илюстрация от Брус Шнайер, който получава безспорния кредит за формулирането и.

Емулатор на немска шифровъчна машина Енигма

Част II. Детайли за роторите и математически модел на машината

Настоящата статия е разделена в няколко публикации на блога:

Част I. Принцип на работа на Енигма машина

Част II. Детайли за роторите и математически модел на машината

Част III. Програмният код

Последна редакция: 28.09.2015г.

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

Всички възможни на теория конфигурации на един ротор са равни на всички възможни пермутации на 26 елемента и възлизат на $26! \approx 2^{88}$^[1]. Всеки ротор на Енигма машината обаче е свързан статично и неговата конфигурация не може да се променя. Предвид трудностите при превозването и съхраняването на такива ротори (Енигма е замислена като портативна шифровъчна машина), не е изненада, че Енигма машините се използват и разпространяват с малък брой стандартни ротори.

Типичната цивилна Енигма от 1924 година използва само три стандартни ротора известни като IC, IIC, IIIC, чиито настройки са представени в табл. 1.

Ротор 
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Година
Модел

IC
DMTWSILRUYQNKFEJCAZBPGXOHV
1924
Цивилна Енигма А и B
IIC
HQZGPJTMOBLNCIFDYAWVEUSRKX
1924
Цивилна Енигма А и B
IIIC
UQNTLSZFMREHDPXKIBVYGJCWOA
1924
Цивилна Енигма А и B

Таблица 1. Настройки на роторите на цивилна машина Енигма. Пермутациите на отделните ротори могат да бъдат разчетени лесно от колона "ABCD..." на таблицата. Така например ротор IC изпраща А->D, B->M, C->T и т.н.
Източник: Уикипедия

Като цивилна машина, Енигма е проектирана да остане достатъчно сигурна при напълно рационалната презумпция, че конфигурацията на роторите ще е известна на потенциалните опоненти. Тоест, машината следва да гради сигурността си на възможните начални позиции на роторите, които са $26^3\approx 2^{14}$.

Макар за 1928 година, това да изглежда много, тази версия на Енигма машината е разбита с "ръчни" средства почти веднага от няколко разузнавания, включително тези на Англия, Франция и Полша.

Първите варианти на военната Енигма от 1930 година също използват три стандартни ротора. Техните конфигурации са различни от тези на цивилната Енигма, като, разбира се, са взети мерки те да бъдат запазени в тайна. Това значително затруднява криптоанализа на машината.

Най-сериозната пречка пред криптоанализа на военната Енигма обаче, е добавянето на комутационното табло, описано в първата част на настоящата публикация. Първоначално кодовете и операционните процедури предвиждат работа с 6 кабела (разместващи по двойки 12 букви). Към края на 1939 година, кабелите, разпространявани в комплект с военната Енигма машина, нарастват до 10, а операционните процедури и кодовите книги започват да предвиждат настройки с променящ се брой използвани кабели (между 6 и 10).

Разглеждана алгоритмично, военната Енигма използва доста сложен механизъм на работа, който е относително труден за емулация. Използването на малко абстракция обаче, спомага задачата да се опрости значително. За целта, действието на Енигма машината може да се представи като математическа формула.

Подобна формула би изглеждала като композиция от различни пермутации, отговарящи на различните части на машината. Така например, вече бе споменато, че всеки ротор на машината представлява пермутация на 26 елемента, отговарящи на буквите на латинската азбука. Ако отбележим тази пермутация за всеки от роторите, броени от дясно наляво, съответно с $\rho_1, \rho_2, \rho_3$, то действието на роторната сглобка от входа до рефлектора, при неподвижни ротори, може да се представи като $E = \rho_3 \circ \rho_2 \circ \rho_1$, като със знак $\circ$ отбелязваме операцията "композиция на пермутации". Композицията на пермутации не е нищо друго, освен прилагане на дадени пермутации върху даден вход в определен ред. Във формулите, ние също ще прилагаме композицията на пермутации от дясно наляво, т.е. първата приложена пермутация е $\rho_1$ и т.н.

Как обаче тази формула може да се промени, така че да отразява движението на роторите? Ключово наблюдение в тази посока е това, че когато един ротор се придвижи с една позиция напред от началното положение, входовете се разместват по такъв начин, че изход А от предния компонент се озовава срещу вход B на ротора. Това се случва с всички останали букви /входове/. Т.е. B->C, C->D ... A->Z. Т.е. движението напред внася една пермутация в уравнението, която се прилага преди пермутацията на ротора. Тази пермутация може да се обозначи като $\mu = (ABCDEFGHIJKLMNOPQRSTUVWXYZ)$^[2]

Точно обратното се случва на изхода на ротора. Изходът А застава слещу вход Z на следващия компонент. По същия начин B->A, C->B, D->C и т.н. Тази пермутация е $\mu^{-1}=(ZYXWVUTSRQPONMLKJIHGFEDCBA)$. (Вж. фиг. 1a и 1b)

Фигура 1а. Ротор в начална позиция.

Фигура 1б. Роторът от фиг. 1a след една стъпка напред.

$\mu$ и $\mu^{-1}$ са обратни една на друга, т.е. след прилагането на двете върху даден вход, резултатът ще бъде същият вход. $\mu^{-1} \circ \mu(A) = A$, $\mu^{-1} \circ \mu(B) = B$ и т.н. Ние бележим това с $\mu \circ \mu^{-1} = 1$. Тук 1 обозначава неутралната пермутация (тази която изпраща А->A, B->B и т.н., т.е. не размества нищо).

Читателят следва да забележи разликата в двете групи равенства. Едните обозначават действия със самите пермутации (в случая композиция). "Входът" в тези равенства са пермутации и "резултатът" от тези равенства са пермутации. Така например равенството $\mu \circ \mu^{-1} = 1$ може да се прочете като "последователното прилагане на $\mu^{-1}$ и $\mu$ дава нова пермутация" (в случая това е неутралната пермутация, която обозначаваме с 1).

Втората група равенства показва действието на дадена пермутация върху конкретен вход. Тъй като пермутациите са функции, ние можем да запишем действието им върху конкретен елемент от входа с нотацията, позната ни от числовите функции. Така например за пермутацията 1, можем да запишем $1(A)=A$, $1(B)=B$ и т.н., което може да се чете като "пермутацията 1 изпраща А към А", "пермутацията 1 изпраща B към B" и така нататък. По същия начин, равенството $\mu^{-1} \circ \mu(A) = A$ може да се прочете като "пермутацията която се получава след последователно прилагане на $\mu$ и $\mu^{-1}$ изпраща А към А".

Ако най-десният ротор е завъртян с една позиция напред, неговата пермутация и отношение към следващите компоненти на машината може да бъде записана като $\mu^{-1} \circ \rho_1 \circ \mu$. Ако роторът е завъртян две позиции напред, неговата пермутация може да бъде записана като $\mu^{-1} \circ \mu^{-1} \circ \rho_1 \circ \mu \circ \mu = \mu^{-2} \circ \rho_1 \circ \mu^2.$ Тук $\mu^2$ може да се разбира като съкращение, обозначаващо последователното прилагане на $\mu$ два пъти. Същото се отнася и за $\mu^{-2}$, което съкращава прилагането на $\mu^{-1}$ два пъти. Този начин на записване доста приятно съвпада с правилата на обичайната алгебра, тъй като $\mu^{-2} \circ \mu^{2} = 1$. (Това не е съвпадение. Всъщност ние избрахме нотация, при която с единица означаваме не числото 1, а неутралната пермутация, именно за да подчертаем алгебричните сходства, която операцията "композиция на пермутации" има с операцията умножение при нормалните числа. Всички други избрани знаци са резултат от прилагането на същата идея.)

Когато роторното колело се превърти с 26 позиции, то застава на оригиналната си позиция, при която входът на ротора А е срещу А на предходния компонент и изходът А е срещу А на следващият компонент. Същото се случва с нашите пермутации. Прилагането на пермутацията $\mu$ 26 пъти дава пермутацията 1, което може да бъде записано като $\mu^{26}=1$. Същото се отнася за обратната пермутация - $\mu^{-26} = 1$.

Въоръжени с тези наблюдения, ние можем да съставим по-коректна формула за поведението на машината от входното колело до рефлектора. Това е просто формулата:

$E = \mu^{-r_3} \circ \rho_3 \circ \mu^{r_3} \circ \mu^{-r_2} \circ \rho_2 \circ \mu^{r_2} \circ \mu^{-{r_1}} \circ \rho_1 \circ \mu^{r_1}$

където $r_1$, $r_2$ и $r_3$ са броя стъпки, които трите роторни колела са изминали от позиция "AAA"^[3]. Разбира се, роторите се въртят и резултатната пермутация $E$ се изменя с всеки следващ символ, набран от клавиатурата на машината.

Нека за момент да се абстрахираме от рефлектора и да се опитаме да опишем обратния път през машината при същата позиция на роторите. Ако при преминаването през роторната сглобка в едната посока вход А e станал Z, B е станал P и т.н., то обратният маршрут по същия електрически път би изпратил Z обратно към А, P обратно към B и т.н. Тоест, ако цялата роторна сглобка дава пермутацията $E$ (вж горната формула), то обратният път би бил такава пермутация $E'$, която комбинирана с оригинала би изпратила А към А, В към В, C към С и т.н. Тоест $E' \circ E = 1$. Тази пермутация ще е точно обратната пермутация на Е, така че може да я запишем като $E^{-1}$. Математически може да бъде доказано, че такава пермутация съществува, и е единствена. Останалата част от работата е може да се извърши интуитивно като "обърнем" всеки елемент на $Е$.

Нека

$E'=\mu^{-r_1} \circ \rho_1^{-1} \circ \mu^{r_1} \circ \mu^{-r_2} \circ \rho_2^{-1} \circ \mu^{r_2} \circ \mu^{{-r_3}} \circ \rho_3^{-1} \circ \mu^{r_3}$

Където с $\rho_1^{-1}$, $\rho_2^{-1}$ и $\rho_3^{-1}$ обозначим обратните пермутации на $\rho_1$, $\rho_2$, $rho_3$, които отразяват какво се случва с електрическия ток, преминаващ наобратно през роторите.

$E' \circ E = \mu^{-r_1} \circ \rho_1^{-1} \circ \mu^{r_1} \circ \mu^{-r_2} \circ \rho_2^{-1} \circ \mu^{r_2} \circ \mu^{{-r_3}} \circ \rho_3^{-1} \circ \mu^{r_3} \circ \mu^{-r_3} \circ \rho_3 \circ \mu^{r_3} \circ \mu^{-r_2} \circ \rho_2 \circ \mu^{r_2} \circ \mu^{-{r_1}} \circ \rho_1 \circ \mu^{r_1} = $

$= \mu^{-r_1} \circ \rho_1^{-1} \circ \mu^{r_1} \circ \mu^{-r_2} \circ \rho_2^{-1} \circ \mu^{r_2} \circ \mu^{{-r_3}} \circ \rho_3^{-1} \circ (\mu^{r_3} \circ \mu^{-r_3}) \circ \rho_3 \circ \mu^{r_3} \circ \mu^{-r_2} \circ \rho_2 \circ \mu^{r_2} \circ \mu^{-{r_1}} \circ \rho_1 \circ \mu^{r_1} = $

$= \mu^{-r_1} \circ \rho_1^{-1} \circ \mu^{r_1} \circ \mu^{-r_2} \circ \rho_2^{-1} \circ \mu^{r_2} \circ \mu^{{-r_3}} \circ \rho_3^{-1} \circ (1) \circ \rho_3 \circ \mu^{r_3} \circ \mu^{-r_2} \circ \rho_2 \circ \mu^{r_2} \circ \mu^{-{r_1}} \circ \rho_1 \circ \mu^{r_1} = $

$= \mu^{-r_1} \circ \rho_1^{-1} \circ \mu^{r_1} \circ \mu^{-r_2} \circ \rho_2^{-1} \circ \mu^{r_2} \circ \mu^{{-r_3}} \circ (\rho_3^{-1} \circ \rho_3) \circ \mu^{r_3} \circ \mu^{-r_2} \circ \rho_2 \circ \mu^{r_2} \circ \mu^{-{r_1}} \circ \rho_1 \circ \mu^{r_1} = $

$= \mu^{-r_1} \circ \rho_1^{-1} \circ \mu^{r_1} \circ \mu^{-r_2} \circ \rho_2^{-1} \circ \mu^{r_2} \circ \mu^{{-r_3}} \circ (1) \circ \mu^{r_3} \circ \mu^{-r_2} \circ \rho_2 \circ \mu^{r_2} \circ \mu^{-{r_1}} \circ \rho_1 \circ \mu^{r_1} = $

$= \mu^{-r_1} \circ \rho_1^{-1} \circ \mu^{r_1} \circ \mu^{-r_2} \circ \rho_2^{-1} \circ \mu^{r_2} \circ (\mu^{{-r_3}} \circ \mu^{r_3}) \circ \mu^{-r_2} \circ \rho_2 \circ \mu^{r_2} \circ \mu^{-{r_1}} \circ \rho_1 \circ \mu^{r_1} = $

$= \mu^{-r_1} \circ \rho_1^{-1} \circ \mu^{r_1} \circ \mu^{-r_2} \circ \rho_2^{-1} \circ \mu^{r_2} \circ (1) \circ \mu^{-r_2} \circ \rho_2 \circ \mu^{r_2} \circ \mu^{-{r_1}} \circ \rho_1 \circ \mu^{r_1} = $

$= \mu^{-r_1} \circ \rho_1^{-1} \circ \mu^{r_1} \circ \mu^{-r_2} \circ \rho_2^{-1} \circ (\mu^{r_2} \circ \mu^{-r_2}) \circ \rho_2 \circ \mu^{r_2} \circ \mu^{-{r_1}} \circ \rho_1 \circ \mu^{r_1} = $

$= \mu^{-r_1} \circ \rho_1^{-1} \circ \mu^{r_1} \circ \mu^{-r_2} \circ \rho_2^{-1} \circ (1) \circ \rho_2 \circ \mu^{r_2} \circ \mu^{-{r_1}} \circ \rho_1 \circ \mu^{r_1} = $

$= \mu^{-r_1} \circ \rho_1^{-1} \circ \mu^{r_1} \circ \mu^{-r_2} \circ (\rho_2^{-1} \circ \rho_2) \circ \mu^{r_2} \circ \mu^{-{r_1}} \circ \rho_1 \circ \mu^{r_1} = $

$= \mu^{-r_1} \circ \rho_1^{-1} \circ \mu^{r_1} \circ \mu^{-r_2} \circ (1) \circ \mu^{r_2} \circ \mu^{-{r_1}} \circ \rho_1 \circ \mu^{r_1} = $

$= \mu^{-r_1} \circ \rho_1^{-1} \circ \mu^{r_1} \circ (\mu^{-r_2} \circ \mu^{r_2}) \circ \mu^{-{r_1}} \circ \rho_1 \circ \mu^{r_1} = $

$= \mu^{-r_1} \circ \rho_1^{-1} \circ \mu^{r_1} \circ (1) \circ \mu^{-{r_1}} \circ \rho_1 \circ \mu^{r_1} = $

$= \mu^{-r_1} \circ \rho_1^{-1} \circ (\mu^{r_1} \circ \mu^{-{r_1}}) \circ \rho_1 \circ \mu^{r_1} = $

$= \mu^{-r_1} \circ \rho_1^{-1} \circ (1) \circ \rho_1 \circ \mu^{r_1} = $

$= \mu^{-r_1} \circ (\rho_1^{-1} \circ \rho_1) \circ \mu^{r_1} = $

$= \mu^{-r_1} \circ (1) \circ \mu^{r_1} = $

$= \mu^{-r_1} \circ \mu^{r_1} = $

$=1 $

Можем да извършим обозначените действия, тъй като операцията "композиция на пермутации" е асоциативна, т.е. няма значение в какъв ред ще извършим действията. Резултатът показва, че $E'$ е обратната пермутация, която търсим. Тя е единствената, която може да отрази какво се случва при обратното движение на тока през роторната сглобка. Читателят, оцелял до тук, е приканен да забележи, че чрез абстракцията на математическите формули, ние получихме възможността да разсъждаваме за иначе много сложен алгоритъм. И дори повече, почти имахме възможността да убедим себе си и останалите, че нашите разсъждения (респективно нашият алгоритъм) са коректни.

Преди токът да се върне по роторната сглобка обаче, Енигма машината го прекарва през рефлектора. Ако обозначим пермутацията на рефлектора с $\theta$, пълната формулата за работата на сглобката и рефлектора придобива вида:

$E = \mu^{-r_1} \circ \rho_1^{-1} \circ \mu^{r_1} \circ \mu^{-r_2} \circ \rho_2^{-1} \circ \mu^{r_2} \circ \mu^{{-r_3}} \circ \rho_3^{-1} \circ \mu^{r_3} \circ \theta \circ \mu^{-r_3} \circ \rho_3 \circ \mu^{r_3} \circ \mu^{-r_2} \circ \rho_2 \circ \mu^{r_2} \circ \mu^{-{r_1}} \circ \rho_1 \circ \mu^{r_1}$

По същият начин комутационното табло добавя две взаимно обратни пермутации към тази формула. Ако обозначим "правата" пермутация с $\beta$, то тогава формулата придобива вида:

$E = \beta^{-1} \circ \mu^{-r_1} \circ \rho_1^{-1} \circ \mu^{r_1} \circ \mu^{-r_2} \circ \rho_2^{-1} \circ \mu^{r_2} \circ \mu^{{-r_3}} \circ \rho_3^{-1} \circ \mu^{r_3} \circ \theta \circ \mu^{-r_3} \circ \rho_3 \circ \mu^{r_3} \circ \mu^{-r_2} \circ \rho_2 \circ \mu^{r_2} \circ \mu^{-{r_1}} \circ \rho_1 \circ \mu^{r_1} \circ \beta$

Трябва да се вмъкне, че операцията композиция на пермутации не е комутативна. Ако две пермутации не са обратни една на друга, техните места във формулата (респективно реда на прилагането им) не могат да се разместват, без това да измени резултата от изчислението. Горната формула не може да се опрости по начина, демонстриран по-рано, тъй като $ \theta $ разделя компонентите на всички двойки взаимо обратни пермутации. Ако това не беше така, криптоанализът на Енигма машината щеше да се свежда само до намирането на $\theta$, защото останалите неизвестни пермутации щяха да могат да се "съкратят" от равенството.

Получената формула всъщност коректно отразява работата на военната Енигма машина. С използването на формулата, разработването на алгоритъм за емулация всъщност драстично се опростява, като се свежда до прилагане на серии от пермутации. Съществува обаче една последна "липсваща" пермутация, чиято история е един от най-интересните дребни детайли, довели в крайна сметка до загубата на Германия във войната.

Цивилната Енигма няма комутационно табло. За сметка на това, клавишът А от клавиатурата не е свързан директно с изход А на входното колело. Вместо това електрическите проводници са разместени. За цивилната Енигма това няма особен смисъл, тъй като на теория всеки би могъл да си купи копие на машината и да я разглоби, разбирайки как са разместени кабелите. Криптоаналитиците на съюническите нации са смятали, че излизайки от комутационния панел и влизайки във входното колело на машината, кабелите на военната Енигма по същия начин ще са разбъркани, внасяйки в процеса още една неизвестна пермутация. Всички бъркали, което в крайна сметка осуетило усилията на повечето от разузнаванията.

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

Именно това предположениe (наред с много красива математика) в крайна сметка довело до това, че Полша през 1939 била първата нация, която успяла системно и рутинно да декодира трафика на комуникационните мрежи (разбирани като набор от радиостанции, работещи с една и съща кодова книга), подсигурени от военната версия на Енигма машината.

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

Рефлектор 
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Година
Модел

A
EJMZALYXVBWFCRQUONTSPIKHGD
Военна Енигма
B
YRUHQSLDPXNGOKMIEBFZCWVJAT
Военна Енигма
C
FVPJIAOYEDRZXWGCTKUQSBNMHL
Военна Енигма

Табл. 2. Рефлектори на военната версия на Енигма машината.
Източник: Уикипедия

Ротор 
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Година
Модел

I
EKMFLGDQVZNTOWYHXUSPAIBRCJ
1930
Военна Енигма
II
AJDKSIRUXBLHWTMCQGZNPYFVOE
1930
Военна Енигма
III
BDFHJLCPRTXVZNYEIWGAKMUSQO
1930
Военна Енигма
IV
ESOVPZJAYQUIRHXLNFTGKDCMWB
Декември, 1938
Военна Енигма, модел М3
V
VZBRGITYUPSDNHLXAWMJQOFECK
Декември, 1938
Военна Енигма, модел М3
VI
JPGVOUMFYQBENHZRDKASXLICTW
Февруари, 1942
Военноморска Енигма, модел M3 и M4
VII
NZJHGRCXMYSWBOUFAIVLPEKQDT
Февруари, 1942
Военноморска Енигма, модел M3 и M4
VIII
FKQHTLXOCBJSPDZRAMEWNIUYGV
Февруари, 1942
Военноморска Енигма, модел M3 и M4

Табл. 3. Ротори на военната версия на Енигма машината.

Оригиналната военна машина от 1930 има три ротора. През 1938 се добавят два допълнителни. Всеки ден, според указанията на кодовата книга се вземат 3 от петте ротора и се монтират в указания ред в машината. Като резулатат от подозренията на германския военноморски флот относно много ефективните действия на съюзниците срещу него през първата половина на 1942, военноморската Енигма е модифицирана и работи с 4 ротора, избрани от 8 възможни - петте "оригинални" и три нови.
Източник: Уикипедия

БЕЛЕЖКИ:

1. Приравняването на даден брой възможности към степен на две е стандартна практика в сравняването на теоретичната сигурност на даден алгоритъм срещу атаки с "груба сила" (изпробване на всички възможни варианти). Често този показател се обозначава като n-битова сигурност. Така например $2^{88}$ би се обозначило като "88-битова сигурност".

2. Тази нотация означава, че пермутацията изпраща А към B, B към C и така нататък до Y->Z и накрая, Z->A.

3. Позиция 'AAA' е позицията, при която всеки от роторите е обърнат с буквата А към прозорчето на капака. В този смисъл, тази позиция е "начална" за машината и математическата формула, която я описва. Ако всички оператори винаги започваха шифрирането от настройка 'ААА', машината не би била сигурна, тъй като всеки притежаващ настройките на роторите (и на комутационното табло) би могъл да дешифрира съобщението. Ето защо от оператора на машината се очаква, преди началото на шифрирането или дешифрирането, да придвижи ръчно роторите от тази позиция до друга, начална за съобщението позиця, след което роторите започват да се движат автоматично при натискане на клавиш. Тази друга позиция е разписана в кодовата книга, използвана с машината и се сменя всеки ден, заедно с настройките на комутационното табло.