Xifratge de Cèsar
| Xifratge de Cèsar | |
|---|---|
 L'acció del xifrat de Cèsar és substituir cada lletra del text clar per una altra 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. | |
| General | |
| Data primera publicació | segle i aC |
| Detall | |
| Estructura | Xifratge per substitució |
| Millor criptoanàlisi pública | |
En criptografia, el xifratge de Cèsar, conegut també com a codificació de Cèsar, xifratge per decalatge, codi de Cèsar o decalatge de Cèsar, és una de les tècniques de xifratge clàssic més senzilles i més a bastament conegudes. És un tipus de xifratge per substitució en el qual cada lletra del text clar se substitueix per una altra lletra que estigui un determinat nombre fix de posicions desplaçades a l'alfabet. Per exemple, amb un decalatge de 3, la A se 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 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.
Descripció del funcionament
[modifica]La transformació es pot representar per mitjà 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 a clau):
Text clar: ABCÇDEFGHIJKLMNOPQRSTUVWXYZ Text xifrat: DEFGHIJKLMNOPQRSTUVWXYZABCÇ
Per 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 desxifrar-lo, es fa a l'inrevés.
Text clar: SETZE JUTGES MENGEN FETGE Text xifrat: WIXÇI NYXKIW QIRKIR JIXKI
Aquest sistema també es pot expressar fent servir aritmètica modular com un cas particular del xifratge afí, a base de transformar primer les lletres en nombres, d'acord amb la correspondència, A = 0, B = 1,..., Z = 27.[1] El xifratge d'una lletra amb un decalatge de n es pot descriure matemàticament com,[2]
El desxifratge es fa de forma similar,
L'operació de substitució es conserva 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.
Història i ús
[modifica].JPG)
El xifratge de Cèsar deu el seu nom a Juli Cèsar, qui, segons Suetoni, el feia servir amb un decalatge de tres per 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. | » |
| — Suetoni, vida de Juli Cèsar 56[3] | ||
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 d'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 comptes de B, i les altres lletres de la mateixa manera, fent servir AA en comptes de X. | » |
| — Suetoni, Vida d'August 88. | ||
Hi ha proves que Juli Cèsar també feia servir sistemes més complicats,[4] i un escriptor, Aule Gel·li, es refereix a un tractat (avui perdut) dels seus xifratges:
| « | Hi ha fins i tot un tractat bastant enginyosament escrit pel gramàtic Probus pel que fa al significat secret de les lletres en la redacció de les epístoles de Caesar. | » |
| — Aule Gel·li, 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.[5] Suposant que poguessin llegir el missatge, no hi ha constància en aquella època de cap tècnica per solucionar els xifratges per substitució simple. Els registres més antics que es conserven daten del segle ix al món àrab amb el descobriment de l'anàlisi freqüencial.[6]
Al darrere de la Mezuzà hi ha un xifratge de Cèsar amb decalatge d'1: "KUZU BMUKSZ KUZU" que decodificat (en l'alfabet hebreu) diu: "YHVH ELHYNU YHVH" (Senyor Déu Senyor).[7]
Al segle xix, a la secció d'anuncis personals dels diaris de vegades es feien servir sistemes simples de xifratge per intercanviar missatges xifrats. L'any 1967, al The Times, David Kahn descriu exemples d'amants intercanviant en secret comunicacions xifrades fent servir el xifratge de Cèsar.[8] Fins i tot el 1915, el xifratge de Cèsar encara es feia servir; l'exèrcit rus en feia ús en substitució de xifratges més complicats que s'havia comprovat que eren massa difícils de manejar per les seves tropes; els criptoanalistes alemanys i austríacs no tenien gaire dificultats en desxifrar els seus missatges.[9]
Un xifratge de Cèsar amb decalatge de 13 es fa servir en l'algorisme ROT13. És un mètode simple per enfosquir text que es troba a bastament al sistema UNIX, però no es fa servir com un mètode de xifratge.[10]
El xifratge de Vigenère fa servir el xifratge de Cèsar amb un decalatge diferent per 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 xifratge 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 claus més curtes que el missatge (és 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.[11]
A l'abril del 2006, el cap mafiós Bernardo Provenzano va ser capturat a Sicília en part a causa del desxifratge dels seus missatges escrits en una variació del xifratge de Cèsar. El xifratge d'en Provenzano feia servir nombres; així, la "A" es podia escriure com a "4", la "B" com a "5", i així successivament[12]
Desxifratge
[modifica]| 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 interpretar fàcilment fins i tot si només es disposa d'un text xifrat curt. Es poden considerar dues situacions:
- 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;
- 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ó.[13] 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.
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.[14] Una forma de fer-ho és escriure una taula en què es desxifra un bocí del text amb tots els decalatges possibles[15] — aquesta tècnica de vegades es coneix com "completant el component clar".[16] 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 un decalatge de cinc. Una altra 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 una altra de les files.
Un altre enfocament és encaixar la distribució de freqüències de les lletres. Per mitjà 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 a anàlisi freqüencial. Per exemple en català les freqüències de les lletres E, A, (normalment les més freqüents), i K, W, W (típicament les menys freqüents) es distingeixen de seguida.[17] Els ordinadors també ho poden fer per mitjà de mesurar com de bé la distribució actual encaixa amb la distribució esperada; per exemple, es pot fer servir l'estadística xi quadrat.[18]
Per textos clars escrits en llenguatge natural, hi haurà, amb tota probabilitat, un únic desxifratge plausible, tot i que per 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 al fet 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.[19]
Referències
[modifica]- ↑ Luciano, Dennis; Gordon Prichett «Cryptology: From Caesar Ciphers to Public-Key Cryptosystems». The College Mathematics Journal, 18, 1, gener 1987, pàg. 3. DOI: 10.2307/2686311.
- ↑ Wobst, Reinhard. Cryptology Unlocked. Wiley, 2001, p. 19. ISBN 978-0470060643.
- ↑ Suetoni, Vida de Juli Cèsar [1] Arxivat 2011-02-01 a Wayback Machine.
- ↑ Reinke, Edgar C. «Classical Cryptography». The Classical Journal, 58, 3, desembre 1992, pàg. 114.
- ↑ Pieprzyk, Josef; Thomas Hardjono, Jennifer Seberry. Fundamentals of Computer Security. Springer, 2003, p. 6. ISBN 3540431012.
- ↑ Singh, Simon. The Code Book. Anchor, 2000, p. 14–20. ISBN 0385495323.
- ↑ Alexander Poltorak The Mysterious Name
- ↑ Kahn, David. The Codebreakers, 1967, p. 775–6. ISBN 978-0-684-83130-5).
- ↑ Kahn, David. The Codebreakers, 1967, p. 631–2. ISBN 978-0-684-83130-5).
- ↑ Wobst, Reinhard. Cryptology Unlocked. Wiley, 2001, p. 20. ISBN 978-0470060643.
- ↑ Kahn, David. The Codebreakers, 1967. ISBN 978-0-684-83130-5).
- ↑ "Mafia boss undone by clumsy crypto" The Register
- ↑ Beutelspacher, Albrecht. Cryptology. Mathematical Association of America, 1994, p. 9–11. ISBN 0-88385-504-6.
- ↑ Beutelspacher, Albrecht. Cryptology. Mathematical Association of America, 1994, p. 8–9. ISBN 0-88385-504-6.
- ↑ Leighton, Albert C. «Secret Communication among the Greeks and Romans». Technology and Culture, 10, 2, abril 1969, pàg. 153. DOI: 10.2307/3101474.
- ↑ Sinkov, Abraham; Paul L. Irwin. Elementary Cryptanalysis: A Mathematical Approach. Mathematical Association of America, 1966, p. 13–15. ISBN 0883856220.
- ↑ Singh, Simon. The Code Book. Anchor, 2000, p. 72–77. ISBN 0385495323.
- ↑ Savarese, Chris; Brian Hart. «The Caesar Cipher», 15-07-2002. [Consulta: 16 juliol 2008].
- ↑ Wobst, Reinhard. Cryptology Unlocked. Wiley, 2001, p. 31. ISBN 978-0470060643.
Bibliografia
[modifica]- 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, 2a edició, 2000, Springer. ISBN 3-540-66871-3. (anglès)
- Chris Savarese and Brian Hart. The Caesar Cipher, 1999 (anglès)
Vegeu també
[modifica]Enllaços externs
[modifica]- Un programa en Windows per xifrar text Arxivat 2007-12-22 a Wayback Machine. caracteritzant un atac "intel·ligent" basat en el diccionari per desxifrar automàticament text xifrat.
- Un descodificador del xifratge de Cèsar en format Excel que permet veure les 25 possibilitats (en anglès 25 lletres) simultàniament Arxivat 2007-10-10 a Wayback Machine.