Cifrado César
En criptografía, o cifrado César, tamén coñecido como cifrado por desprazamento, código de César ou desprazamento de César, é unha das técnicas de codificación máis simples e máis usadas. É un tipo de cifrado por substitución no que unha letra no texto orixinal é substituída por outra letra que se atopa un número fixo de posicións máis adiante no alfabeto. Por exemplo, cun desprazamento de 3, o A sería substituído polo D (situado 3 lugares á dereita do A), o B sería substituído polo E etc. Este método debe o seu nome a Xulio César, que o usaba para comunicarse cos seus xenerais.
O cifrado César moitas veces pode formar parte de sistemas máis complexos de codificación, como o cifrado Vigenère, e ata ten aplicación no sistema ROT13. Como todos os cifrados de substitución alfabética simple, o cifrado César se descifra con facilidade e na práctica non ofrece moita seguridade na comunicación.
Exemplo editar
A transformación pódese representar aliñando dous alfabetos; o alfabeto cifrado e un alfabeto normal que está desprazado un número determinado de posicións cara á esquerda ou á dereita. Por exemplo, aquí o cifrado César está usando un desprazamento de seis espazos cara á dereita:
Alfabeto orixinal: ABCDEFGHILMNÑOPQRSTUVXZ
Alfabeto codificado: GHILMNÑOPQRSTUVXZABCDEF
Para codificar unha mensaxe, simplemente débese buscar cada letra da liña do texto orixinal e escribir a letra correspondente na liña codificada. Para descodificalo deber facer o contrario.
Texto orixinal: HOXE NON CHOVEU NA NOSA CIDADE
Texto codificado: OUEM SUS IOUDMC SG SUAG IPLGLM
A codificación tamén se pode representar usando aritmética modular, transformando as letras en números, de acordo ao esquema A = 0, B = 1,..., Z = 22.[1] A codificación da letra x cun desprazamento n pode ser descrita matematicamente como:[2]
A descodificación faise de maneira similar:
A operación de substitución realízase cun mesmo valor de n fixado para toda a mensaxe, é dicir, emprégase un mesmo alfabeto codificado para toda a mensaxe. Por este motivo dise que o cifrado César é un cifrado de substitución monoalfabética, en oposición aos de substitución polialfabética, que non empregarían sempre a mesma codificación do alfabeto en distintas posicións da mensaxe.
Historia e uso editar
.JPG)
O cifrado César recibe o seu nome en honra a Xulio César, que, segundo Suetonio, o usou cun desprazamento de tres espazos para protexer as súas mensaxes importantes de contido militar:
Se tiña que dicir algo confidencial, escribíao usando o cifrado, isto é, cambiando a orde das letras do alfabeto, para que nin unha palabra puidese entenderse. Se alguén quere descodificalo, e entender o seu significado, debe substituír a cuarta letra do alfabeto, é dicir, o D polo A, e así cos demais.Suetonio, Vida dos Césares 56 [1].
Aínda que César é a primeira persoa da que se sabe que usase este sistema, anteriormente xa se utilizaron outros cifrados por substitución. O sobriño de Xulio César, Augusto, tamén empregou o cifrado pero cun desprazamento dunha soa posición:
Cando escribía un texto cifrado, substituía o B polo A, o C polo B e o resto das letras dese mesmo modo, usando AA para X.Suetonio, Vida de Augusto 88.
Hai indicios de que Xulio César usaba tamén sistemas máis complicados, e un escritor, Aulo Xelio, fai referencia a un tratado (agora perdido) sobre o cifrado:[3]
Hai incluso un tratado enxeñosamente escrito do gramático Probus referente ao significado secreto das letras na composición das epístolas do César.Aulo Xelio, 17.9.1–5.
Non se sabe como de efectivo resultaba realmente o cifrado César nesa época, pero debeu ser razoablemente seguro, xa que poucos inimigos de César saberían ler, e moito menos poderían levar a cabo a criptoanálise necesaria. Asumindo que o atacante puidese ler a mensaxe, non existen probas da existencia de técnicas para solucionar este tipo de codificación.[4]
No século XIX, a sección de avisos persoais dos xornais servía ás veces para intercambiar mensaxes codificadas usando técnicas de cifrado simples. David Kahn (1967) describe algúns exemplos de comunicación secreta entre amantes que utilizaban este cifrado no periódico The Times.[5] Mesmo en 1915, o cifrado César aínda era utilizado: a armada rusa empregábao substituíndo outros cifrados máis complicados que resultasen moi difíciles de utilizar polas súas tropas; os criptoanalistas alemáns e austríacos non tiveron moita dificultade para descodificar as mensaxes.[6]
O cifrado César pódese encontrar na actualidade nalgúns xoguetes modernos, coma os aneis descodificadores. No algoritmo ROT13 úsase o cifrado César cun desprazamento de 13, un método simple para ofuscar o texto que se usa nalgúns foros de Internet para ocultar texto (coma a liña final dun chiste, ou as partes da trama dunha película ou libro que non se queren revelar), pero non se usa como método serio de codificación.[7]
O cifrado Vigenère usa o cifrado César cun desprazamento diferente en cada posición do texto; o valor do desprazamento defínese usando unha palabra clave repetitiva. Se a palabra clave fose escollida ao chou e tan longa coma a mensaxe (para que non se repita), o sistema resultante sería, en teoría, indescifrábel. Para claves máis curtas que a mensaxe (é dicir, polo cifrado Vigenère), que é o que se usaba historicamente, aparece no texto un padrón cíclico que se pode detectar co método Kasiski, e saber a lonxitude da clave. Unha vez coñecida a lonxitude da clave, por exemplo k, entón o criptograma descomponse en k criptogramas de César que se poden descifrar cunha análise frecuencial.[8]
A modo anecdótico, cómpre sinalar tamén que o capo mafioso Bernardo Provenzano, detido en 2006, utilizaba para comunicarse, en pleno século XXI, notas escritas cunha máquina de escribir, codificadas mediante este rudimentario algoritmo, renegando de calquera tecnoloxía nova como o teléfono móbil ou a Internet. A pesar do rudimentario do sistema, conseguiu ter á policía despistada durante anos.[9]
Descifrado editar
| Desprazamento | Posible mensaxe orixinal |
|---|---|
| 0 | esezeuai |
| 1 | drdxdtzh |
| 2 | cqcvcsxg |
| 3 | bpbubrvf |
| 4 | aoataque |
| 5 | zñzszptd |
| 6 | xnxrxosc |
| ... | |
| 20 | hvhchzdn |
| 21 | gugbgxcm |
| 22 | ftfafvbl |
O descifrado do cifrado César pódese facer doadamente, mesmo se só se dispón dun texto cifrado curto. Pódense considerar dúas situacións:
- Un atacante coñece (ou adiviña) que se pode utilizar algunha forma simple de substitución de letras, pero non sabe que se usa o cifrado César.
- Un atacante sabe que se empregou o cifrado César, pero non coñece o valor do desprazamento.
Na primeira situación, poderíase romper o criptograma coas mesmas técnicas que se empregarían para un cifrado de substitución simple, como por exemplo cunha análise de frecuencias ou de patróns de palabras.[10] Deste xeito, un atacante decataríase de certa uniformidade na súa análise e deduciría que o algoritmo de cifrado empregado é o cifrado César.
Na segunda situación, o proceso de descifrado é directo. Como só hai un número limitado de posibles desprazamentos, pódense probar todos por orde, nun ataque por forza bruta.[11] Unha forma de facelo é escribir unha táboa na que se descifra un anaco do texto con todos os desprazamentos posibles[12] — esta técnica ás veces coñécese como «completando o compoñente claro».[13] No exemplo da táboa da dereita inténtase descodificar o texto cifrado «ESEZEUAI»; neste caso, o texto coherente recoñécese instantaneamente a primeira ollada, atopándose codificado por un desfasamento de catro letras cara á esquerda. Outra forma de obter a solución mediante este método é escribindo debaixo de cada letra o alfabeto en orde inversa e empezando por esa letra. Este proceso pódese acelerar usando cintas verticais co alfabeto escrito en orde inversa e aliñado, de modo que formen o texto cifrado nunha fila. Así, o texto coherente debe aparecer nalgunha das filas.
Outra técnica de forza bruta para romper o cifrado César consistiría en comparar os gráficos das distribucións de frecuencias das letras (análise de frecuencias). Representando as frecuencias das letras no texto cifrado e coñecendo a distribución de letras no idioma da mensaxe orixinal, unha persoa pode determinar facilmente o valor do desprazamento se é quen de identificar cantas unidades á dereita se trasladan as características dun gráfico no outro. Por exemplo, en español, as frecuencias das letras E e A (as máis frecuentes) e as da K e a W (as menos frecuentes) son particularmente distinguibles.[14] Os ordenadores tamén poden facelo a base de medicións, facendo que a distribución actual coincida coa distribución esperada (pódese utilizar por exemplo unha análise de distribución chi cadrado).[15]
A maioría das veces só se atopará unha mensaxe descifrada. Con todo, cando a mensaxe é moi curta poden aparecer varias palabras descifradas. Por exemplo, "ezaz" pode ser descifrado como "topo" ou "faba".
Repetir o proceso de cifrado varias veces non mellora a seguridade. Isto débese a que usar dous desprazamentos, por exemplo o desprazamento A e despois o desprazamento B, sería equivalente a usar un desprazamento A + B. En terminoloxía matemática, o cifrado repetido con diferentes claves forma un grupo.[16]
Notas editar
- ↑ Luciano, Dennis; Gordon Prichett (1987). "Cryptology: From Caesar Ciphers to Public-Key Cryptosystems". The College Mathematics Journal 18 (1): 3. doi:10.2307/2686311.
- ↑ Wobst, Reinhard (2001). Cryptology Unlocked. Wiley. p. 19. ISBN 978-0470060643.
- ↑ Reinke, Edgar C. (1992). "Classical Cryptography". The Classical Journal 58 (3): 114.
- ↑ Pieprzyk, Josef; Thomas Hardjono, Jennifer Seberry (2003). Springer, ed. Fundamentals of Computer Security. pp. 6. ISBN 3540431012.
- ↑ Kahn, David (1967). The Codebreakers. pp. 775–6. ISBN 978-0-684-83130-5.
- ↑ Kahn, David (1967). The Codebreakers. pp. 631–2. ISBN 978-0-684-83130-5.
- ↑ Wobst, Reinhard (2001). Wiley, ed. Cryptology Unlocked. p. 20. ISBN 978-0470060643.
- ↑ Kahn, David. The Codebreakers, 1967. ISBN 978-0-684-83130-5.
- ↑ Leyden, John (19 de abril de 2006). The Register, ed. "Mafia boss undone by clumsy crypto". Consultado o 13 de xuño de 2008.
- ↑ Beutelspacher, Albrecht (1994). Mathematical Association of America, ed. Cryptology. pp. 9–11. ISBN 0-88385-504-6.
- ↑ Beutelspacher, Albrecht. Cryptology. Mathematical Association of America, 1994, 8–9. ISBN 0-88385-504-6.
- ↑ Leighton, Albert C. «Secret Communication among the Greeks and Romans». Technology and Culture, vol. 10, 2, pàg. 153.
- ↑ Sinkov, Abraham; Paul L. Irwin. Elementary Cryptanalysis: A Mathematical Approach. Mathematical Association of America, 1966, 13–15. ISBN 0-88385-622-0.
- ↑ Singh, Simon. The Code Book. Anchor, 2000, 72?77. ISBN 0-385-49532-3.
- ↑ Savarese, Chris; Brian Hart. «The Caesar Ciphe r», 15-7-2002. Consultado o 16 de xullo de 2008.
- ↑ Wobst, Reinhard (2001). Cryptology Unlocked. Wiley. pp. 31. ISBN 978-0-470-06064-3.
Véxase tamén editar
Bibliografía editar
- Bauer, F. L. (2000). Decrypted Secrets: methods and maxims of cryptology (en inglés) (2ª ed.). Springer. ISBN 3-540-66871-3.
- Kahn, David (1996). Codebreakers — The Story of Secret Writing (en inglés) (2ª ed.). Scribner. ISBN 9780684831305.
- Savarese, Chris; Hart, Brian (2002). "The Caesar Cipher". Historical Cryptography Web Site (en inglés). Hartford, Connecticut: Trinity College Department of Computer Science. Arquivado dende o orixinal o 04 de xullo de 2008. Consultado o 31 de marzo de 2014.
- Singh, Simon (2000). The code book: the science of secrecy from ancient Egypt to quantum cryptography (en inglés). Anchor Books. ISBN 9780385495325.