Cifra Hill

În criptografia clasică, Cifrul Hill este un cifru de substituție polialfabetic bazat pe algebră liniară . Conceput de Lester S. Hill în 1929 , a fost primul cifru polialfabetic în care a fost posibil în practică (deși cu dificultate) să funcționeze cu mai mult de 3 simboluri la un moment dat. Următoarea discuție presupune o înțelegere de bază a teoriei matriciale .

Criptare

În criptare, fiecare literă este mai întâi codificată în număr. Schema cea mai frecvent utilizată este pur și simplu: A = 0, B = 1, ..., Z = 25, dar aceasta nu este o caracteristică esențială a cifrului. Un bloc de n litere este apoi considerată ca un spațiu vectorial de dimensiune n și înmulțit cu un n x n matrice , modulo 26 (dacă există un număr mai mare de 26 este utilizat în modulo de bază, apoi o schemă numerică diferită poate fi utilizată pentru codificați literele și puteți utiliza și spații și punctuație). Întreaga matrice este considerată cheia cifrului și trebuie să fie aleatorie, atâta timp cât este inversabilă $\mathbb {Z} _{26}^{n}$ ${\ displaystyle \ mathbb {Z} _ {26} ^ {n}}$ ${\ displaystyle \ mathbb {Z} _ {26} ^ {n}}$ (pentru a se asigura că este posibilă decriptarea). Luând în considerare mesajul „DUMNEAVOASTRĂ” și următoarea cheie (care în litere ar fi YYPRZWIZJ):

{\begin{pmatrix}24&24&15\\17&25&22\\08&25&09\end{pmatrix}}

{\ displaystyle {\ begin {pmatrix} 24 & 24 & 15 \\ 17 & 25 & 22 \\ 08 & 25 & 09 \ end {pmatrix}}}

{\ displaystyle {\ begin {pmatrix} 24 & 24 & 15 \\ 17 & 25 & 22 \\ 08 & 25 & 09 \ end {pmatrix}}}

Având în vedere că „T” este „19”, „U” este „20” și „O” este „14”, mesajul este vectorul:

{\begin{pmatrix}19\\20\\14\end{pmatrix}}

{\ displaystyle {\ begin {pmatrix} 19 \\ 20 \\ 14 \ end {pmatrix}}}

{\ displaystyle {\ begin {pmatrix} 19 \\ 20 \\ 14 \ end {pmatrix}}}

În consecință, vectorul criptat este dat de:

{\begin{pmatrix}24&24&15\\17&25&22\\08&25&09\end{pmatrix}}{\begin{pmatrix}19\\20\\14\end{pmatrix}}={\begin{pmatrix}1146\\1131\\778\end{pmatrix}}{\pmod {26}}\equiv {\begin{pmatrix}02\\13\\24\end{pmatrix}}

{\ displaystyle {\ begin {pmatrix} 24 & 24 & 15 \\ 17 & 25 & 22 \\ 08 & 25 & 09 \ end {pmatrix}} {\ begin {pmatrix} 19 \\ 20 \\ 14 \ end { pmatrix}} = {\ begin {pmatrix} 1146 \ \ 1131 \\ 778 \ end {pmatrix}} {\ pmod {26}} \ equiv {\ begin {pmatrix} 02 \\ 13 \\ 24 \ end {pmatrix} }}

{\ displaystyle {\ begin {pmatrix} 24 & 24 & 15 \\ 17 & 25 & 22 \\ 08 & 25 & 09 \ end {pmatrix}} {\ begin {pmatrix} 19 \\ 20 \\ 14 \ end { pmatrix}} = {\ begin {pmatrix} 1146 \ \ 1131 \\ 778 \ end {pmatrix}} {\ pmod {26}} \ equiv {\ begin {pmatrix} 02 \\ 13 \\ 24 \ end {pmatrix} }}

care se potrivește cu textul criptat „CNY”.

Calculul este dat de înmulțirea matricei × text simplu. După efectuarea acestui calcul, modulul (în acest caz 26) este eliminat din rezultat de câte ori este nevoie pentru a avea ca diferență un număr mai mic al modulului în sine și care, prin urmare, dă o literă bine definită ca rezultat.

C\leftarrow 02=24\cdot 19+24\cdot 20+15\cdot 14{\pmod {26}}

