Criptografia simètrica

Xifratge simètric. La simetria rau en el fet que la clau de xifratge és la mateixa que la del procés invers: el desxifratge. En alguns casos fins i tot l'algorisme de xifratge i el de desxifratge són el mateix

La criptografia simètrica, anomenada també de clau secreta (per oposició a la criptografia de clau pública), és la forma més antiga de xifratge. Es tenen rastres de la seva utilització pels Egipcis cap al 2000 aC. Més recent, es pot citar el xifratge de Juli Cèsar, del qual el ROT13 n'és una variant. Es basa en el fet que emissor i receptor posseeixen tots dos el coneixement d'una clau secreta amb la que poden xifrar o desxifrar els textos.

Clau de seguretat

Un dels conceptes fonamentals de la criptografia simètrica és la clau, que és una informació que ha de permetre xifrar i desxifrar un missatge i sobre la qual pot descansar tota la seguretat de la comunicació. Un algorisme com el ROT13, per exemple, no té clau, n'hi ha prou amb saber que és aquest el mètode que ha estat utilitzat per xifrar un missatge i es pot tenir accés al text clar. En altres paraules, aquí, el secret resideix en el mètode utilitzat. Aquest tipus de secret no satisfà els usuaris dels sistemes de xifratge, ja que la concepció d'un bon algorisme és molt difícil i un cop descobert ja no ofereix cap seguretat, i tots els missatges que han estat xifrats amb ell esdevenen accessibles. Es pot modificar el ROT13 canviant el valor de la diferència, aquest valor passa a ser llavors la clau. El conjunt de les claus possibles - l'espai de les claus - ofereix 26 diferències possibles. Encara que una mica més pesat, el desxiframent continua sent accessible fins i tot a mà. I amb ordinadors, es poden provar trilions claus.

A partir d'aquest exemple es veu la importància d'aquesta clau i de les restriccions. August Kerckhoffs a (La criptografia militar, 1883) és un dels primers a haver-ho comprès plenament que: per poder estar segur, l'algorisme s'ha de poder divulgar. És el que es diu d'ara endavant el principi de Kerckhoffs. Cal afegir que aquesta clau ha de poder prendre prou valors diferents perquè un atac exhaustiu - prova sistemàtica de totes les claus - no es pugui portar a terme, ja que per ser massa lent. Es parla de seguretat calculatòria.

Aquesta seguretat calculatòria és, evidentment, dependent del temps, les prestacions dels mitjans de càlcul creixen contínuament, un sistema de xifratge s'enfronta a una adversitat cada dia més forta, mentre que el missatge xifrat no canvia. La il·lustració d'aquest problema és el DES, aquest sistema s'ha fet obsolet a causa que el nombre de claus que pot utilitzar és massa petit (tanmateix 2⁵⁶). Es pensa que, actualment, 2⁸⁰ és un mínim estricte. A títol indicatiu, l'última estàndard escollit pels Americans el desembre de 2001, l'AES, utilitza claus, la mida de les quals és almenys de 128 bits, en altres paraules n'hi ha 2¹²⁸. Per donar una ordre de magnitud sobre aquest nombre, dona aproximadament 3,4 10³⁸ claus possibles; l'edat de l'univers és de 10¹⁰ anys, si se suposa que és possible provar un bilió de claus per segon (o sigui 3,2 10¹⁹ claus anualment) caldria més de mil milions de vegades l'edat de l'univers per provar-les totes. En tal cas es pot pensar raonablement que el nostre algorisme és segur. Tanmateix, és fer una hipòtesi molt forta sobre l'algorisme suposar que l'únic mitjà de trencar-lo és de portar un atac exhaustiu: nombroses són les falles que poden encobrir un algorisme i encara més nombroses són les males utilitzacions d'un algorisme.

