Xifratge de C??sar

De Viquip??dia

Detall
Xifratge de Cesar
La acci?? del xifrat de C??sar ??s substituir cada lletra del text clar per un altre que estigui un nombre fix de llocs m??s endavant a l'alfabet. Aquest exemple ??s amb un despla??ament de tres, per tant una `B` en el text clar esdev?? `E` en el text xifrat.
Estructura	xifratge per substituci??
Millor cripoan??lisi p??blic
Atac per la for??a bruta i an??lisi freq??encial.

En criptografia, un xifrat de C??sar, conegut tamb?? com a codificaci?? de C??sar, xifratge per decalatge, codi de C??sar or decalatge de C??sar, ??s una de les t??cniques de xifratge m??s senzilles i m??s abastament conegudes. ??s un tipus de xifratge per substituci?? en el qual cada lletra del text clar es substitueix per un altre lletra que estigui un determinat nombre fix de posicions despla??ada a l'alfabet. Per exemple, amb un decalatge de 3, la A es substituiria per la D, la B esdevindria E, i aix??. El m??tode deu el seu nom a en Juli C??sar, qui el feia servir per a comunicar-se amb els seus generals.

El pas de xifratge que fa l'algorisme de C??sar sovint forma part d'esquemes de codificaci?? m??s complexos, com ara el xifratge de Vigen??re, i encara avui t?? aplicaci?? en el sistema ROT13. Com tots els sistemes de xifratge per substituci?? amb clau no aleat??ria m??s curta que el text, el xifratge de C??sar es pot trencar f??cilment i en la pr??ctica no ofereix cap mena de seguretat essencial en les comunicacions.

[edita] Exemple

La transformaci?? es pot representar a base d'alinear dos alfabets; l'alfabet xifrat ??s l'alfabet clar despr??s d'aplicar-li una rotaci?? cap a l'esquerra o cap a la dreta un determinat nombre de posicions. Per exemple, vet aqu?? un xifratge de C??sar fent servir una rotaci?? cap a l'esquerra de quatre llocs (el par??metre de decalatge, en aquest cas 4, es fa servir com al clau):

Text clar:     ABC??DEFGHIJKLMNOPQRSTUVWXYZ
Text xifrat:   DEFGHIJKLMNOPQRSTUVWXYZABC??

Per a xifrar un missatge, nom??s cal buscar cada lletra a la l??nia de "text clar" i escriure la lletra que li correspon a la l??nia de "text xifrat". Per a desxifrar-lo, es fa al reves.

Text clar:   SETZE JUTGES MENJEN FETGE
Text xifrat: WIX??I NYXKIW QIRNIR JIXKI

Aquest sistema tamb?? es pot expressar fent servir aritm??tica modular a base de transformar primer les lletres en nombres, d'acord amb la correspond??ncia, A = 0, B = 1,..., Z = 27. El xifratge d'una lletra $x$ amb un decalatge de n es pot descriure matem??ticament com,

$X_n(x) = (x + n) \mod {27}.$

EL desxifratge es fa de forma similar,

$D_n(x) = (x - n) \mod {27}.$

La operaci?? de substituci?? es conserva la mateixa al llarg de tot el missatge, per tant el xifratge es classifica com un xifratge de tipus substituci?? monoalfab??tica, en oposici?? a la substituci?? polialfab??tica.

[edita] Hist??ria i ??s

El xifratge de C??sar rep el seu nom degut a que en Juli C??sar, el feia servir amb un decalatge de tres.

El xifratge de C??sar rep el seu nom degut a Juli C??sar, qui, segons Suetonius, el feia servir amb un decalatge de tres per a protegir missatges amb inter??s militar:

??	si tenia quelcom confidencial a dir, ho escrivia xifrat, ??s a dir, a base de canviar l'ordre de les lletres de l'alfabet, de forma que no hi apareixia ni un paraula. Si alg?? vol desxifrar-ho, i obtenir el seu significat, ha de substituir la quarta lletra de l'alfabet, la D, per la A, i aix?? amb les altres.	??

??? Suetonius, vida de Juli C??sar 56 [1].

