Xifratge de Hill

El xifratge de Hill va ser el primer sistema criptogràfic polialfabètic que servia per treballar amb més de tres símbols simultàniament. Aquest sistema és polialfabètic perquè pot passar que un mateix caràcter en un missatge a enviar es xifri en dos caràcters diferents en el missatge encriptat.

Màquina de xifratge de Hill. US patent 1,845,947.

Història

El xifratge de Hill va ser inventat l'any 1929 pel matemàtic i educador, interessat per les comunicacions Lester S. Hill. Aquest sistema està basat en l'àlgebra lineal i ha sigut important en la història de la criptografia.

Elaboració

Suposant que treballem amb un alfabet de 26 caràcters les lletres es numeren en ordre alfabètic de manera que A = 0, B = 1, ..., Z = 25.

Es tria un enter “d” que determina blocs de “d” elements que són tractats com un vector de “d” dimensions.

Es tria de forma aleatòria una matriu $\mathrm {M}$ de “d” × “d” elements els quals seran la clau a utilitzar. Els elements de $\mathrm {M}$ seran enters entre 0 i 25, a més $\mathrm {M}$ ha de ser invertible.

Per a l'encriptació, el text és dividit en blocs de “d” elements dels quals es multipliquen per $\mathrm {M}$.

Totes les operacions aritmètiques es realitzen en la forma mòdul 26, és a dir que: $26\equiv 0{\pmod {26}}$; $27\equiv 1{\pmod {26}}$; $28\equiv 2{\pmod {26}}$, etc.

Donat un missatge a xifrar hem de prendre blocs del missatge de "d" caràcters i aplicar: $matriu\cdot bloc$ $de$ $missatge=bloc$ $de$ $text$ $xifrat$.

Violació

El sistema de Hill planteja als criptoanalistes problemes molt més grans a què plantejava. Per començar l'espai de claus és molt més gran, en aquest cas és de 303 600, és a dir les permutacions de 4 elements presos d'entre 25 possibles. I utilitzant una matriu més gran la quantitat de possibles claus es pot fer tan gran com sigui necessari per fer que sigui impossible un atac per força bruta.

El millor que pot fer un criptoanalista és tractar d'aconseguir un codi per al qual es conegui una part del missatge, i veure si amb les dues dades és capaç de trobar com va ser la matriu utilitzada per xifrar el missatge. La matriu es trobaria utilitzant el mètode de reducció de Gauss.

Enllaços externs

• «Hill Cipher» (en anglès). [Consulta: 12 febrer 2013]. «Web que implementa un mètode en línia per xifrar i desxifrar missatges en aquest xifratge»
• http://massey.limfinity.com/207/hillcipher.pdf