Xifratge afí

El xifratge afí és un tipus de xifratge de substitució mono-alfabètic, en el qual cada lletra d'un alfabet s'assigna al seu equivalent numèric, es xifra usant una funció matemàtica simple, i converteix de nou en una lletra. La fórmula utilitzada implica que cada lletra es xifra en una altra lletra. El procés de desxifrat és anàleg. És a dir, el sistema de xifratge és essencialment un xifratge de substitució estàndard amb una regla que governa quina lletra es converteix en quina. Per tant, té totes les debilitats dels xifratges de substitució. Cada lletra es xifra amb la funció $(ax+b)\mod (26)$ , on $b$ és la magnitud del desplaçament.

Descripció

En el sistema de xifratge afí les lletres d'un alfabet de mida $m$ s'assignen primer als nombres enters entre $0..m-1$ . A continuació, s'utilitza aritmètica modular per transformar l'enter corresponent a cada lletra del text pla en un altre nombre enter que correspondrà amb una lletra del text xifrat. La funció de xifrat per a una sola lletra és

{\mbox{E}}(x)=(ax+b)\mod {m},

on el mòdul $m$ és la mida de l'alfabet i $a$ i $b$ són la clau del xifratge. El valor d' $a$ s'ha d'escollir de manera que $a$ i $m$ siguin coprimers. La funció de desxifrat és

{\mbox{D}}(x)=a^{-1}(x-b)\mod {m},

on $a^{-1}$ és l'invers multiplicatiu modular de $a\mod {m}$ . És a dir, satisfà l'equació

1=aa^{-1}\mod {m}.

L'invers multiplicatiu d' $a$ només existeix si $a$ i $m$ són coprimers. Per tant, sense aquesta condició el desxifrat podria no ser possible. Es pot mostrar de la següent manera que la funció de desxifrat és la inversa de la funció de xifrat,

{\begin{aligned}{\mbox{D}}({\mbox{E}}(x))&=a^{-1}({\mbox{E}}(x)-b)\mod {m}\\&=a^{-1}(((ax+b)\mod {m})-b)\mod {m}\\&=a^{-1}(ax+b-b)\mod {m}\\&=a^{-1}ax\mod {m}\\&=x\mod {m}.\end{aligned}}

Debilitats

Atès que el xifratge afí és encara un xifratge de substitució mono-alfabètica, hereta les debilitats d'aquesta classe de sistemes de xifratge. El xifratge afí és un xifratge de Cèsar quan $a=1$ , ja que la funció d'encriptació es redueix simplement a un canvi lineal: en el xifratge de Cèsar tradicional, $b=3$ ; i en el ROT13, $b=13$ .

Si considerem el cas específic de l'encriptació de missatges en anglès (és a dir, $m=26$ ), hi ha un total de 286 sistemes de xifratge afí no trivials, sense comptar els 26 sistemes de xifratge de Cèsar trivials. Aquest nombre ve del fet que hi ha 12 nombres que són coprimers amb 26 i que a la vegada són menors que 26 (aquests són els valors possibles de $a$ ). Cada valor d' $a$ pot tenir 26 desplaçaments diferents (el valor $b$ ). Per tant, hi ha 12 * 26 = 312 claus possibles. Aquesta manca de varietat fa que el sistema sigui altament insegur quan es té en compte el principi de Kerckhoffs.

La debilitat principal del sistema de xifratge ve del fet que si el criptoanalista pot descobrir (per mitjà d'anàlisi de freqüència, força bruta, endevinant o de qualsevol altra manera) el text pla de dos caràcters de text xifrat, aleshores pot obtenir la clau solucionant un sistema d'equacions. Ja que a més se sap que $a$ i $m$ són coprimers, es pot utilitzar aquesta informació per descartar ràpidament moltes claus "falses" en un sistema automatitzat.

El mateix tipus de transformació usat en sistemes de xifrat afins s'utilitza en generadors de congruència lineal, un tipus de generador de nombres pseudoaleatoris. Aquest generador no és un generador de nombres pseudoaleatoris criptogràficament segur per la mateixa raó que el xifrat afí no és segur.

Vegeu també