La qüestió que formula aquesta noció de seguretat calculatòria és la d'una seguretat absoluta. Se sap des de Claude Shannon i el seu article Comunicació theory of secrecy system (1949) que el xifratge de Vernam que consisteix a afegir al missatge en clar una clau de la mateixa longitud (veure XOR) és perfectament segur. És l'únic per al qual s'ha estat capaç de demostrar-ho. L'inconvenient és que per a avaluar un missatge de n bits, cal prèviament haver intercanviat una clau de n bits amb el destinatari del missatge, i això per una via absolutament segura, si no, xifrar es fa inútil. Molt pocs casos necessiten tal sistema, però era tanmateix el sistema utilitzat per al Telèfon vermell entre el Kremlin i la Casa Blanca.

Tècniques classiques

Fins a l'adveniment de les comunicacions digitals, els sistemes utilitzaven l'alfabet i no combinaven les substitucions - els símbols es canvien però es queden al mateix lloc - i les xifratge per tansposició - els símbols no es modifiquen però canvien de lloc. Quan la substitució aplicada depèn del lloc de la lletra en el text, es parla de substitució polialfabètica – per exemple el xifratge de Vigenère, Enigma -, en oposició a la substitució monoalfabètica on la substitució és la mateixa per a totes les lletres – per exemple una simple simple diferència com en el xifratge de Cèsar.

Xifratges per substitució

Entre les substitucions hi ha les diferències, on cada lletra del missatge a xifrar es transforma en la lletra situada n posicions més lluny en l'alfabet (si no pot ser perquè s'acaben les lletres, en acabar per la z es continua comptant tornant a començar per la a). El cas de la diferència simple - una sola diferència idèntica per a totes les lletres del missatge – es coneix també com el xifratge de Cèsar. Seguint la mateixa línia, però una mica més complet hi ha el xifratge de Vigenère, que no utilitza una diferència sinó un nombre qualsevol de diferències n, la primera diferència es fa servir per xifrar les lletres número 1, 1+n, 1+2n... la segona diferència per a les lletres número 2, 2+n, 2+2n... Usualment, el valor d'aquestes diferències ve donat per una paraula de longitud n del qual la lletra i-èsima dona el valor de la i-èsima diferència. Per exemple.

Missatge clar : wikipedia
Paraula clau : crypto
Missatge xifrat : yzixirfzy

Una 'a' a la paraula clau correspon a una diferència de 0, una 'b' a una diferència d'1, etc. En l'exemple, la clau té 6 lletres, per tant les lletres 1 ('w') i 7 ('d') es xifren amb el mateix decalatge: 2.

La màquina Enigma utilitzada pels alemanys durant la Segona Guerra Mundial es basa també en substitucions, però amb un mecanisme molt més sofisticat.

Una altra forma de la substitució és el diccionari: en lloc de canviar els símbols del missatge un a un, són paraules senceres les que se substitueixen.

Xifratges per transposició

Per a les transposicions es modifica l'ordre dels símbols del text clar. Una tècnica consisteix a donar-se una paraula clau, a escriure el missatge sota aquesta paraula clau i a llegir el text en columna, per ordre alfabètic. Per exemple:

Missatge : viquipediaesunaenciclopedialliure 
Paraula clau : crypto
S'escriu:
viquip
ediaes
unaenc
iclope
dialli
ure***

Llavors s'escriu la paraula clau per ordre alfabetic:

coprty

Això indica les transposicions que s'han de fer a cada fila, com que la w ha quedat al mateix lloc, la primera lletra no canvia, la e que era l'última ha anat a parar al segon lloc, per tant a cada fila l'última lletra es posa al lloc de la segona, i així successivament:

vpuiiq 
esadei
ucenna
ieocpl
dilila
u**r*e

En acabar es llegeixen les lletres en columnes.

El missatge xifrat que resulta és: veuidupscei*uaeol*idncirienpl*qialae

Els asteriscs s'han afegit per indicar els espai (tipografia) espais en el missatge xifrat únicament per facilitar la llegibilitat.

Tècniques modernes

Des de l'adveniment de les comunicacions digitals, els paradigmes del xifratge simètric han canviat força. Per una banda, la disciplina s'ha formalitzat, fins i tot si la concepció de sistema de xifratge conserva inevitablement un aspecte artesanal. En efecte en aquest àmbit, l'única cosa que se sap provar és la resistència de cara a tipus d'atacs coneguts. D'altra banda, ha canviat la forma del text xifrat. Els algorismes moderns xifren successions de bits.