Tot i que el de C??sar ??s el primer cas enregistrat d'??s d'aquest sistema, se sap que abans ja s'havien fet servir altres xifratges per substituci??. El seu nebot, August, tamb?? feia servir aquest xifratge, per?? amb un decalatge de 1, i no tornava a comen??ar pel comen??ament de l'alfabet:

??	Sempre que escrivia xifrat, escrivia B en comptes de A, C en coptes de B, i les altres lletres de la mateixa manera, fent servir AA en comptes de X.	??

??? Suetonius, Vida d'August 88.

Hi ha evid??ncia de que Juli C??sar tamb?? feia servir sistemes m??s complicats, i un escriptor, Aulus Gellius, refereix un tractat (avui perdut) dels seus xifratges:

??	Hi ha fins i tot un tractat bastant ingeniosament escrit pel gram??tic Probus pel que fa al significat secret de les lletres en la redacci?? de les ep??stoles de Caesar.	??

??? Aulus Gellius, 17.9.1???5.

No es coneix l'efectivitat del xifratge de C??sar en el seu temps, per?? ??s probable que fos raonablement segur, perqu?? segurament pocs enemics sabrien llegir en llat?? ni tan sols estarien familiaritzats amb el llenguatge escrit, i encara menys serien capa??os de plantejar cap mena de criptoan??lisi. Suposant que poguessin llegir el missatge, no hi ha const??ncia en aquella ??poca de cap t??cnica per a solucionar els xifratges per substituci?? simple. Els registres m??s antics que es conserven daten del segle 9 al m??n ??rab amb el descobriment de l'an??lisi freq??encial.

Al darrere de la Mezuz?? hi ha un xifratge de C??sar amb decalatge de 1: ???KUZU BMUKSZ KUZU??? que decodificat (en l'alfabet hebreu) diu: ???YHVH ELHYNU YHVH??? (Senyor D??u Senyor).^[1]

En el segle 19, a la secci?? d'anuncis personals dels diaris de vegades es feien servir sistemes simples de xifratge per intercanviar missatges xifrats. En David Kahn (1967) descriu exemples d'amants intercanviant en secret comunicacions xifrades fent servir el xifratge de C??sar al The Times. Fins i tot al 1915, el xifratge de C??sar encara es feia servir: L'ex??rcit rus el feia servir en substituci?? de xifratges m??s complicats que s'havia comprovat que eren massa dif??cils de manegar per les seves tropes; Els criptoanalistes alemanys i austr??acs no tenien gaires dificultats en desxifrar els seus missatges.

El xifratge de Vigen??re fa servir el xifratge de C??sar amb un decalatge diferent per a cada posici?? del text; el valor del decalatge es defineix fent servir una paraula clau que es repeteix. Si la paraula clau es fa servir un sol cop, ??s tan llarga com el missatge, i es tria de forma aleat??ria, llavors ??s un xifrate de Vernam, impossible de desxifrar si els usuaris mantenen la clau en secret (de fet ??s l'??nic xifratge que s'ha pogut demostrar matem??ticament que ??s indesxifrable). Per a claus m??s curtes que el missatge (es a dir pel xifratge de Vigen??re), que ??s el que es feia servir hist??ricament, apareix al text un patr?? c??clic que es pot detectar amb el m??tode de Kasiski i saber la longitud de la clau, un cop coneguda la longitud de la clau per exemple k, llavors el criptograma es descompon en k criptogrames de C??sar que es poden desxifrar amb l'an??lisi freq??encial.

A l'abril del 2006, el cap mafi??s Bernardo Provenzano va ser capturat a Sic??lia en part degut al desxifratge dels seus missatges escrits en una variaci?? del xifratge de C??sar. El xifratge den Provenzano feia servir nombres, aix?? la "A" es podia escriure com a "4", la "B" com a "5", i aix??.^[2]

[edita] Desxifratge

Decalatge de desxifratge	Candidat a text clar
0	`ijxujwyekjwwt`
1	`hiwtivxdjivvs`
2	`ghvshuw??ihuur`
3	`fgurgtvchgttq`
4	`eftqfsubgfssp`
5	`despertaferro`
6	`??drodqszedqqn`
...
24	`lmaxmzbinmzzw`
25	`klzwlyahmlyyv`
26	`jkyvkxzglkxxu`

El xifratge de C??sar es pot desxifrar f??cilment fins i tot si nom??s es disposa d'un text xifrat curt. Es poden considerar dues situacions:
1) L'atacant sap (o suposa) que s'ha fet servir alguna mena de xifratge per substituci??, per?? no sap que s'ha fet servir espec??ficament el xifratge de C??sar;
2) L'atacant sap que s'ha fet servir el xifratge de C??sar per?? no sap el valor del decalatge.

