Cifrul Hill
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9a/Hill%27s_message_protector.png/220px-Hill%27s_message_protector.png)
În criptografia clasică, cifrul Hill este un cifru al substituției poligrafic bazat pe algebră lineară. Inventat de către Lester S. Hill în 1929, a fost primul cifru poligrafic în care era practic posibil să se opereze cu mai mult de trei simboluri deodată. Pentru a înțelege discuția următoare sunt necesare cunoștințe de teoria matricelor.
Operare
Fiecare literă este tratată ca o cifră din baza 26: A = 0, B =1 ș.a.m.d. Un bloc de n litere este considerat ca un vector cu n dimensiuni, și multiplicat cu o matrice n × n, modulo 26. Componentele matricei reprezintă cheia, care trebuie alese aleatoriu astfel încât matricea să fie inversabilă în (pentru a asigura posibilitatea decriptării). Considerăm mesajul 'ACT', și cheia de mai jos (sau GYBNQKURP în litere):
Deoarece 'A' este 0, 'C' este 2 și 'T' este 19, mesajul este vectorul:
Deci vectorul criptat este dat de:
care corespunde criptotextului 'POH'. Acum, presupunem că mesajul nostru este 'CAT', sau:
De această dată, vectorul criptat este dat de:
care corespunde criptotextului 'FIN'. Fiecare literă s-a schimbat. Cifrul Hill are proprietatea de difuzie a lui Shannon, iar un cifru Hill n-dimensional are proprietatea de difuzie peste n simboluri deodată.
Decriptare
Pentru a putea decripta, transformăm criptotextul în vector și apoi îl înmulțim cu inversa matricei cheie (IFKVIVVMI în litere). (Există metode standard de calculare a inversei unei matrici; vezi inversarea matricilor pentru detalii.) Găsim că, în , inversa matricei din exemplul de mai sus este:
Luând criptotextul de mai sus, 'POH', obținem:
care reprezintă 'ACT'.
Complicația care poate apărea este faptul că nu toate matricele au inverse (vezi matrice inversabilă). Există o metodă directă de determinare a acestei proprietăți. Dacă determinantul unei matrice este 0, sau are factori comuni cu modulul (adică factori ca 2 sau 13, în cazul modulului 26), atunci matricea nu poate fi olosită în cifrul Hill. Din fericire, dacă baza nu are factori mici, cele mai multe matrice au inverse. De exemplu, matricea cheie:
25 este coprim cu 26, deci nu este nici o problemă. Riscul ca determinantul să aibă factori comuni cu modulul poate fi eliminat prin alegerea unui modul prim. În consecință, o variantă utilă de cifru Hill adaugă încă 3 simboluri pentru a crește modulul la 29.
Criptografie clasică v • d • m |
---|
Cifruri: ADFGVX | Afin | Alberti | Atbash | Autocheie | Bifid | Carte | Cezar | Cod Smithy | Codul bătăilor | Cuvânt cheie | Două pătrate | Francmasonic | Hill | Nihilist | Patru pătrate | Permutare | Playfair | Polialfabetic | Polybius | Rail Fence | Reihenschieber | Reservehandverfahren | ROT13 | Running key | Schitală | Solitaire | Straddling checkerboard | Substituție | Transpoziție | Trifid | VIC | Vigenère |
Criptanaliză: Analiza frecvenței | Index de coincidență |
Diverse: Criptogramă | Bacon | Pătratul lui Polybius | Schitală | Straddling checkerboard | Tabula recta |
Criptografie v • d • m |
Istoria criptologiei | Criptanaliză | Portalul criptografiei | Subiecte în criptografie |
Algoritm cu chei simetrice | Cifru bloc | Cifru stream | Criptografie cu chei publice | Funcție hash criptografică | Cod de autentificare a mesajelor | Număr aleatoriu |