Криптоанализът на Енигма (Част 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. Авторът си позволи да "открадне" тази ярка илюстрация от Брус Шнайер, който получава безспорния кредит за формулирането и.