MathType

събота, 26 септември 2015 г.

DES на Python с разяснения (Част I. Някои разяснения и операцията XOR)

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

Започваме тази част на настоящата публикация с малко разяснения. Първото от тях касае въпроса защо Data Encryption Standard (или съкратено "DES"), си струва вниманието, което ще му отделим. В крайна сметка DES е разработен през 70-те години на миналия век и бе поетапно изваден от употреба до началото на този век, следвано от отменянето му като стандарт за шифриране на информация. Причините да му отделим внимание са няколко:

  • DES е прототип на т.нар. "мрежи на Фейстел", които представляват много оригинална идея и напълно валидна архитектура за изграждане на бъдещи шифри.
  • DES е част от т.нар. "Троен DES" (съкращаван като "3DES"), който е все още широко използван, макар и остаряващ бързо, алгоритъм за шифриране на информация.
  • Историята на DES е много показателна за някои чисто политически аспекти на използването на криптография и е тясно свързана със социално-политическия феномен, известен като "криптографски войни" - тема, която бе повдигната отново във връзка с терористичните атаки срещу САЩ и последните разкрития около дейността на АНС.

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

XOR (от "eXclusive OR" или "изключващо или" на български) се изпълнява върху два входа, всеки от който представлява двоична цифра. В информатиката една двоична цифра се нарича много често "бит" - конвенция, към която ще се придържаме от тук нататък.

При входове 0 и 0, резултатът от изпълнението на XOR е 0. При входове 1 и 0, както и при входове 0 и 1, резултатът от изпълнението на XOR е 1. При входове 1 и 1, резултатът от изпълението на XOR е отново нула.

Действието на побитовата операция XOR върху входовете може да се систематизира в следната таблица:

Бит 1Бит 2Резултат
000
101
011
110

Ако си представим за момент, че 1 представлява логическа "истина", а 0 означава логическа "неистина", то тогава действието на XOR може да се опише като връщане на резултат "истина" само ако точно един от двата входа е "истина". От там идва наименованието "изключващо или". Операцията XOR върху логически стойности се нарича "логически XOR". Разграничаването между побитов и логически XOR има смисъл при програмирането на езици от високо ниво, където невинаги логическата истина и неистина се представят с по един бит - единица или нула.

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

Фиг. 1. Архитектурна диаграма на полусуматор, реализиран с AND и XOR. Полусуматорът приема два бита вход и ги събира, извеждайки на изхода един бит резултат и един бит пренос към по-старша позиция. Така например 1+0 дава резултат 1 и пренос 0, а 1+1 дава резултат 0 и пренос 1. За да се постигне събирането на числа с по-голяма разрядност, например 32 двоични цифри (бита), множество полусуматори се свързват заедно.
Оригинално изображение: Wikipedia

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

В компютърните системи и цифровата електроника, XOR рядко се използва върху входове с дължина само един бит. Компютърните системи, от съображения за бързодействие, манипулират информацията на порции с по-голяма дължина, най-малката от която е т.нар. "байт", който представлява 8-битово число, т.е. такова, което може да бъде представено с 8 двоични цифри. Когато говорим за прилагане на XOR, ние много често имаме предвид прилагането му именно към две такива "порции" с фиксирана дължина в битове. В такъв случай, XOR се изпълнява за всяка двойка битове от двата входа. Например:

10011010
XOR 
10101010
========
00110000

Резултатът от горния пример (последният ред) е получен, като към всяка двойка битове, стоящи една под друга, е приложена операция XOR. Точно така тази операция се изпълнява в цифровата електроника и в частност - компютърните процесори. Именно затова наричаме XOR "побитова" операция.

XOR има много интересното свойство, че прилагането му към две еднакви числа дава винаги нула.

10111010
XOR 
10111010
========
00000000

Това свойство доста често се използва за оптимизация на програми на машинен код и асемблер, тъй като изпълнението на XOR върху дадена променлива е по-бързо в електрониката, отколкото поставянето на константна стойност 0 в нея. За запознатите с асемблера на Intel процесорите това изглежда така:

XOR AX,AX

e по бързо от:

MOV AX,0

но пък с него може са се постави само стойност 0 в регистъра АX. За всяка друга стойност все още се нуждаем от MOV.

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

10111010
XOR 
00000000
========
10111010

XOR e комутативна операция. Комутативността означава, че операндите могат да сменят местата си без резултатът от операцията да се променя. Т.е.

11011010             10100010
XOR           =      XOR
10100010             11011010 
========             ========
01111000             01111000
Във формули, XOR доста често се записва със знака $\oplus$. Ние ще се придържаме към тази конвенция и ще запишем това равенство по-кратко като $11011010_{(2)} \oplus 10100010_{(2)} = 10100010_{(2)} \oplus 11011010_{(2)}$.[1]. Как обаче да сме сигурни че това ще е вярно за всеки две числа?