Es distingeixen dos tipus d'algorismes, els algorismes en blocs, que prenen n bits de l'entrada i en surten n, i els algorismes de flux, que xifren bit a bit seguint el model de la xifratge de Vernam.

Xifratge per flux

En aquest últim cas, l'algorisme genera una successió de bits que és afegit (XOR) a la successió binària a xifrar. Les tècniques utilitzades per generar la successió que s'afegeix – anomenada successió que xifra -- són diverses, però les que s'utilitzen més sovint són els registres de decalatge amb retroalimentació lineal.

Xifratge per blocs

La segona família d'algorismes, el den blocs, en general es construeix sobre un model iteratiu. Aquest model utilitza una funció F que pren una clau k i un missatge M de n bits. És aquesta funció F que és iterada un cert nombre de vegades, es parla de moltes rondes. A cada ronda, la clau k utilitzada canvia i el missatge que es xifra és el resultat de la iteració precedent. Els blocs han de ser prou grans perquè la funció no es pugui descriure mitjançant una taula, 64 bits es consideren suficients.

$C_{1}=F(k_{1},M)$ ;

$C_{2}=F(k_{2},C_{1})$ ;

...

$C_{r}=F(k_{r},C_{r-1})$ ;

Les claus $k_{i}$ utilitzades es dedueixen d'una clau estre K que és la quantitat secreta que han de compartir emissor i receptor. L'algorisme que genera aquestes claus a partir de K s'anomena l'algorisme de programació de claus.

Perquè un sistema d'aquest tipus pugui funcionar, la funció F utilitzada ha de ser una permutació, és a dir que cal que per a tota clau k i missatge M poder recalcular M a partir de F(k,M) , altrament el desxiframent no és possible i per tant no es disposa d'un algorisme utilitzable. Formalment, això significa que existeix una funció G que verifica

$G(k,F(k,M))=M$.

La seguretat del sistema resideix essencialment a dos indrets, l'algorisme de programació de claus i la robustesa de la funció F . Si l'algorisme de programació està mal dissenyat, les $k_{i}$ poden ser deduïbles unes de les altres, o mal repartides... Dir de la funció F que és robusta significa que se suposa difícil d'invertir sense conèixer la clau k que ha servit en el càlcul de C = F(k,M) . En Altres Paraules, coneixent només C, F i G, no s'ha de poder trobar el missatge M, si no és efectuant una cerca exhaustiva de la clau k, és a dir calculant

1) $X=G(k,C$);

2) $Y=F(k,X)$;

i això per a totes les claus k fins que se'n trobi una per a la qual Y és igual a C. Un està llavors segur de tenir el missatge M que no és altre que X. El problema és que si k està constituït de l bits, calen de mitjana $2^{l}/2=2^{l-1}$ proves. Prenent l prou gran, es pot fer que això no sigui realitzable a la pràctica: suposem que es puguin intentar 10⁹ (mil milions) de claus per segon, que és aproximadament 2³⁰, els segons que té l'any són 31557600 que són 2²⁵, en conseqüència es poden provar 2⁵⁵ claus anualment. Si es pren per a l un valor de 80 bits, caldrien 2²⁴ anys, més d'1 milió d'anys. Una tècnica molt escampada per fabricar funcions F és la de l'esquema de Feistel. En aquest esquema, el missatge a avaluar es talla en 2 blocs de n/2 bits, M = (L,R) i el missatge xifrat és

$C=(R,L+f(k,R))$

on el '+' és el XOR i f és una funció qualsevol, ja no s'ha de suposar que és una permutació. En efecte, es pot trobar M a partir de la clau k

1) coneixent C, es coneix R que és la seva part esquerra,

2) es calcula f(k,R) ,

3) s'afegeix el resultat del càlcul precedent a la part dreta de C, i es troba L,

això sense restricció sobre f. Clarament, en aquest esquema, la robustesa de F descansa sobre la funció f.

Vegeu també

• Xifratge de Vigenère
• Xifratge de Cèsar
• Xifra dels quatre quadrats
• DES