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)