Dossier: Criptografia. 10 Criptologia i informàtica (la Colossus)

Fer que els codis secrets siguin irrompibles és el somni de tota la vida dels professionals de la seguretat. Des de l'antiguitat, els humans van inventar sistemes manuals i després mecànics abans de la revolució electrònica. Descobreix la criptologia i els seus usos, des del xifratge tradicional fins al xifratge RSA i la informàtica.

La criptologia i la informàtica han conegut un desenvolupament des de la Segona Guerra Mundial. Creada per Claude Shannon, la teoria de la informació, que va conduir a la digitalització de branques tecnològiques senceres, va néixer de la qüestió del que podia aprendre un adversari observant la comunicació xifrada.

El matemàtic britànic Alan Turing, conegut per haver modelat la noció de computabilitat amb la màquina que porta el seu nom, va tenir un paper crucial dins de l'equip de Bletchley Park, responsable de desxifrar els missatges de l'exèrcit alemany.

Clic a la imatge per engrandir. L'interior d'una de les màquines electromecàniques Enigma, que va ser utilitzada per l'exèrcit alemany per xifrar missatges durant la Segona Guerra Mundial. Alan Turing va tenir un paper important en el desxiframent d'aquest codi. Crèdit: TedColes, Wikimedia Commons, DP.

Trobar les claus s'estava convertint en una tasca massa complexa per fer-la a mà, i s'havien de construir màquines cada cop més potents per provar les innombrables combinacions possibles. Les tècniques utilitzades per realitzar aquests càlculs van ser crucials per al desenvolupament dels primers ordinadors.

Clic a la imatge per engrandir. Retrat d'Alan Turing a la dècada del 1940. Crèdit: Criticalgamer

L'enginyer telefònic Tommy H. Flowers va tenir la idea d'utilitzar vàlvules de buit, utilitzades recentment per la commutació telefònica, per tal de construir una calculadora enorme, el Colossus, destinada a desxifrar el xifratge del teleimpressor alemany.

Clic a la imatge per engrandir. Retrat de Tommy H. Flowers a la dècada del 1940. Crèdit: KPBS, BBC

La calculadora Colossus

El progrés aconseguit pels mitjans informàtics segueix una llei empírica, anomenada llei de Moore, que rep el nom del director de recerca del fabricant americà de circuits integrats Fairchild, qui ho va afirmar per primera vegada el 1965. Això afirma que la potència dels ordinadors electrònics es duplica cada 18 mesos, cosa que s'ha verificat fins avui. Mentre que l'ordinador ENIAC va trigar més de 70 hores a calcular 2.000 decimals del nombre π el 1949, l'ordinador més petit integrat en un telèfon mòbil actual realitza aquest càlcul en una fracció de segon. El 1977, la revista  Scientific American va presentar el RSA sota el nom de "un nou sistema que trigaria milions d'anys a trencar-se". Tanmateix, la clau pública que contenia va ser factoritzada el 1994, molt abans dels terminis anunciats!

Clic a la imatge per engrandir. El Colossus, la primera calculadora electrònica. Crèdit: Historyblog

Aquest progrés increïble i constant permet aplicar la força bruta per cercar la clau d'un procés en conjunts cada cop més grans. Tanmateix, és el xifrador i no el desxifrador qui es beneficia dels avenços en la potència de càlcul. Suposem que, en un moment donat, s'utilitzen nombres de 200 dígits com a mòdul RSA . Si la potència de càlcul es duplica, la mida del mòdul es pot augmentar a 250 dígits sense que l'usuari noti el més mínim canvi en la velocitat del càlcul. El treball de l'oponent per factoritzar aquest nou mòdul, però, segueix una llei donada per la fórmula c(n) = exp(k(ln(n))^1/3 (ln(ln(n)))^2/3) per a un nombre de n dígits. Per tant, aquest treball s'haurà de multiplicar per un factor de 36. Amb la seva potència de càlcul, que només s'haurà duplicat, haurà perdut un factor de 18 en el procés. Com més potents siguin les màquines, més gran serà l'asimetria entre el xifratge i l'atac dóna un avantatge al xifratge.

Ho he vist aquí.