{\ displaystyle C \ leftarrow 02 = 24 \ cdot 19 + 24 \ cdot 20 + 15 \ cdot 14 {\ pmod {26}}}

{\ displaystyle C \ leftarrow 02 = 24 \ cdot 19 + 24 \ cdot 20 + 15 \ cdot 14 {\ pmod {26}}}

N\leftarrow 13=17\cdot 19+25\cdot 20+22\cdot 14{\pmod {26}}

{\ displaystyle N \ leftarrow 13 = 17 \ cdot 19 + 25 \ cdot 20 + 22 \ cdot 14 {\ pmod {26}}}

{\ displaystyle N \ leftarrow 13 = 17 \ cdot 19 + 25 \ cdot 20 + 22 \ cdot 14 {\ pmod {26}}}

Y\leftarrow 24=08\cdot 19+25\cdot 20+09\cdot 14{\pmod {26}}

{\ displaystyle Y \ leftarrow 24 = 08 \ cdot 19 + 25 \ cdot 20 + 09 \ cdot 14 {\ pmod {26}}}

{\ displaystyle Y \ leftarrow 24 = 08 \ cdot 19 + 25 \ cdot 20 + 09 \ cdot 14 {\ pmod {26}}}

Decriptare

Pentru a decripta, rescriem textul codificat ca vector, pe care îl vom înmulți pur și simplu cu matricea inversă a matricei cheie (IFKVIVVMI în litere). Există metode standard pentru calcularea matricei inverse; vezi matricea inversabilă pentru detalii. Vedem că matricea inversă din $\mathbb {Z} _{26}^{n}$ ${\ displaystyle \ mathbb {Z} _ {26} ^ {n}}$ ${\ displaystyle \ mathbb {Z} _ {26} ^ {n}}$ decât cel din exemplul anterior este:

{\begin{pmatrix}13&03&23\\23&18&13\\17&08&10\end{pmatrix}}

{\ displaystyle {\ begin {pmatrix} 13 & 03 & 23 \\ 23 & 18 & 13 \\ 17 & 08 & 10 \ end {pmatrix}}}

{\ displaystyle {\ begin {pmatrix} 13 & 03 & 23 \\ 23 & 18 & 13 \\ 17 & 08 & 10 \ end {pmatrix}}}

Prin urmare:

{\begin{pmatrix}13&03&23\\23&18&13\\17&08&10\end{pmatrix}}{\begin{pmatrix}02\\13\\24\end{pmatrix}}={\begin{pmatrix}617\\592\\378\end{pmatrix}}={\begin{pmatrix}19\\20\\14\end{pmatrix}}=

{\ displaystyle {\ begin {pmatrix} 13 & 03 & 23 \\ 23 & 18 & 13 \\ 17 & 08 & 10 \ end {pmatrix}} {\ begin {pmatrix} 02 \\ 13 \\ 24 \ end { pmatrix}} = {\ begin {pmatrix} 617 \ \ 592 \\ 378 \ end {pmatrix}} = {\ begin {pmatrix} 19 \\ 20 \\ 14 \ end {pmatrix}} =}

{\ displaystyle {\ begin {pmatrix} 13 & 03 & 23 \\ 23 & 18 & 13 \\ 17 & 08 & 10 \ end {pmatrix}} {\ begin {pmatrix} 02 \\ 13 \\ 24 \ end { pmatrix}} = {\ begin {pmatrix} 617 \ \ 592 \\ 378 \ end {pmatrix}} = {\ begin {pmatrix} 19 \\ 20 \\ 14 \ end {pmatrix}} =}

ceea ce ne face să ne întoarcem la „AL TĂU”, așa cum am vrut.

Există încă o complicație prezentă în alegerea matricei de codare de discutat: nu toate matricile sunt inversabile . O matrice are un invers dacă și numai dacă determinantul său nu este zero și nu are factori în comun cu modulul de bază. Prin urmare, dacă lucrăm modulul 26 ca mai sus, determinantul nu trebuie să fie zero și nu trebuie să fie divizibil cu 2 sau 13. Dacă determinantul este zero sau are factori în comun cu modulul de bază, atunci matricea nu poate fi utilizată în Cifrul Hill și o altă matrice trebuie alese (altfel nu ar fi posibilă decriptarea). Din fericire, matricile care îndeplinesc condițiile de utilizare în cifrul Hill sunt destul de frecvente.

