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

четвъртък, 27 август 2015 г.

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

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

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

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

Енигма е резултат на дълга еволюция в проектирането на такива шифри. Така например шифри, базирани на заместване, датират чак от времето на Римската империя. Повечето от тях обаче, заместват една буква в нешифрирания текст с една и съща друга буква, за да получат шифрирания текст. Например А винаги се замества с M, B винаги се замества с P и т.н. Този недостатък на заместващите шифри позволява елементарното им дешифриране - факт, който е известен поне от началото на Ренесанса. Енигма преодолява този критичен недостатък като извършва полибуквено заместване - една буква от нешифрирания текст се замества с различна буква всеки път, когато тя бъде срещната в оригиналния текст. Така например при първото срещане на буквата А в нешифрирания текст, тя може да заменена с Q, но при второто срещане на същата буква, тя може да бъде заменена с например L и т.н. Това подобрение изключително усложнява криптоанализа на шифъра.

Енигма машината /фиг. 1/ работи на електро-механичен принцип и е се състои от клавиатура, 3 до 8 на брой роторни колела, рефлектор, комутационен панел и табло с лампи.

Фиг. 1. Енигма машина. 1 - роторни колела /покрити от капак,
част от корпуса на машината/; 2 - табло с лампи;
3 - клавиатура; 4 - комутационен панел, закрит от
капак на дървения корпус на машината.
Оригинално изображение: RadioFan

Роторните колела /фиг. 2, 3/ са най-важните компоненти на машината. От едната страна, роторното колело има 26 електрически контакта с пинчета на пружина. От другата страна, колелото има 26 контактни точки, с които контактуват пинчетата на следващото колело.

Фиг. 2. Роторни колела на Енигма машина.
Оригинално изображение: The Science Museum

Фиг. 3. Роторни колела на Енигма машина. Пиновете са ясно видни на лявото колело, а контактните точки са виждат на дясното колело.
Оригинално изображение: TedColes

Роторните колела съдържат проводници, които свързват всеки пин от едната страна на колелото с точно една контактна точка от другата страна на колелото /фиг. 4/

Фиг. 4. Сглобеното роторно колело /ляво/ и основните му части. Стрелката показва проводниците, които свързват пиновете с контактните точки.
Оригинално изображение: Jerry Proc

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

Роторите на Енгима машината (обикновено 3 или 4, според варианта на машината) се поставят на шпиндел между две крайни неподвижни колела. Едното от тях е неподвижно и несменяемо и е свързано с клавиатурата. То се нарича входно колело. Колелото в другия край се нарича рефлектор. То е неподвижно, но сменяемо, като неговото значение е свързано с възможността машината да бъде използвана за шифриране и дешифриране с едни и същи настройки.

Фиг. 5. Роторни колела на техния шпиндел
Оригинално изображение: Wikipedia

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

Всеки ротор може да се завърта ръчно от оператора на една от 26-те възможни позици. Тези позиции са обозначени обикновено с буквите от латинската азбука - от A до Z. Обозначаването се осъществява от специален пръстен, който се монтира върпу ротора и има изписани буквите, отговарящи на позициите.

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

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

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

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

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

Фиг. 6. Енигма машина с премахнати роторни колела, което позволява да се види добре рефлектора /крайно ляво на изображението/.
Оригинално изображение: www.w1tp.com

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

Така например, ако дадени фиксирани позиции на роторите превръщат А в F преди влизането на електрическия сигнал в рефлектора, рефлекторът превръща F в S, а S при връщането през роторите се превръща в Р, крайният резултат ще бъде превръщането на А в P.

При същите настройки на роторите, те ще превърнат P на входа началното колело в S при входа на рефлектора, който ще превърне S в F. При повторното преминаване през роторите, F ще се превърне в А /Фиг. 7/

Фиг. 7. Диаграма, илюстрираща функцията на рефлектора

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

Комутационното табло, точно като рефлектора, позволява разместване на буквите по двойки. За целта се използват кабели с щекери, които свързват две гнезда. Свързването на две гнезда ефективно кръстосва електрическите пътища. Така например свързването на щекерното гнездо А с щекерното гнездо D ще кръстоса пътищата така, че когато се натисне клавиш А от клавиатурата, към роторната сглобка ще бъде "изпратено" D. Обратно, ако от роторната сглобка "излезe" D, то ще бъде светната лампата, която отговая на A. Щекерно гнездо, което няма подкачен кабел затваря директно веригата, което води до изпращането на същата буква, която е набрана от клавиатурата, към ротора.

Фиг. 8. Eлектрическа схема на Енигма машина.
Оригинално изображение: Matt Crypto

Фиг 8. илюстрира пътя на електрическия ток през комутационното табло при натискане на клавиша А. Всички клавиши са ключове с две затворени позиции. В горна позиция, клавишите осъществяват контакт на таблото с лампите с комутационното табло. В долна позиция /натиснат клавиш/, ключът свързва батерията с комутационното табло, предизвиквайки протичането на ток през него към роторната сглобка.

В ситуацията, илюстрирана на фиг. 8, натискането на клавиша А свързва батерията с гнездо А на комутационното табло. То няма щекер, следователно затваря веригата към позиция А на входното колело. Роторите и рефлекторите извършват заместването, резултат от което е ток на позиция S на входното колело, което е свързано с гнездо S на комутационното табло. Това гнездо има щекер, което прекъсва директната връзка към клавиша S и лампа S, като вместо това насочва електрическия ток към гнездо D, което е свързано с клавиш D. Клавиш D е в горна позиция, което значи че свързва гнездо D с лампа D, която светва.

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

Металният пръстен на всеки ротор има поне една вдлъбнатина. Ролята на тази вдлъбнатина е да контролира кога палецът може да превърти следващия по ред ротор. /Фиг. 9/ Когато най-десният ротор се превърти и вдлъбнатината му застане срещу палеца, палецът е свободен да се зацепи в зъбчатката на следващия ротор и да го избута една позиция напред. По този начин, когато палците се задвижат, най-десният ротор винаги се придвижва с една позиция, тъй като срещу неговия палец няма метален пръстен на по-десен от него ротор, който да предотвратява зацепването. Едва когато десният ротор се превърти и вдлъбнатината в неговия пръстен се изравни с зъба на палеца, следващият ротор се придвижва с една позиция напред. Превъртането на следващите ротори работи по аналогичен начин.

По-късните версии на Енигма машините, които са използвани най-масово във Втората световна война, имат ротори, които имат повече от една вдлъбнатина. По този начин роторите се движат по различен ред от "естествената" последователност /ААА, ААB, ААС ... AAZ, ABA, ABB .... ZZZ/.

Фиг. 9. Роторни колела на Енигма машина с отбелязани: 1 - зъбчатка; 2 - метален пръстен; 3 - вдлъбнатина в металния пръстен
Оригинално изображение: Matt Crypto

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

Приключваме тази част със снимки на съветската шифрираща машина M-125 (Фиалка), която е завършекът на еволюцията на тези машини. Първите /по-елементарни/ версии на машината са внедвени около 1956 година, докато последните версии датират от началото на 80-те години на миналия век. С изместването им от компютърната техника, те вече принадлежат на историята.

Фиг. 10. Съветска роторна шифрираща машина Фиалка (M-125) от времето на Студената война. Разсекретена около 2005.
Оригинално изображение: Glenn's Computer Museum