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
Резултат
0
0
0
1
0
1
0
1
1
1
1
0

Ако си представим за момент, че 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
Резултат
0
0
0
1
0
1
0
1
1
1
1
0

Когато двата входа са еднакви, е очевидно че местата им могат да се сменят произволно. Остава да разгледаме случая вярно ли е, че $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 b
b XOR c
(a XOR b) XOR c
a 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) означава, че числото е записано в двоична бройна система.