MathType

четвъртък, 24 септември 2015 г.

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

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

Настоящата статия е разделена в няколко публикации на блога:
Част I. Принцип на работа на Енигма машина
Част II. Детайли за роторите и математически модел на машината
Част III. Програмният код
Последна редакция: 28.09.2015г.

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

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

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

Ротор ABCDEFGHIJKLMNOPQRSTUVWXYZ Година Модел
ICDMTWSILRUYQNKFEJCAZBPGXOHV1924Цивилна Енигма А и B
IICHQZGPJTMOBLNCIFDYAWVEUSRKX1924Цивилна Енигма А и B
IIICUQNTLSZFMREHDPXKIBVYGJCWOA1924Цивилна Енигма А и 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 Година Модел
AEJMZALYXVBWFCRQUONTSPIKHGDВоенна Енигма
BYRUHQSLDPXNGOKMIEBFZCWVJATВоенна Енигма
CFVPJIAOYEDRZXWGCTKUQSBNMHLВоенна Енигма

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

Ротор ABCDEFGHIJKLMNOPQRSTUVWXYZ Година Модел
IEKMFLGDQVZNTOWYHXUSPAIBRCJ1930Военна Енигма
IIAJDKSIRUXBLHWTMCQGZNPYFVOE1930Военна Енигма
IIIBDFHJLCPRTXVZNYEIWGAKMUSQO1930Военна Енигма
IVESOVPZJAYQUIRHXLNFTGKDCMWBДекември, 1938Военна Енигма, модел М3
VVZBRGITYUPSDNHLXAWMJQOFECKДекември, 1938Военна Енигма, модел М3
VIJPGVOUMFYQBENHZRDKASXLICTWФевруари, 1942Военноморска Енигма, модел M3 и M4
VIINZJHGRCXMYSWBOUFAIVLPEKQDTФевруари, 1942Военноморска Енигма, модел M3 и M4
VIIIFKQHTLXOCBJSPDZRAMEWNIUYGVФевруари, 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' е позицията, при която всеки от роторите е обърнат с буквата А към прозорчето на капака. В този смисъл, тази позиция е "начална" за машината и математическата формула, която я описва. Ако всички оператори винаги започваха шифрирането от настройка 'ААА', машината не би била сигурна, тъй като всеки притежаващ настройките на роторите (и на комутационното табло) би могъл да дешифрира съобщението. Ето защо от оператора на машината се очаква, преди началото на шифрирането или дешифрирането, да придвижи ръчно роторите от тази позиция до друга, начална за съобщението позиця, след което роторите започват да се движат автоматично при натискане на клавиш. Тази друга позиция е разписана в кодовата книга, използвана с машината и се сменя всеки ден, заедно с настройките на комутационното табло.

Няма коментари:

Публикуване на коментар