Operația XOR la nivel de bit

Dacă ai văzut lecția despre one-time-pad = cheia de unică folosință, știi că este cel mai bun cifru cu deplasare. Aceasta presupune aplicarea unei succesiuni aleatoare de deplasări egală cu lungimea mesajului. Este important să înțelegem exact cum și de ce cheia de unică folosință este imposibil de spart sau, cum se mai spune, perfect secretă.

Pentru a putea înțelege cele menționate mai sus, va trebui să introducem următorii termeni: AND, OR, XOR, adesea numiți operatori pe biți. "Pe biți" înseamnă pur și simplu că vom avea de-a face cu niște biți sau numere binare. În orice mecanism de criptare modern sau computerizat, simbolurile folosite la criptare vor fi reprezentate folosind cifre binare. Dacă ai uitat asta, poți să revezi secvența video despre Memoria calculatorului

Să începem cu un exemplu vizual prin criptarea culorii logo-ului Khan Academy care este reprezentat de o frunză verde.

Cum putem transforma o culoare într-un număr? Ei bine, în acest moment tu privești culori HTML care sunt definite folosind modelul de culoare RGB. Acesta este un model care se bazează pe mixarea unor cantități de lumină roșie, verde și albastră.

Putem defini cantitatea de ROȘU, VERDE și ALBASTRU folosind un număr între 0-255, Negru nu are nicio culoare și se reprezintă ca (0,0,0), în timp ce alb are cantitatea maximă din fiecare culoare, adică (255, 255, 255). Între cele două există 16 milioane de culori posibile (256 * 256 * 256). Acum, hai să găsim verdele din logo-ul Khan Academy într-un program de editare grafică:

Culorile pe care le conține sunt: ROȘU=156, VERDE=181, ALBASTRU=58.

Numerele de mai sus pot fi exprimate în binar astfel: ROȘU=10011100, VERDE=10110101, ALBASTRU=00111010.

ROȘU = 10011100, VERDE = 10110101, ALBASTRU = 00111010

Vrem să generăm o secvență de deplasare reprezentând în binar fețele dintr-o serie de aruncări a unei monede, astfel:

Cum putem să aplicăm această secvență de deplasare pe culoarea noastră pentru a o cripta folosind OTP (one-time pad = cheia de unică folosință)?

Pentru ca algoritmul de criptare cu OTP să funcționeze, vom alege operația corectă, astfel încât secvența rezultată să fie la fel de probabil egală cu orice culoare. Vom discuta despre 3 operații: AND, OR, XOR.

Operatorul AND (ȘI) numit conjuncție logică funcționează la fel ca înmulțirea. Acesta va genera 1 numai dacă toate intrările sunt 1, altfel rezultatul va fi 0. Mai jos avem tabelul de adevăr:

0 AND 0 = 0

0 AND 1 = 0

1 AND 0 = 0

1 AND 1 = 1

100111001011010100111010 AND 010110100001101111011000 = 000110000001000100011000

Exemplul de mai sus reprezintă un mov închis. Este important de observat faptul că atunci când aplicăm operația AND pe orice număr binar, secvența rezultată nu poate fi mai mare. În exemplul nostru de culoare, se elimină multe nuanțe posibile, deoarece împinge culoarea spre negru.

Operatorul OR, numit disjuncție logică, conduce la valoarea 1 oricând una sau mai multe intrări sunt 1. Tabelul de adevăr este următorul:

0 OR 0 = 0

0 OR 1 = 1

1 OR 0 = 1

1 OR 1 = 1

100111001011010100111010 OR 010110100001101111011000 = 110111101011111111111010

Rezultatul obținut este un mov deschis. Ține minte că atunci când realizăm o operație de tip OR, pe orice secvență binară, secvența rezultată nu poate fi mai mică. Astfel, gama de culori este împinsă spre nuanța de alb.

Operatorul XOR, numit SAU EXCLUSIV, va afișa 1 oricând intrările vor fi diferite între ele, altfel valoare obținută va fi 0. Acest rezultat este echivalent cu suma mod 2. Tabelul de adevăr este următorul:

0 XOR 0 = 0

0 XOR 1 = 1

1 XOR 0 = 1

1 XOR 1 = 0

100111001011010100111010 XOR 010110100001101111011000 = 110001101010111011100010

Rezultatul constă într-o nuanță mai închisă de mov decât nuanța de mov obținută cu ajutorul operației OR. Ține minte că atunci când realizăm o operație XOR pe o secvență binară, secvența rezultată poate fi orice secvență posibilă. Fiind dată o anumită culoare criptată, tot ce știm este că "nuanța originală poate fi orice culoare". De asemenea, este aproape imposibil să ghicim o nuanță, probabilitatea fiind 1/16 milioane.

Pentru a putea câștiga mai multe puncte de energie, vom face o reprezentare vizuală astfel încât să putem vedea criptarea cu ajutorul OTP în acțiune.