La millor xifra
polialfabètica: la xifra de Vigenère
Al segle XVI el francès Blaise de Vigenère
va millorar unes idees un segle anteriors de l'artista-matemàtic italià
Leon Battista Alberti.
Vigenère va publicar un llibre titulat Traité des chiffres où secrètes
manières d'escrire on explicava una forma de xifratge polialfabètic:
Una
mateixa lletra, al llarg del missatge, pot està representada per altres
de forma canviant. Una A podrà ser algunes vegades una D o una
H, però,
atenció!, no sempre la D o la H representarà la A.
En el fons la xifra de Vigenère era una forma d'utilitzar la xifra
del Cèsar amb uns quants alfabets a la vegada. Però el mètode era tan bo
que el va poder publicar sense guardar-lo en secret perquè encara que al
començament del missatge estigués escrit ben clarament "AQUEST MISSATGE
ESTÀ XIFRAT AMB EL SISTEMA DE VIGENÈRE" sense la paraula clau era
pràcticament impossible descodificar-lo.
Vegem com funciona.
S'ha de decidir una paraula clau. Per exemple CALAIX. Aquesta
paraula només l'han de conèixer la persona emissora i la receptora.
A sota de cada lletra del missatge es va repetint la paraula
clau.
Tenim la Taula de Vigenère amb els 26 alfabets desplaçats. Només
haurem de treballar amb les files que assenyalen les lletres de la
nostra paraula clau: C, A, L, I i X
Totes les lletres del missatge aparellades amb la lletra C de la
paraula clau es codificaran amb la fila C, totes les lletres
aparellades amb les A de la clau, es codifiquen amb l'alfabet de la
fila A...
Si observem com ha quedat la xifra veurem algunes fites
importants
Text clar
Quedem avuia les cinc
Text xifrat
SUPDMJ CVFIIIGS NIVZ
la lletra E del text clar queda codificada una vegada amb
la P, una altra amb la M i una encara amb la G.
la lletra I del text codificat representa dues vegades la
pròpia I, una la lletra A i una altra la lletra L
La xifra de Vigenère desafia completament l'anàlisi de freqüències i,
durant molts anys va ser la millor xifra coneguda. Però tenia un punt
feble. Quin?
Fes servir la màquina codificadora en xifra
de Vigenère
I van arribar Kasiski i
Babbabge
Durant gairebé tres
segles ningú va saber com atacar la Xifra de Vigenère. Però a
meitat del segle XIX dos criptoanalistes, de forma independent,
van saber trobar per on vèncer-la. Un va ser un oficial prussià,
F.W. Kasiski i l'altre un matemàtics anglès, Charles Babbage, un
dels precursors dels ordinadors.
Els criptoanalistes són
especialistes a trobar el més mínim punt feble d'un mètode de
xifrat i saben separar perfectament les diferents parts del
problema de la descodificació.
El que era fonamental d'esbrinar en la Xifra de Vigenère era
la clau. Però la clau té dues característiques: la longitud de
la paraula i les lletres concretes que la formen.
Charles Babbage
El primer objectiu de Kasiski i de Babbage va ser esbrinar la
longitud de la clau. Però com? L'explicació és una mica complicada però
és molt interessant intentar-la seguir.
1a fase: Com saber la longitud de la clau
Si un missatge és prou llarg és possible que determinats grups de
lletres, per exemple la paraula QUE, coincideixi alguna o algunes
vegades, sobre el mateixos llocs de la paraula clau, per tant
quedaran codificats també amb les mateixes lletres.
Podem buscar uns
quants casos i anotar quina distància en lletres els separen.
Aquesta distància ha de ser, forçosament, un múltiple de la longitud
de la clau.
Quantes més repeticions tinguem, ja sigui d'un mateix grup o
de grups diferents, millor, perquè tindrem més informació
La clau serà un divisor comú de totes aquestes
distàncies.
Observem un exemple per desxifrar aquest text en el que hem
marcat un parell de repeticions:
Si busquem totes les repeticions de grups de 2, 3, 4 o 5 lletres
podem obtenir una taula llista de distàncies de repetició, totes
múltiple de la llargada de la clau
Al text superior la clau és de 5 lletres
2a fase: trobar la paraula clau
Sabem que la clau té cinc lletres i, per tant, que s'han fet
servir, ordenadament cinc alfabets diferents. Cada cinc lletres
estan ordenades amb el mateix:
Grup 1: lletres 1, 6, 11, 16, 21...
Grup 2: lletres 2, 7, 12, 17, 22...
Grup 3: lletres 3, 8, 13, 18, 23...
Grup 4: lletres 4, 9, 14, 24, 29...
Grup 5: lletres 5, 10, 15, 20, 25...
Al que haurem de fer ara és separar cada grup de lletres, fer a
cada grup el seu anàlisi de freqüències i buscar a quina fila de la
taula de Vigenère correspon.
Amb aquest enllaç obriràs una finestra en el que, en
poc més de 5 minuts, podràs veure, amb animacions
incloses, com s'aplica el mètode
complet per trobar la clau (longitud i lletres) del missatge de l'exemple.
Tens una eina
d'anàlisi informàtic de la Clau de Vigenère
Contraataquem a Kasiski
Kasiski i Babbage van evidenciar el punt feble de la
Xifra de Vigenère: es pot descobrir la longitud de la clau. Com podem
contraatacar?
La clau infinita
Si tenim una clau tan llarga com el propi text no
ens la podran trobar. Però, com aconseguir una clau prou llarga? Un
bon truc és fer servir la mateixa pàgina de la mateix edició d'un
llibre. Per exemple, ens podem posar d'acord en utilitzar el llibre
"L'art de la comunicació secreta" de David Juher en l'edició de
Llibres de l'Índex de l'any 2004. Això només ho sabem les dues
persones interessades. Al començament del missatge només caldria
escriure un 77 per entendre que la clau és la pàgina 77 del llibre.
Amb aquest truc la clau serà:
Encara que aquesta clau és molt llarga la millor
seria una clau infinita. No la tenim, però ens hi acostem.
La clau a l'atzar
Els criptoanalistes tenen molta paciència i si
pensem que la clau són paraules conegudes podem fer proves fins
trobar el llibre-clau. A més la llengua repeteix paraules (que, de,
en...) que, per força es repetiran a la clau. Seria molt millor una
clau a l'atzar
AHNTOEPLLDMVPWSDKJGFUEWKDMDSKFLWOP...
Aquesta clau té alguns inconvenients:
és impossible de recordar i pesada
d'utilitzar
no és completament a l'atzar; l'he feta
picant amb els ulls tancats al teclat i com que faig, ara un dit
d'una mà, ara un dit de l'altra, hi ha alternativament, més o
menys, una lletra de cada meitat del teclat.
Encara que una màquina no pot fabricar atzar el
pot simular força bé. A les màquines no es cansen amb les feines
pesades. Perquè no deixem treballar a la màquina?
L'enigma d'ENIGMA
Entre la 1a i la 2a Guerra Mundial els alemanys van
utilitzar una màquina diabòlica per encriptar missatges que
s'acostava molt a la utilització del mètode de Vigenère amb una
clau llarguíssima i feta a l'atzar. La van batejar amb el nom
d'ENIGMA. Com era aquesta màquina? La
part visible ens mostra un teclat i unes lletres que
s'il·luminaven. Pitjant una tecla s'encenia la lletra codi (o bé
la correcta quan desxifràvem).
A la imatge tens un enllaç amb un emulador de la màquina
ENIGMA.
El missatge
FFFFF FFFFF FFFFF FFFFF FFFFF
s'ha codificat com
OXZIZ ZSXBR XGREJ HQJJD UVTGI
Observem per sobre el seu funcionament.
la màquina tenia unes rodes modificadores o rotors
que connectaven cada punt d'entrada amb un altre de sortida
descol·locat respecte al primer. Cada vegada que es picava una
lletra el modificador girava una posició. La imatge et presenta un
esquema amb només sis lletres, però els rotors d'ENIGMA tenien 26.
es posaven tres modificadors seguits; quan el primer havia
completat una volta feia girar una posició al següent. D'aquesta
forma els modificadors no tornaven a estar en la mateixa posició
fins a 26·26·26 moviments: 17576 girs. Pel mateix criteri hi ha
17576 posicions inicials possibles dels tres modificadors. Cada
posició és una clau específica: F-G-P significaria posar el
primer en F, el segon en G i el tercer en P.
els rotors, però, eren intercanviables; si en tenim
tres hi ha sis disposicions possibles
1-2-3
1-3-2
2-1-3
2-3-1
3-1-2
3-2-1
Una clau afegida seria com disposar-los. Per exemple
podríem dir (2-1-3; H-M-B) i indicaríem com posar els
modificadors i com orientar-los. Ara hem multiplicat per 6 les
possibilitats inicials (6·17576 = 105 456 possibilitats)
a més la màquina tenia un clauer que permetia
alterar el teclat de forma que la A es convertís en G (i la G en A)
o la B en U (i la U en B). Es podien intercanviar sis parells de
lletres el que dóna més de cent milions de formes diferents!
si diem com col·locar els sis cables i la clau de
posició-orientació dels modificadors ens en anem a més de deu
mil bilions de possibilitats inicials. Recordem que a cada tecla
que piquem la posició global dels modificadors canvia un pas.
al final del camí dels modificadors hi havia un
reflector que feia a tornar passar el corrent en direcció contrària
per encendre la bombeta.
A la imatge tens un enllaç que porta a un emulador d'Enigma
amb els rotors visibles.
Així es pot veure com van girant
a cada lletra que es tecleja.
la cosa no acabava aquí; l'exèrcit alemany disposava d'un llibre
de claus per determinar la posició inicial del dia de clauers i
rotors. Però al començament del missatge s'enviava un codi de tres
lletres que indicava com reorientar els rotors per descodificar la
resta del missatge. Aquest codi de tres lletres s'escrivia dues
vegades per confirmar-ho. És a dir:
el descodificador posava tota la
màquina en la posició del dia.
Descodificava les sis primeres
lletres i li sortia una seqüència repetida, per exemple ZFDZFD.
Col·locava els rotors orientats en ZFD i descodificava la resta del
missatge.
Recordem que les sis primeres lletres també s'enviaven
codificades i l'aspecte de ZFDZFD podia ser CEOUNY.
Desenigmant l'ENIGMA
La victòria sobre la màquina ENIGMA té dos episodis principals: el primer
a Polònia i el segon a Anglaterra
L'episodi de Polònia
El protagonista principal del primer atac amb èxit a
ENIGMA va ser Marian Adam Rejewski. A Polònia estaven
(amb encert) molt temorosos d'una possible invasió
alemanya i tenien gran interés en trencar el codi d'ENIGMA.
Els criptoanalistes polonesos disposaven
d'una rèplica de la màquina ENIGMA. Per tant el problema
real era buscar una manera de descobrir com col·locar
els rotors i els clauers.
Rejewski va pensar en dividir el problema en dues
parts:
descobrir l'ordre i la posició dels rotors
descobrir els intercanvis de lletres provocats
pels clauers
Marian A. Rejewski
Encara que hi havia més possibilitats de combinacions dels
clauers va pensar que era un problema més fàcil de solucionar. Només
es canviaven sis parells de lletres i la resta quedaven igual. No
havia de ser especialment difícil descobrir els intercanvis. Per
exemple, si veiem la la paraula TARPENAR no costa gaire descobrir
que la R i la T estan canviades i la paraula correcta és RATPENAT.
Per tant Rejewski va abordar el problema més complexe dels rotors. Però... on
estava el defecte dels sistema de l'exèrcit alemany? En la clau
repetida! Quan al començament del missatge hi trobem CEOUNY sabem
que són dos blocs que representen les mateixes lletres (CEO = UNY).
Això ens permet saber que en tres voltes de rotor el que es
codificava amb C ara ho fa amb U, el que ho feia amb E ara ho farà
amb N i que la O es tornava Y.
A partir d'aquí, fent cadenes de
lletres amb tots els missatges d'un dia, fent llistats exhaustius
durant tot un any i fabricant unes màquines que simplifiquessin els
càlculs (anomenades bombes) amb pocs missatges era
relativament fàcil esbrinar les posicions dels tres rotors i
descodificar la resta de missatges del dia.
Però quan el criptògrafs alemanys van afegir dos rotors més a
ENIGMA (disposaven de 5 i col·locaven tres a la màquina) tot el treball s'havia
de tornar a començar. Però la feina, a més, amb els mitjans dels
polonesos era inabastable. Amb la incorporació de dues rodes més les
17576 posicions inicials dels rotors s'havien convertit en gairebé
12 milions (265) i les claves totals eren ara pròximes
als 160 trilions.
L'episodi d'Anglaterra
Polònia va posar a l'abast del servei d'Inteligència anglès les
descobertes fetes i el disseny de les bombes que ajudaven a
col·locar els rotors. El govern britànic va crear un gran centre de
criptoanàlisi a Bletchley Park, prop de Londres, amb centenars de
persones treballant en secret.
A Anglaterra els criptoanalistes van millorar les bombes
poloneses i van trobar altres dreceres per desencriptar les claus
inicials. Per exemple van observar que poques vegades la clau es
formava per tecles pròximes. Continuava havent un problema
important: i si l'exèrcit alemany descobria que el punt feble d'ENIGMA era la repetició de la clau, com s'ho farien?
Aquí és on entra, entre d'altres, el gran matemàtic
anglès Alan Turing.
Turing havia fet grans aportacions
al desenvolupament d'importants aspectes de la lògica
matemàtica. A més havia assentat les primeres bases de
com hauria de funcionar el que ara anomenem ordinador.
Les bombes angleses eren, en poc temps, totalment
diferents de les poloneses. Amb vàlvules de buit, més
potents... i en gran part era gràcies a les idees de
Turing.
Però la idea genial de Turing va ser una altra. Va
observar que els primers missatges de cada dia donaven informacions
meteorològiques. Per tant hi hauria tot un conjunt de paraules
(temps, vent, temperatura...) que es normalment hi apareixerien. A
aquestes paraules especials els criptoanalistes les anomenen
puntals. També sabien que, per la forma d'estar construïda, la
màquina ENIGMA era incapaç de codificar una lletra amb ella mateixa
(D no es codifica mai amb D).
Observem, de forma simplificada, com s'aplicava la
tècnica dels puntals:
Es buscava un lloc on el puntal (per
exemple TEMPERATURA) no coincidís amb cap lletra igual. Si es
pensava que la paraula apareixia al començament del text la
recerca es començava per aquí.
A partir del joc d'equivalències obtingut es
posaven a treballar a les bombes per poder esbrinar la
col·locació dels modificadors.
Amb tècniques com aquestes es van poder descodificar
els missatges de les tropes alemanyes i saber per anticipat algunes
de les accions militars previstes prenen mesures que, ben segur, van
ajudar a accelerar el final de la guerra.
