Vés al contingut

Xifratge clàssic

De la Viquipèdia, l'enciclopèdia lliure

Un xifratge és una manera d'ocultar un missatge mitjançant la reordenació de les seves lletres segons un patró, o mitjançant la substitució de les seves lletres per altres lletres o números seguint un algorisme establert.

Aquestes maneres de reordenar (transposicions) o de substituir (substitucions) són conegudes tant per l'emissor com pel receptor, de tal manera que el receptor pot realitzar el procediment invers al xifratge que s'hagi aplicat si vol recuperar el missatge original.

En criptografia, anomenem xifratge clàssic a totes aquelles maneres de xifrar que s'han fet servir històricament per ocultar informació, però que actualment ja no s'utilitzen. En general, es tracta d'algorismes aplicats sobre l'abecedari "A-Z", que es podrien aplicar a mà o amb aparells mecànics simples. Degut a aquestes característiques, molts d'ells es poden també desxifrar a mà fàcilment. I d'altra banda, en cas que a mà fos complicat o laboriós, la tecnologia actual acostuma a poder-los desxifrar amb molta facilitat.

Els mètodes més moderns doncs, utilitzats pels ordinadors cada dia (per exemple, quan accedim a una web amb https) operen amb bits i bytes, i realitzen algorismes molt més complicats, impossibles de desxifrar en un temps raonable fins i tot amb l'ajuda d'altres ordinadors).

Molts xifratges clàssics van ser utilitzats (o fins i tot inventats) per gent molt coneguda, com Juli Cèsar o Napoleó. Sovint es creaven amb finalitats militars (per a transportar missatges secrets entre persones del mateix bàndol). Amb els coneixements actuals, però, sovint és fàcil desxifrar-los fins i tot sense conèixer quin sistema s'ha utilitzat, mitjançant eines com l'anàlisi de freqüències.

Dins el concepte de xifratge clàssic però, a més dels sistemes senzills dels grecs i els romans, acostumem a incloure-hi també xifrats més elaborats com els que s'utilitzaven al Renaixement, així com els mètodes de xifratge utilitzats a la segona guerra mundial, com la màquina Enigma.

Tipus de xifratge clàssic

[modifica]

Generalment distingim dues categories de xifratge clàssic: xifratge per transposició[1] i xifratge per substitució.

Xifratge per substitució

[modifica]

En un xifratge per substitució, cada lletra (o grup de lletres) és reemplaçat per altres lletres, símbols, números o grups de lletres.

Substitució Monoalfabètica

[modifica]

Anomenem substitució monoalfabètica a aquells mètodes de substitució en què per a cada lletra (símbol) del missatge original correspon un sol símbol del missatge xifrat.

Una substitució monoalfabètica molt coneguda és la del Xifratge Cèsar. Per tal de xifrar un missatge amb Xifratge Cèsar, cada lletra és reemplaçada per la lletra que es troba k posicions més endavant a l'abecedari. Per exemple, si escollim avançar 3 posicions, la A seria reemplaçada per la D, la B per la E, la C per la F... i finalment la X per la A, la Y per la B i la Z per la C. Segons aquest exemple, la paraula "WIKIPEDIA" es convertiria en "ZLNLSHGLD".

alfabet normal A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
alfabet xifrat D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

En el nostre exemple (que és el que acostumava a utilitzar Cèsar), la clau del xifratge és 3, però evidentment es pot fer el mateix amb qualsevol número.

Si volem afegir una mica més de complexitat (fer-ho més difícil de desxifrar) podem agafar la idea de Cèsar i desordenar-ne l'abecedari xifrat mitjançant una paraula clau. Per exemple, si escollim la paraula "rinoceront" com a clau, l'abecedari xifrat començaria amb aquesta paraula (però obviant les lletres repetides), i llavors continuaria l'abecedari des de l'última lletra i afegint les lletres que faltin (ordenades en el seu ordre estàndard).

alfabet normal A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
alfabet xifrat R I N O C E T U V W X Y Z A B D F G H J K L M P Q S