En el primer cas, el xifratge es pot trencar fent servir les mateixes t??cniques que per qualsevol xifratge general per substituci??, com ara l'an??lisi freq??encial o les paraules patr??. En resoldre-ho, ??s probable que l'atacant s'adoni r??pidament de la regularitat de la soluci?? i dedueixi que s'ha fet servir l'algorisme espec??fic del xifratge de C??sar.

La freq????ncia de la distribuci?? de les lletres en una mostra t??pica en catal??, angl??s i franc??s, t?? una forma distingible i predictible. Un xifratge de C??sar "despla??a" aquesta distribuci??, i ??s possible determinar l'idioma del text i el despla??ament examinant la gr??fica de freq????ncies que en resulta.

En el segon exemple, trencar el xifratge ??s encara m??s directe. Com que nom??s hi ha un nombre limitat de possibles decalatges (27 en catal??), es poden provar tots per ordre en un atac per la for??a bruta. Una forma de fer-ho ??s escriure una taula en que es desxifra un boc?? del text amb tots els decalatges possibles ??? aquesta t??cnica de vegades es coneix com "completant el component clar". L'exemple de la taula de la dreta ??s pel text xifrat " IJXUJWYEKJWWT "; el text clar es reconeix instant??niament a cop d'ull per a un decalatge de cinc. Un altre forma de veure aquest m??tode ??s que davall de cada lletra s'escriu l'alfabet en ordre invers i comen??ant per aquella lletra. Aquest proc??s es pot accelerar fent servir cintes verticals amb l'alfabet escrit en ordre invers i alinear-les de forma que formin el text xifrat en una fila, el text clar ha d'apar??ixer en un altre de les files.

Un altre enfocament ??s encaixar la distribuci?? de freq????ncies de les lletres. A base de fer una gr??fica de la freq????ncia de les lletres en el text xifrat, sabent la distribuci?? esperada d'aquestes lletres en el llenguatge clar, una persona pot descobrir f??cilment el valor del decalatge mirant el despla??ament de determinades caracter??stiques de la gr??fica. Aquesta t??cnica es coneix com an??lisi freq??encial. Per exemple en catal?? les freq????ncies de les lletres the letters E, A, (normalment les m??s freq??ents), i K, W, W (t??picament les menys freq??ents) es distingeixen de seguida. Els ordinadors tamb?? ho poden fer a base de mesurar lo b?? que la distribuci?? actual encaixa amb la distribuci?? esperada; per exemple es pot fer servir l'estad??stica xi quadrat.

Per a textos clars escrits en llenguatge natural, hi haur??, amb tota probabilitat, un ??nic desxifratge plausible, tot i que per a textos clars extremament curts, ??s possible que hi hagi m??ltiples candidats. Per exemple, el text xifrat ??P?? es podria, desxifrar, plausiblement en "nan" o "ama" o "ses" (suposant que el text clar sigui en catal??).

Repetint molts cops el xifratge de C??sar no dona cap seguretat afegida. Aix?? ??s degut a que dos xifratges, per exemple primer amb un decalatge de 3 i despr??s amb un decalatge de 5, ??s equivalent a un ??nic xifratge de decalatge 3+5=8. En terminologia matem??tica, el xifratge repetit amb diferents claus forma un grup.

[edita] Refer??ncies

Amparo Fuster Sabater et al, T??cnicas criptogr??ficas de protecci??n de datos???, 2000. ISBN 84-7897-421-0 (castell??)
David Kahn, The Codebreakers ??? The Story of Secret Writing, 1967. ISBN 0-684-83130-9. (angl??s)
F.L. Bauer, Decrypted Secrets, 2nd edition, 2000, Springer. ISBN 3-540-66871-3. (angl??s)
Chris Savarese and Brian Hart, The Caesar Cipher, 1999 (angl??s)