Всъщност, това не е толкова трудно. Тъй като XOR работи бит по бит, достатъчно е да се върнем към първата таблица от началото на настоящата част, която даваше резултатите от изпълнението на XOR върху отделни битове. Ако успеем да докажем, че бит по бит XOR е комутативна, то това ще е вярно и за операции върху числа с произволна дължина. Това е лесно, тъй като възможните комбинации от два бита за вход са само 4 и те са в таблицата. Остава само да изчислим дали $Бит1 \oplus Бит2 = Бит2 \oplus Бит1$.

Бит 1Бит 2Резултат
000
101
011
110

Когато двата входа са еднакви, е очевидно че местата им могат да се сменят произволно. Остава да разгледаме случая вярно ли е, че $1 \oplus 0 = 0 \oplus 1$. Таблицата по-горе, с която дефинирахме операцията показва, че $1 \oplus 0 = 1$ и $0 \oplus 1 = 1$, т.е. двете са равни и XOR трябва да е комутативна.

Току-що доказахме нещо доста очевидно. Тази техника обаче, има потенциал да докаже по-малко очевиден, но важен факт. Ако имаме три числа, то $(a \oplus b) \oplus c = a \oplus (b \oplus c)$. Това свойство се нарича асоциативност и най-общо означава, че когато имаме ситуация като например $a \oplus b \oplus c \oplus d \oplus e$ ние можем да изберем произволно от коя двойка съседни операнди да започнем извършването на действията, поради което няма нужда от скоби, които да поясняват последователността на действията. Веднага трябва да се подчертае, че асоциативността в никакъв случай не предполага комутативност. Т.е. асоциативността не предполага сама за себе си, че можем да разместваме местата на операндите.

a b c a XOR bb XOR c(a XOR b) XOR ca XOR (b XOR c)
0 0 0 0 0 0 0
0 0 1 0 1 1 1
0 1 0 1 1 1 1
0 1 1 1 0 0 0
1 0 0 1 0 1 1
1 0 1 1 1 0 0
1 1 0 0 1 0 0
1 1 1 0 0 1 1

Първите три колони за трите операнда $a$, $b$ и $c$, обхващат всички възможни комбинации от техните стойности. За всички тях, последните две колони са равни, което доказва, че за три елемента, редът на изпълняване на действията няма значение (стига да не разместваме местата на операндите). Доказването на същото твърдение за повече операнди изисква използване на математическа индукция.

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

  1. Операцията XOR върху n-битови числа дава отново n-битови числа, т.е. множеството на всички n-битови числа е затворено по отношение на операцията XOR
  2. Операцията XOR е асоциативна
  3. Съществува неутрален елемент $e$ за който $e \oplus x=x \oplus e=x$ за всяко $x$ в множеството на n-битовите числа. В случая това е нулата.
  4. Всеки елемент $x$ има обратен елемент $x^{-1}$, такъв, че $x \oplus x^{-1}=e$. (В случая, всеки елемент е обратен сам на себе си, т.е. $x \oplus x =0$.
  5. Операцията XOR е комутативна.

Използвайки този факт за база, е лесно да се докаже, че прилагането на един и същ елемент чрез XOR към множеството на всички n-битови числа всъщност представлява пермутация на това множество (например разглеждайки горната операция като действие на тази на група върху себе си).

Читателите с по-малко математически уклон могат да разгледат следния пример:

a b a XOR b
000 101 101
001 101 100
010 101 111
011 101 110
100 101 001
101 101 000
110 101 011
111 101 010

Той показва, че ако фиксираме единия операнд и го приложим към към всички 8 елемента на множеството на 3-битовите числа, ще получим пермутация на това множество, определена от фиксирания елемент.

С това важно за мрежите на Фейстел свойство завършваме встъпителната част на настоящата публикация.

БЕЛЕЖКИ:

1. Тук (2) означава, че числото е записано в двоична бройна система.

четвъртък, 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' е позицията, при която всеки от роторите е обърнат с буквата А към прозорчето на капака. В този смисъл, тази позиция е "начална" за машината и математическата формула, която я описва. Ако всички оператори винаги започваха шифрирането от настройка 'ААА', машината не би била сигурна, тъй като всеки притежаващ настройките на роторите (и на комутационното табло) би могъл да дешифрира съобщението. Ето защо от оператора на машината се очаква, преди началото на шифрирането или дешифрирането, да придвижи ръчно роторите от тази позиция до друга, начална за съобщението позиця, след което роторите започват да се движат автоматично при натискане на клавиш. Тази друга позиция е разписана в кодовата книга, използвана с машината и се сменя всеки ден, заедно с настройките на комутационното табло.