En aquest cas, "WIKIPEDIA" ens quedaria "MVXVDCOVR". Com podem veure, habitualment es fa servir l'abecedari anglès (sense la ç), però podríem fer servir la mateixa tècnica amb qualsevol abecedari que escollim.

Substitució polialfabètica

[modifica]

En la substitució polialfabètica s'utilitza més d'un abecedari per al mateix missatge, de tal manera que una mateixa lletra del missatge original pot acabar convertida en lletres diferents en el missatge xifrat, en funció de la posició que ocupi en el text.

Una manera senzilla de fer substitució polialfabètica seria tenir dos alfabets xifrats diferents, i anar-los alternant a cada lletra. D'aquesta manera, la primera lletra del missatge es codificaria amb el primer alfabet, la segona amb el segon, la tercera amb el primer, etc.

Elaborant una mica més aquesta idea arribem al Xifratge de Vigenère, que parteix dels 26 possibles alfabets que podem obtenir del Xifratge Cèsar, i mitjançant una paraula clau n'escull uns quants per anar-los alternant.

Per tal de facilitar la feina de xifrar i desxifrar aquesta mena de xifratges basats en el Xifratge Cèsar, sovint s'utilitza una Tabula Recta per veure totes les opcions alhora.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

En el cas de Vigenère, si utilitzem la paraula clau "carxofa" voldrà dir que la primera lletra del missatge se xifrarà amb un Cèsar 3 (la c és la tercera lletra), la segona lletra es deixarà igual, la tercera se xifrarà amb un Cèsar 18, la quarta amb Cèsar 24, etc. És a dir, escollirem la fila de la Tabula Recta que comença amb la lletra que toqui de la paraula clau (i un cop se'ns acaba la paraula clau, simplement tornem a començar-la.

Continuant amb l'exemple, si volem xifrar la frase "Vigenère també es pot fer amb autokey" amb la clau "carxofa" escollida, ens quedaria així:

Missatge normal: VIGENERE TAMBE ES POT FER AMB AUTOKEY
Paraula clau: CARXOFAC ARXOF AC ARX OFA CAR XOFACAR
Missatge xifrat: XIXBBJRG TRJPJ EU PFQ TJR CMS XIYOMEP

Algunes substitucions inclouen l'ús de nombres en comptes de lletres. Un exemple extrem d'això és el Gran Xifratge, on es feien servir 587 números per tal de codificar síl·labes senceres.

Fragmentació

[modifica]

En casos com el del Gran Xifratge, en què un sol símbol del missatge original acaba representat per més d'un símbol en el missatge xifrat, parlem de fragmentació.

Un exemple conegut d'aquesta tècnica és el Quadrat de Polibi, que intercanvia cada lletra per un grup de dos números, cadascun entre 1 i 5.

1 2 3 4 5
1 A B C D E
2 F G H I/J K
3 L M N O P
4 Q R S T U
5 V W X Y Z

Com veiem, per tal d'encabir un alfabet de 26 lletres en una graella de 5x5 hem hagut d'ajuntar la I i la J a la mateixa casella. Altres variants combinen la U amb la V.

Posant un exemple, si vull codificar "Moltes felicitats Clara", el missatge xifrat em quedaria:

Missatge normal: M O L T E S F E L I C I T A T S C L A R A
Missatge xifrat: 32 34 31 44 15 43 21 15 31 24 13 24 44 11 44 43 13 31 11 42 11

De manera que cada símbol (cada lletra) ha acabat representat per dos símbols (dos números). D'altra banda, si volgués complicar més les coses, podria prescindir dels espais en el missatge xifrat, i donar-ho tot com una renglera de números (el meu receptor ja sabria que van de dos en dos i els separaria amb facilitat).

Un altre exemple famós de fragmentació és el Xifratge de Bacon, en què cada lletra es xubstitueix per un grup de cinc As o Bs.

a AAAAA g AABBA n ABBAA t BAABA
b AAAAB h AABBB o ABBAB u-v BAABB
c AAABA i-j ABAAA p ABBBA w BABAA
d AAABB k ABAAB q ABBBB x BABAB
i AABAA l ABABA r BAAAA i BABBA
f AABAB m ABABB s BAAAB z BABBB

En aquest cas, però, les As i Bs no serien el resultat final, ja que el Xifratge de Bacon està pensat per a ser utilitzat juntament amb esteganografia (ocultant també la pròpia existència del missatge). Així, les A i B en realitat acabaran essent per exemple dos tipus de lletra diferents, enmascarades en un mateix missatge.

Per exemple, el missatge "cansalada" es podria ocultar de la manera següent:

Missatge original: CANSALADA
Missatge xifrat: AAABA AAAAA AABBAA BAAAB AAAAA ABABA AAAAA AAABB
Esteganografia: les A seran normals i les B cursiva
Text qualsevol: És aquí la classe dels porcs? Sí, però ha estat cansalada.
Missatge amagat:
És aquí la classe dels porcs? Sí, però ha estat cansalada.

En aquest cas hem ignorat els signes de puntuació, i com que el text era més llarg que el missatge, hem omplert la part que ens sobrava amb Bs (aprofitant que en el codi de Bacon la seqüència BBBBB no es correspon amb cap lletra).

Altres alfabets

[modifica]
Missatge Pigpen
Missatge en Xifratge Francmaçó

Els símbols també han estat usats en comptes dels nombres, reemplaçant lletres o síl·labes. Un exemple d'això és l'alfabet del Zodíac, on els símbols del zodíac s'utilitzen per representar diferents lletres (per exemple, es fa servir el símbol del sol per substituir la A, Júpiter per la B, saturn per la C...). I un altre exemple conegut seria el xifratge francmaçó (o Pigpen), que representa les lletres amb símbols fets a partir de les caselles d'unes quadrícules predefinides.

D'altra banda, també podem combinar aquesta idea dels altres alfabets amb la fragmentació, i obtindríem coses com per exemple el Codi morse, que malgrat no s'ha inventat per utilitzar-lo com a xifrat, respon als mateixos principis (cada lletra es converteix en tres símbols: punts, ratlles i espais).

Xifratge per transposició

[modifica]

En els xifratges per transposició, en lloc d'intercanviar unes lletres per unes altres, el que es fa és intercanviar l'ordre de les lletres (mitjançant un algorisme concret).

Molts dels xifratges per transposició utilitzen algun disseny geomètric, com pot ser posar les lletres del missatge per files i llegir-ho per columnes, o escriure les lletres en ziga-zaga i llegir-ho en línia recta. Un exemple trivial però que dona a entendre la idea seria simplement escriure el missatge girat (primer l'última lletra, i enrere fins a la primera).

D'altra banda, també es pot fer la transposició amb l'ajuda d'instruments com l'escítala.

Si entrem en exemples més concrets, un dels xifratges per transposició més coneguts és la transposició per columnes, que funciona de la manera següent: escollim una paraula clau (en aquest cas "pernil"), i escrivim el nostre missatge per files que tinguin la mateixa amplada que la paraula escollida (si volem podem omplir els forats del final amb qualsevol lletra, tot i que això en facilitarà el desxifratge).

Missatge normal: AVUI ESTIC EDITANT LA WIKIPEDIA
Clau: pernil
p e r n i l
5 1 6 4 2 3
A V U I E S
T I C E D I
T A N T L A
W I K I P E
D I A X X X
Missatge xifrat: VIAI IEDL PXSI AEXI ETIX ATTW DUCN KA

Finalment copiem la graella que ens ha quedat, però aquesta vegada llegint per columnes (per ordre alfabètic, segons les lletres de la paraula clau). En aquest cas hem posat espais a la resposta cada quatre lletres per facilitar-ne la lectura i per dissimular l'espaiat original del missatge (la qual cosa és una pràctica habitual).

Un altre xifratge per transposició conegut és el Rail Fence, que escriu les coses en ziga-zaga a través de diferents rails i després llegeix normal d'esquerra a dreta. Per exemple, si escollim la clau 4 (quatre rails) per enviar el missatge "se m'ha escapat l'ornitorrinc al matí", el procediment serà el següent:

Missatge normal: SE MHA ESCAPAT LORNITORRINC AL MATI
Clau: 4
S . . . . . S . . . . . L . . . . . O . . . . . A . . . . .
. E . . . E . C . . . T . O . . . T . R . . . C . L . . . I
. . M . A . . . A . A . . . R . I . . . R . N . . . M . T .
. . . H . . . . . P . . . . . N . . . . . I . . . . . A . .
Missatge xifrat: SSLO AEEC TOTR CLIM AAAR IRNM THPN IA

Finalment, podríem combinar substitució amb transposició per tal de generar algorismes més complexes i, per tant, més difícils de desxifrar. Alguns exemples d'això poden ser els xifratges Bífid i Trífid, o el Xifratge VIC.

En els xifratges moderns com el xifratge per blocs o el DES es realitzen diverses substitucions i transposicions consecutives.

Criptoanàlisi dels xifratges clàssics

[modifica]

En general els xifratges clàssics són bastant fàcils de desxifrar. Molts d'ells, de fet, es poden decodificar fins i tot sense saber gaire coses del xifrat, de manera que són susceptibles de patir un atac de només text xifrat conegut. Alguns xifratges clàssics (com el Xifratge Cèsar) tenen un espai de clau molt reduït (molt poques possibilitats), així que poden ser decodificats amb un atac per la força bruta (és a dir, simplement provant totes les combinacions).

Un xifratge per substitució en canvi sí que té un espai de clau molt més ampli, però és susceptible a l'anàlisi de freqüències (les lletres més freqüents de l'idioma utilitzat en el missatge es correspondran amb les lletres o símbols que apareguin més sovint en el text xifrat). I de fet, si es conserven els espais i signes de puntuació, la tasca esdevé un passatemps interessant (que anomenem criptograma), ja que hom pot utilitzar els seus coneixements de l'idioma (quines paraules de dues i tres lletres són freqüents, quines van després dels apòstrofs o guions, etc) per tal de deduir gradualment quina lletra es correspon amb quina.

Escalant en complexitat, xifratges com el de Vigenère eviten la possibilitat d'un anàlisi de freqüències (com que cada lletra acabarà essent diferents caràcters en funció del moment, ja no podem simplement comptar quants caràcters tenim de cada per saber quantes lletres hi havia de cada). Tot i això, existeixen tècniques d'anàlisi de freqüències més avançades que poden desxifrar el vigenère (com pot ser el mètode Kasiski, que divideix el text en diferents subconjunts en funció de la longitud de la clau, per tal d'agrupar totes les lletres que hagin estat xifrades amb el mateix alfabet).

Finalment, els xifratges moderns estan dissenyats per suportar atacs més potents que simplement el de només text xifrat conegut. És a dir, un bon xifratge modern ha d'estar segur fins i tot si l'atacant sap quin xifratge s'ha fet servir, si sap quin missatge es correspon amb bona part del text xifrat, o si pot obtenir text xifrat a partir de missatges escollits o viceversa (sense necessitat de saber quin procés converteix un en l'altre).

Referències

[modifica]
  1. Lasry, George. A Methodology for the Cryptanalysis of Classical Ciphers with Search Metaheuristics (en anglès). Kassel University Press GmbH, 2018, p. 61. ISBN 9783737604581. 

Bibliografia

[modifica]
  • Singh, Simón. The Code Book The Science of Secrecy from Ancient Egypt to Quantum *Cryptography. Nova York: Anchor, 2000.
  • D'Agapeyeff, Alexander. Codes and Ciphers. Oxford UP, 1939.
  • Laffin, John. Codes and Ciphers: Secret Writing through the Ages. Abelard-Schuman, 1964.
  • Wrixon, Fred B. Codes, Ciphers, and Secret Languages. Nova York: Bonanza Books, 1989.

Vegeu també

[modifica]

Enllaços externs

[modifica]