Referindu-ne la exemplul dat, determinantul este:

{\begin{vmatrix}06&24&01\\13&16&10\\20&17&15\end{vmatrix}}\equiv 6(16\cdot 15-10\cdot 17)-24(13\cdot 15-10\cdot 20)+1(13\cdot 17-16\cdot 20)\equiv 441\equiv 25{\pmod {26}}

{\ displaystyle {\ begin {vmatrix} 06 & 24 & 01 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \ end {vmatrix}} \ equiv 6 (16 \ cdot 15-10 \ cdot 17) -24 (13 \ cdot 15-10 \ cdot 20) + 1 (13 \ cdot 17-16 \ cdot 20) \ equiv 441 \ equiv 25 {\ pmod {26}}}

{\ displaystyle {\ begin {vmatrix} 06 & 24 & 01 \\ 13 & 16 & 10 \\ 20 & 17 & 15 \ end {vmatrix}} \ equiv 6 (16 \ cdot 15-10 \ cdot 17) -24 (13 \ cdot 15-10 \ cdot 20) + 1 (13 \ cdot 17-16 \ cdot 20) \ equiv 441 \ equiv 25 {\ pmod {26}}}

Astfel, modulul 26, determinantul este 25. Deoarece acest lucru nu are factori comuni cu 26, matricea poate fi utilizată în cifrul Hill. Riscul determinant de a avea factori comuni cu modulele poate fi eliminat prin utilizarea unui număr prim ca modul. În consecință, o variantă utilă a cifrului adaugă trei simboluri suplimentare (de exemplu, spațiu, punct și semn de întrebare) pentru a aduce formularul la 29.

Siguranță

În ceea ce privește securitatea, din păcate, cifrul Hill, în versiunea sa de bază, este vulnerabil la un atac cunoscut în text clar (KPA), deoarece este complet liniar. Un adversar care interceptează n² perechi de caractere în clar și cifrate poate configura un sistem liniar care (de obicei) poate fi ușor rezolvat; se poate întâmpla ca sistemul să fie nedeterminat, dar în acest caz este suficient să adăugați alte perechi de caractere simple și criptate pentru a putea rezolva problema. Calculul soluției cu un algoritm standard de algebră liniară necesită puțin timp.

Deși simpla înmulțire cu o matrice nu este un cifru sigur, poate fi totuși un pas util atunci când este combinat cu alte operații neliniare, deoarece generează difuzie . De exemplu, o matrice aleasă corect poate provoca mici diferențe în vectorul inițial (text simplu) pentru a rezulta diferențe mult mai mari după multiplicare (text cifrat). Unele cifre moderne folosesc multiplicarea matricei intern în acest scop. Un exemplu este pasul AES MixColums. Funcția g în Twofish este, de asemenea, o combinație de cutii S neliniare și multiplicarea cu o matrice (MDS).

Lungimea cheii

Lungimea cheii este logaritmul binar al numărului de chei posibile. Sunt $26^{n^{2}}$ ${\ displaystyle 26 ^ {n ^ {2}}}$ ${\ displaystyle 26 ^ {n ^ {2}}}$ matrici de dimensiune n x n , deci $\log _{2}(26^{n^{2}})\approx 4,7n^{2}$ ${\ displaystyle \ log _ {2} (26 ^ {n ^ {2}}) \ aproximativ 4,7n ^ {2}}$ ${\ displaystyle \ log _ {2} (26 ^ {n ^ {2}}) \ aproximativ 4,7n ^ {2}}$ este o margine superioară pentru dimensiunea unei chei de cifrare Hill folosind n x n matrice. Aceasta este doar o limită superioară, deoarece nu toate matricile sunt inversabile și, prin urmare, nu toate pot fi folosite ca chei. Numărul de matrice inversabile poate fi calculat cu teorema restului chinezesc . Adică o matrice este modul inversabil 26 dacă și numai dacă este modul invers 2 și modul 13. Numărul de n x n matrice inversabile modul 2 este egal cu ordinea grupului liniar general GL (n, Z ₂ ), și anume:

2^{n^{2}}(1-1/2)(1-1/2^{2})\cdots (1-1/2^{n})

{\ displaystyle 2 ^ {n ^ {2}} (1-1 / 2) (1-1 / 2 ^ {2}) \ cdots (1-1 / 2 ^ {n})}

{\ displaystyle 2 ^ {n ^ {2}} (1-1 / 2) (1-1 / 2 ^ {2}) \ cdots (1-1 / 2 ^ {n})}

În mod similar, numărul matricilor inversabile modulul 13 (GL (n, Z ₁₃ )) este

13^{n^{2}}(1-1/13)(1-1/13^{2})\cdots (1-1/13^{n})

{\ displaystyle 13 ^ {n ^ {2}} (1-1 / 13) (1-1 / 13 ^ {2}) \ cdots (1-1 / 13 ^ {n})}

{\ displaystyle 13 ^ {n ^ {2}} (1-1 / 13) (1-1 / 13 ^ {2}) \ cdots (1-1 / 13 ^ {n})}

Prin urmare, numărul de matrici inversabile modulul 26 este produsul acestor două numere:

26^{n^{2}}(1-1/2)(1-1/2^{2})\cdots (1-1/2^{n})(1-1/13)(1-1/13^{2})\cdots (1-1/13^{n})

{\ displaystyle 26 ^ {n ^ {2}} (1-1 / 2) (1-1 / 2 ^ {2}) \ cdots (1-1 / 2 ^ {n}) (1-1 / 13) (1-1 / 13 ^ {2}) \ cdots (1-1 / 13 ^ {n})}

{\ displaystyle 26 ^ {n ^ {2}} (1-1 / 2) (1-1 / 2 ^ {2}) \ cdots (1-1 / 2 ^ {n}) (1-1 / 13) (1-1 / 13 ^ {2}) \ cdots (1-1 / 13 ^ {n})}

De asemenea, pare prudent să evitați să aveți prea multe zerouri în matricea cheie, deoarece acestea reduc spread-ul. Rezultatul este că numărul real de chei pentru cifrul Hill este de aproximativ 4,64 n ² - 1,7. Pentru un cifru 5 x 5, acesta este de aproximativ 114 biți. În mod clar, testarea sistematică a tuturor cheilor nu este cel mai eficient atac dintre cele cunoscute.

Implementare mecanică

Funcționând pe două simboluri, cifrul Hill nu oferă avantaje deosebite față de cifrul Playfair sau cifrul bifid și, de fapt, este mai slab decât ambele și puțin mai laborios de calculat cu pix și hârtie. Pe măsură ce dimensiunea crește, devine rapid imposibil să o calculați manual. Cu toate acestea, un cifru Hill de dimensiunea 6 a fost implementat mecanic de Hill, în colaborare cu o altă persoană, obținând brevetul ( ( EN ) US1,845,947 , Biroul de brevete și mărci al Statelor Unite, Statele Unite ale Americii. ). Această mașină a realizat un modul de multiplicare 26 pentru o matrice 6 × 6 folosind un sistem de roți și curele. Din păcate, sistemul de roți și, odată cu acesta, cheia, au fost remediate, așa că pentru siguranță s-a recomandat efectuarea unei criptări în trei pași: un prim pas neliniar (secret), criptarea cu mașina, care dă difuzie și, în final, o altă pas neliniar (secret). Această combinație de cifre a fost foarte puternică în 1929 și pare să arate că Hill a înțeles conceptele de atac întâlnire în mijloc și confuzie și difuzie .

Bibliografie

Lester S. Hill, Criptografie într-un alfabet algebric, The American Mathematical Monthly 36, iunie-iulie 1929, pp 306-312.
Lester S. Hill, În ceea ce privește anumite aparate de criptografie liniară, The American Mathematical Monthly 38, 1931, pp. 135–154.
Jeffrey Overbey, William Traves și Jerzy Wojdylo, On the Keyspace of the Hill Cipher, Cryptologia , 29 (1), ianuarie 2005, pp 59-72. ( PDF )
Shahrokh Saeednia, How to Make the Hill Cipher Secure, Cryptologia , 24 (4), octombrie 2000, pp353-360.

Elemente conexe

Portal de criptografie : Accesați intrările Wikipedia care se ocupă de criptografie