Estudi de l'algorisme d'encriptació AES i del seu funcionament

Estudi de l’algorisme d’encriptació AES i del seu

funcionament

Laura Roigé Foix

Treball de recerca 2n de batxillerat

IES Montserrat

Tutora: Glòria Peraita

Curs 2013-2014

Estudi de l'algorisme d'encriptació AES i del seu funcionament 1

Índex:

1.Introducció i justificació.....................................................................................3

2.Metodologia......................................................................................................5

3.Context històric.................................................................................................6

4.Criptografia.......................................................................................................8

4.1.Criptografia de clau privada...........................................................................8

4.2.Criptografia de clau pública...........................................................................9

4.2.1.Funcionament ...........................................................................................10

4.2.2.avantatges i desavantatges......................................................................11

4.3.Signatura digital...........................................................................................11

5.Conceptes matemàtics utilitzats al treball.......................................................14

5.1.Congruències...............................................................................................14

5.2.Cossos.........................................................................................................14

5.2.1.Cossos finits..............................................................................................15

5.3.Algorisme d’Euclides extès i identitat de Bézout.........................................16

5.4.Funcions lògiques: XOR..............................................................................18

6.AES.................................................................................................................19

6.1.Funcionament de l’AES...............................................................................19

6.1.1.SubBytes..................................................................................................19

6.1.2.ShiftRows..................................................................................................20

6.1.3.MixColumns..............................................................................................21

6.1.4.AddRoundKey...........................................................................................21

6.1.5.Claus de ronda..........................................................................................22

6.1.6.Rondes......................................................................................................22

6.1.7.Desencriptat de l'AES...............................................................................23

7.Part pràctica....................................................................................................24


8.Conclusió........................................................................................................25

9. Agraïments.....................................................................................................26

10.Bibliografia....................................................................................................27

Annex I: SubBytes.............................................................................................28

Annex III: AES....................................................................................................29

Annex III: El llenguatge ASCII............................................................................31

Annex IV: Glossari.............................................................................................32

Annex V: CD......................................................................................................34


1.Introducció i justificació

He fet aquest treball centrant-me en dos àmbits que m’interessen molt de cara als meus estudis i al meu futur: les matemàtiques i la informàtica. En el moment en que em trobo en la meva educació, fer aquest treball és una oportunitat per veure les aplicacions pràctiques que es poden donar als estudis que m’interessen.

Un altre objectiu que m’he marcat i és explicar, d'una manera clara i detallada, com funciona la criptografia, i més concretament l’algorisme AES (Advanced Encryption Standard).

La criptografia és un element present en el nostre dia a dia, i fa funcionar coses tan quotidianes com les trucades telefòniques o les connexions inalàmbriques i tan complexes com les transaccions bancàries o la protecció d'arxius governamentals.

L’AES és un algorisme de xifratge que va ser dissenyat fa més de quinze anys i es va convertir en estàndard internacional de xifratge fa més de deu1. Les prestacions de les noves tecnologies han canviat molt en els últims anys, però no s’ha aconseguit trencar aquest algorisme, tot i que s’hagi aconseguit debilitar-lo lleugerament sense comprometre la seva fortalesa2. Crec que l'AES és un model de funcionament, ja que el seu algorisme de funcionament és públic i tot i així encara ningú ha aconseguit trencar-lo3. Per això considero que aquest estudi del funcionament de l’AES està justificat, encara que en el moment en que acabi el treball aquest algorisme hagi estat trencat.

A més, la criptografia és ara un tema d’actualitat, ja que mou gran part del món de les finances i la informació a petita i gran escala, i això ens afecta a tots, ja que tots en som usuaris. A més, tot i ser un tema important i actual, la criptografia és relativament poc coneguda i tractada, i trobo interessant donar-la a conèixer.

1 L'AES fou dissenyat l'any 1997 i fou designat estàndard internacional pel NIST (National

Institute of Standards and Technology) el 2000.

2 El 17 d'agost de 2011 va sortir al diari El País la notícia que tres investigadors, Andrey Bogdanov, Dmitry Khovratovich y Christian Rechberger, que treballaven al centre de recerca de Microsoft, havien aconseguit trencar l’AES. En realitat, aquests tres investigadors havien trobat una manera d’atacar l’AES que podia trencar aquest algorisme d’encriptació en una quarta part del temps que es necessita per fer-ho amb força bruta (veure glossari). Tot i que és una millora notable, no compromet la seguretat de les dades encriptades amb AES, ja que el nombre d’operacions requerides per trencar-lo és 8*1037, una xifra inassolible per la tecnologia actual. Per tant, l'algorisme es continua considerant segur. http://sociedad.elpais.com/sociedad/2011/08/17/actualidad/1313532009_850215.html 3 Veure Glossari.


Al principi de començar aquest treball no tenia molt clar què volia fer exactament, però poc a poc em vaig anar centrant en el tema, i vaig anar aprenent tot allò que necessitava per continuar.

El meu propòsit inicial, entendre com funciona l'algorisme AES i els conceptes matemàtics en què es basa, ha estat assolit. També volia, a partir del que he aprés sobre l'AES, programar aquest algorisme, ja que li dóna una dimensió pràctica al meu treball. Tanmateix, com que no tenia el coneixement suficient per fer-ho, no he pogut programar-lo completament. Tot i això, estic molt satisfeta dels resultats que he obtingut.


2.Metodologia

Aquest treball l’he fet amb una doble tutoria. A més de la Glòria Peraita, la meva tutora del treball, que m’ha ajudat en una part més metodològica, he comptat amb l’ajuda d’un tutor extern al centre, en Jordi Quer, degà de la Facultat de Matemàtiques i Estadística de la UPC, que m’ha assessorat en la part més tècnica del treball.

La criptografia és un tema molt ampli que és present en moltes èpoques i pot ser enfocada des de múltiples punts, com puguin ser el seu impacte històric, o com ha propiciat diferents descobriments matemàtics o computacionals, com la invenció del primer ordinador, el Colossus, que va servir per trencar la màquina Enigma. Per això, una de les primeres coses que he hagut de fer ha estat acotar el treball a un determinat aspecte i època. Per fer aquest treball m'he centrat en la criptografia en el moment actual i en l’estudi de l’algorisme d’encriptació AES (Advanced Encryption System) i el seu funcionament.

He utilitzat principalment recursos a internet, ja que hi ha poca bibliografia impresa sobre aquest tema, mentre que a la xarxa s’hi pot trobar molta informació contrastada. Per els apartats teòrics he utilitzat apunts que m'ha subministrat en Jordi Quer. També he participat a un curset d’estiu de programació per aprendre les bases per poder programar l'AES, ja que m'agradaria fer-ho com a part pràctica del treball.

Un entrebanc que m’he trobat a l’hora de plantejar el treball ha estat la falta de coneixement de conceptes matemàtics relacionats amb els sistemes que estudio al treball i la dificultat de trobar explicacions d’aquests conceptes adaptades al meu nivell. He pogut superar aquesta dificultat gràcies a l’ajuda d’en Jordi Quer, que m’ha facilitat informació al meu nivell i m’ha explicat tot allò que no entenia.

També m'ha costat decidir quin tipus de pràctica fer. En Jordi Quer em va proposar d'estudiar la signatura digital, que es basa en la criptografia de clau pública, però al final, i donat que el treball es centra en la criptografia de clau privada i en l'AES, he decidit intentar programar aquest algorisme.


3.Context històric

Des de molt antic alguns col·lectius, ja fos per guerres o per interès, han tingut la necessitat d'ocultar les seves comunicacions a estranys. De fet, tot i que s'han trobat mostres de que els egipcis i mesopotàmics ja utilitzaven algun mètode de xifratge, els primers en explotar aquest recurs varen ser els grecs i els romans, cultures per les quals la guerra era una situació corrent i, per tant, la privacitat de les comunicacions era un element clau. Per a mantenir les seves comunicacions en secret, utilitzaven diferents mètodes de codificació i/o ocultació per als seus missatges.

L’ús de la criptografia arriba al seu màxim esplendor durant les dues guerres mundials, on les comunicacions a llarga distància, sovint per ràdio, eren fàcilment interceptables, i era necessari el seu xifratge. En aquest moment es va crear una gran quantitat d'algorismes i sistemes criptogràfics, que s'anaven renovant a mesura que els anaven trencant. Així, paral·lelament a les dues guerres mundials es va lliurar una guerra oculta entre criptògrafs, que creaven codis cada cop més elaborats, i criptoanalistes, que els intentaven trencar. Això va durar fins que, amb la creació de la màquina Enigma, la guerra entre criptògrafs i criptoanalistes semblava guanyada a favor dels primers. Tot i això, Alan Turing, gràcies als treballs anteriors de Marian Rejewski, aconseguí trencar aquest codi, gràcies a la màquina Bomba.

Poc després del trencament d'Enigma es crea el primer ordinador, el Colossus, cosa que ens introdueix, en últim terme, a l'era digital. Els ordinadors permeten fer moltes operacions molt més ràpid del que abans era concebible. Això, dut a la criptografia, significa que es poden utilitzar codis molt més complexos amb procediments d'encriptament més llargs.

Internet es va crear primer amb objectius militars, i després es va expandir i unir amb altres xarxes que s'havien anat creant arreu dels Estats Units i d'Europa per formar la gran interconnexió de xarxes que avui coneixem. Amb la creació d'Internet, doncs, a principis dels noranta, la criptografia deixa de tenir un caràcter militar, per esdevenir una eina necessària en l’entorn civil i quotidià.

En aquest entorn, on per primera vegada el públic civil pot accedir a un mateix mitjà d’intercanvi de dades, es dóna el cas que hi ha una gran quantitat d'informació circulant pel mateix canal. En aquesta nova xarxa, on la quantitat d'usuaris creix exponencialment en molt poc temps, a la criptografia se li demana un sistema adaptable a un gran nombre d'usuaris que proporcioni una major protecció en la transmissió de dades en un temps d'encriptació molt menor. Ens trobem, per tant, en un entorn per la criptografia molt diferent del que hi havia en èpoques anteriors, i els requisits que se li demanen també han variat molt. Ara la criptografia ha de garantir tres característiques bàsiques: Privacitat, adaptabilitat i agilitat.


Com hem dit, hi ha una gran quantitat d'usuaris a la xarxa, i per tant hi ha molta informació circulant per un mateix canal. Aquesta acumulació d'informació necessita un encriptament que garanteixi la privacitat en transmissió de les dades.

En una era on la informació és compartida per usuaris d'entorns molt diferents és important l'estandardització dels sistemes. Per aquest motiu la criptografia evoluciona en sistemes adaptables al màxim de dispositius i sistemes.

Actualment hi ha una gran exigència del mercat tecnològic de produir dispositius mòbils cada cop més petits i senzills d'utilitzar amb capacitat d'enviar missatges des de qualsevol lloc. A més, les noves tecnologies intenten consumir cada cop menys energia i proporcionar més velocitat de transmissió. Això crea la necessitat de sistemes criptogràfics més àgils, així com més lleugers.


4.Criptografia

La criptografia consisteix en la codificació de textos o altres conjunts de dades de manera que només l’emissor i un receptor autoritzat puguin comprendre’n el significat. Per a mantenir aquestes dades en secret s’utilitzen claus i diferents mètodes de xifratge, com la criptografia de clau privada i la de clau pública.

Un sistema criptogràfic consta de dos elements: l’algorisme d’encriptació, que és la manera en com es codifica el missatge i que pot ser comuna en diverses comunicacions, i la clau, que és el paràmetre concret utilitzat en cada missatge. Per exemple, un dels codis més utilitzats durant l'edat antiga fou el codi cèsar, que consisteix en substituir cada lletra del missatge per la que es troba un nombre determinat de posicions davant seu a l'abecedari.

De: http://acacha.org/mediawiki/upload/b/b8/Criptoborjamedina02.png

En aquest cas, l'algorisme d'encriptació seria "agafar la lletra que es troba n llocs davant de la que correspon", i la clau seria el nombre n de posicions que s'ha de moure la lletra.

Es distingeixen dos tipus de criptografia segons el nombre de claus per usuari i tipus de comunicació: la criptografia de clau pública i la de clau privada.

4.1.Criptografia de clau privada

En la criptografia clàssica s'utilitza el xifratge de clau privada, que consta d’una sola clau compartida per l’emissor i el receptor, i que permet xifrar i desxifrar missatges de manera que només aquells que posseeixen la clau els poden comprendre. Això aporta, a part de seguretat, autenticitat, ja que només aquells que comparteixen la clau poden escriure els missatges en codi.

En criptografia simètrica es poden utilitzar una o dues claus, sempre i quan la funció inversa d'una es pugui trobar fàcilment a partir de l'altra.

De: http://i.technet.microsoft.com/dynimg/IC115427.gif


Els sistemes que utilitzen la criptografia de clau privada o simètrica acostumen a ser sistemes forts, sempre i quan es disposi d'una bona clau.

La criptografia simètrica presenta, però, dos grans inconvenients lligats a la clau. D'una banda, si algú aconsegueix la clau pot enviar o llegir missatges sense que l’emissor o el receptor se n’adonin, cosa que trenca la seguretat del canal i també l’autenticitat del missatge, ja que la clau ja no en garanteix l’autoria. L’altre inconvenient que presenta és que, en algun moment, l’emissor i el receptor s’han d’intercanviar la clau, que és susceptible de ser interceptada i, per tant, descoberta, eliminant-ne la seguretat. Per a evitar això es pot transmetre la clau xifrada amb una altra clau, que tindria els mateixos problemes, cosa que ens duria a un cicle infinit de dependència a altres claus.

En els sistemes de clau privada es necessita una clau o parell de claus per a cada parell d'usuaris, tres si hi ha tres usuaris (un parell per a A i B, un per a B i C, i un per a C i A), sis per a la comunicació de quatre usuaris, etc. En general, per a qualsevol comunicació amb n usuaris es necessiten {n(n-1)/2} claus (n sobre 2) mentre que per a un sistema de clau pública se'n necessiten 2*n (dues per usuari).

En una comunicació entre pocs usuaris, pot sortir a compte utilitzar criptografia de clau privada, però quan el nombre d'usuaris augmenta la criptografia de clau pública és més eficient en quant al nombre de claus necessàries.

1. Nombre de claus necessàries 2. Nombre de claus necessàries per un

per un sistema de clau privada sistema de clau pública

4.2.Criptografia de clau pública

Aquesta manera revolucionària de xifrar informació fou concebuda el 1874 per William Stanley Jevons, qui estudià les funcions unidireccionals i proposà el seu ús en la criptografia; i fou posada en pràctica a partir del 1976 gràcies al


treball de Whitfield Diffie i Martin Hellman, presentat en un article científic titulat “New directions in cryptography”4.

La criptografia de clau pública o asimètrica constitueix una revolució en el món de l’intercanvi d’informació perquè no requereix que emissor i receptor es trobin i intercanviïn claus, i perquè no hi ha perill que un tercer pugui interceptar i modificar el missatge. Això passa perquè s’utilitzen claus diferents per xifrar i desxifrar i perquè l’únic que té la clau per desxifrar és el receptor autoritzat.

D’aquesta manera, la criptografia de clau pública resol els dos grans problemes de la criptografia de clau privada: d’una banda, no es pot interceptar la clau en ser intercanviada, ja que no es dóna intercanvi de claus; i de l’altra, no es compromet l’autenticitat del missatge, ja que, com s’explica més endavant, gràcies a la signatura digital es pot conèixer amb seguretat la identitat de l’autor d’un missatge.

Un dels algorismes d'encriptament de clau pública més utilitzats avui dia és l'anomenat RSA, que es diu així en honor dels seus tres creadors: Ron Rivest, Adi Shamir i Leonard Adleman.

4.2.1.Funcionament:

Aquest mètode per xifrar consisteix en una clau pública, a l’abast de tothom, i una clau privada, inversa de la clau pública i pràcticament impossible d’obtenir a partir d’aquesta, que només posseeix l’emissor i que serveix per descodificar tot allò xifrat amb la clau pública. Aquestes dues claus estan relacionades entre sí matemàticament, però la clau privada és gairebé impossible d’obtenir a partir de l’altra.

La clau pública és distribuïda de manera que qui vulgui enviar un missatge a qualsevol usuari l’ha de xifrar amb la seva clau pública. Després, el receptor desxifrarà el missatge amb la seva clau privada, inversa de la pública que s’ha utilitzat per xifrar el missatge. Això aporta confidencialitat a la comunicació, ja que ningú, a part del receptor a qui s’envia el missatge té la capacitat de desxifrar-lo i, per tant, de comprendre’l.

4 Diffie, Whitfield; Hellman, Martin E. New directions in cryptography (1976). Dins: IEEE

Transactions on Information Theory (Vol. IT-22, No.6, pàg. 644-654)


De: http://acacha.org/mediawiki/upload/thumb/8/85/Davidginovartcodicesar7.png/500px-

Davidginovartcodicesar7.png

La fortalesa dels sistemes criptogràfics de clau pública es basa en la gran quantitat de temps i recursos que es necessita per trobar els factors primers d'un nombre gran, i de la velocitat amb que aquest es pot obtenir multiplicant nombres primers. Generalment la clau pública s'obté a partir de la multiplicació de dos nombres primers grans, que formen la clau privada. Per trencar el codi s'han d'obtenir els dos factors primers a partir del seu producte, que acostuma a tenir una enorme quantitat de xifres.

Això les màquines només ho poden fer comprovant un a un tots els nombres anteriors a aquest. Tot i que hi ha maneres d'accelerar el procés, encara no hi ha màquines prou potents per trencar aquests codis, i en el moment en que n'hi pogués haver, simplement es podrien escollir factors primers més llargs.

Per aquest motiu, no es pot obtenir la clau privada d'un usuari a partir de la seva clau pública i/o d'un missatge encriptat amb aquesta.

4.2.2.Avantatges i desavantatges:

La criptografia de clau pública presenta un gran avantatge, i és que el nombre de claus que es requereixen per a una comunicació amb n usuaris és molt menor. Així, per a una comunicació amb clau privada es necessita una clau per a cada parella d'usuaris, ja que si s'utilitzés un nombre menor s'estaria comprometent la privacitat de les comunicacions. Per tant, per a n usuaris, es necessiten tantes claus com combinacions de n usuaris agafats de dos en dos (és a dir: n*(n-1)/2); mentre que la clau pública només requerirà 2n claus (la pública i la privada de cada usuari).

La criptografia de clau pública, però, presenta un gran inconvenient, i és que és considerablement més lenta que la de clau privada. Per aquest motiu sovint es combinen ambdós mètodes i la criptografia de clau pública s'utilitza només per intercanviar les claus. Aquesta combinació es coneix amb el nom de


criptografia híbrida5, i s'utilitza, per exemple, en servidors web on l'usuari s'ha d'identificar mitjançant un usuari i contrasenya, llavors a l’URL de la pàgina hi posa, en lloc del comú http, https6.

4.3.Signatura digital

Com hem vist a l’apartat anterior, la criptografia de clau pública aporta confidencialitat a les comunicacions, però no autenticitat, ja que no es pot saber qui t’ha enviat un missatge només per la clau amb què està codificat.

Amb l’objectiu d’aportar l’autenticitat necessària es crea el concepte de signatura digital, també basat en la criptografia asimètrica. La signatura digital consisteix a xifrar, amb la clau privada de l’emissor, un resum del contingut del missatge i afegir-lo al missatge abans de codificar-ho amb la clau pública del receptor. D’aquesta manera el receptor pot saber, desxifrant la signatura digital de l’emissor i comparant-la amb el missatge, si l’emissor ha escrit realment el missatge, ja que, com que la signatura ha estat xifrada amb la clau privada de l’emissor, només pot ser desxifrada per la seva funció inversa, és a dir, la seva clau pública.

En comptes d’un resum del text, s’acostuma a utilitzar una funció hash per fer la signatura digital7. D’aquesta manera, es garanteix tant l’autoria com la integritat del missatge, ja que per comprovar que aquest no ha estat modificat, només cal fer la funció hash del missatge rebut i comparar-la amb la que venia inclosa en el missatge. Si els resultats coincideixen significa que el missatge no ha estat alterat.

De: http://img.genbetadev.com/2013/01/375px-Cryptographic_Hash_Function.svg.png

5 Veure glossari.

6 Http: hipertext transfer protocol. Https: hipertext transfer protocol secure.

7 Veure glossari.


En ser gairebé impossible que dos missatges diferents tinguin funcions hash idèntiques, són una bona mesura per comprovar la integritat d’un missatge, i com que tampoc no gasten molta memòria per executar-se, són un mètode molt útil i utilitzat en les comunicacions d’avui en dia.

Així, la signatura digital complementa la criptografia asimètrica i li aporta confidencialitat i la seguretat de que el missatge no ha estat alterat.


5.Conceptes matemàtics necessaris per comprendre l' AES

L'AES utilitza alguns conceptes matemàtics que no s'imparteixen a l'educació secundària. Per tal de poder garantir una bona comprensió de l'algorisme estudiat els explico en aquest apartat del treball. Aquests conceptes no són exclusius de l'algorisme AES, sinó que s'utilitzen en molts altres aspectes de les matemàtiques i de la informàtica. Per això considero útil donar-los a conèixer.

5.1.Congruències Dos nombres (a i b) són congruents entre ells mòdul un altre nombre (m) quan els residus obtinguts dividint cadascun d'aquests nombres pel mòdul són iguals entre ells. Dit d'una altra manera, donats a, b ∈ Z i m ∈ N, llavors a i b són congruents si:

a mod (m) = b mod (m) o b–a = K·m (on K ∈ Z)

La congruència entre dos nombres es representa a ≡ b (mod (m)) i es llegeix "a congruent amb b mòdul m".

"Mod" és l'operació mòdul, que és la resta de la divisió euclidiana de dos nombres.

r = a mod (m) <=> a = m·q + r

Per exemple, 27 i 12 són congruents mòdul 5, ja que en dividir-los per 5 els dos donen residu igual a 2.

27=5*5+2 12=5*2+2

27≡2 (mod(5)) 12≡2 (mod(5)) 27≡12(mod(5))

5.2.Cossos

Un cos és una estructura algebraica en la qual es poden realitzar les operacions de suma i multiplicació i en el qual es compleixen les següents propietats:

1. Per tot a i b ∈ F, a+b i a*b pertanyen a F.

2. La suma i la multiplicació compleixen la propietat associativa:

Per tot a, b i c ∈ F, a+(b+c) = (a+b)+c i a*(b*c)=(a*b)*c.

3. La suma i la multiplicació compleixen la propietat commutativa:


Per tot a i b ∈ F, a+b=b+a i a*b=b*a.

4. La multiplicació compleix la propietat distributiva respecte de la suma:

Per tot a, b i c ∈ F, a*(b+c)=(a*b)+(a*c).

5. Existeix un element neutre per la suma:

Existeix un element 0 ∈ F tal que per tot a ∈ F, a+0=a.

6. Existeix un element neutre per la multiplicació:

Existeix un element 1∈ F tal que per tot a ∈ F, a*1=a.

7. Existeix un element invers per la suma:

Per tot a ∈ F, existeix un element –a ∈ F tal que a+(-a)=0.

8. Existeix un element invers per la multiplicació:

Per tot a≠0 ∈ F, existeix un element a-1∈ F tal que a*a-1=1.

A partir d'aquestes propietats es poden fer les operacions bàsiques de suma i multiplicació i, utilitzant els inversos de la suma i la multiplicació, les operacions de resta i divisió.

Un exemple de cos són els nombres racionals (Q), que compleixen les següents propietats i que són infinits, i que tenen l'element invers de la suma i la multiplicació per tots els seus elements. En canvi, els nombres naturals no ho podrien ser, ja que, en ser tots positius, no tenen l'element invers de la suma. Tampoc ho podrien ser els enters, ja que no tenen invers de la multiplicació.

5.2.1.Cossos finits

Els cossos finits són aquells que tenen un nombre finit d’elements. Quan s'utilitzen cossos finits moltes vegades es fa servir l'abreviatura GF(pn), que són les sigles de Galois Field (cos de Galois), en honor de Évariste Galois8.

El nombre d’elements que té un cos finit s’anomena l’ordre, i es designa com a q. L’ordre q d’un cos finit és igual a un nombre primer positiu p elevat a un nombre natural n. Per exemple: un cos finit d'ordre 8 s'anomenarà GF(23).

En un cos finit, com en qualsevol altre cos, es pot operar amb normalitat amb les operacions de suma i multiplicació, i, trobant els respectius inversos, de resta i multiplicació. Quan en una operació el nombre resultant no es troba dins 8 Évariste Galois (1811-1832) matemàtic francès fundador de la teoria dels cossos finits


dels elements del cos, es busca un nombre congruent amb aquest mòdul l’ordre del cos, ja que, com hem vist a la primera propietat dels cossos, la suma i el producte de dos elements d'un cos ha de pertànyer a aquest cos.

També es poden utilitzar cossos finits l'ordre dels quals és un polinomi. En aquest cas s'operarà amb normalitat, amb l'única diferència que els elements del cos seran polinomis en comptes de nombres. Per fer les operacions de mòdul en aquests cossos s'utilitza un polinomi primer de grau igual al de l'ordre del cos. D'aquesta manera, el residu serà sempre de grau menor al mòdul i, per tant es trobarà dins del cos.

En l'AES s'utilitzen els cossos finits per operar amb cadenes de bits, que es tracten com a polinomis dins del cos finit GF(23). Quan el producte d'alguna operació amb elements del cos no es troba dins del cos es busca un nombre congruent amb aquest mòdul el polinomi x8 + x4 + x3 + x + 1. Vegem un exemple de suma amb polinomis en el cos finit GF(23):

(x6 + x4 + x2 + x + 1) + (x7 + x + 1) = x7 + x6 + x4 + x2.

Cal fixar-se en que quan hi ha dos valors del mateix grau que es sumen, queden anul·lats. Això passa perquè s'està tractant amb un cos finit en base dos, i que per tant només opera amb valors d'uns i zeros. Per tant, 2x (mod 2) = 0x, i per tant no s'escriu en el resultat.

Vegem ara un exemple de multiplicació amb polinomis en el cos finit GF(23).

(x6 + x4 + x2 + x + 1)(x7 + x + 1) = x13 + x11 + x9 + x8 + x7 + x7 + x5 + x3 + x2 + x + + x6 + x4 + x2 + x + 1 =

= x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1

A continuació es fa la operació mòdul amb el producte obtingut:

x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1 (mod x8 + x4 + x3 + x + 1) = x7 + x6 + 1.

Com es pot veure, la multiplicació és fa com una multiplicació normal entre polinomis. l'única diferència que hi ha és que el resultat es redueix mitjançant l'operació mòdul per tal de que existeixi dins del cos.

5.5.Algorisme d’Euclides extès i identitat de Bézou t

L'algorisme d'Euclides serveix per trobar el màxim comú divisor de dos nombres enters a i b. Consisteix en:

→ Dividir el nombre major entre el menor. La divisió euclidiana compleix que a=b·q+r, on q és el quocient de la divisió i r n'és el residu.


→ Si la divisió és exacta, el divisor és el màxim comú divisor. Si hi ha residu, el divisor passa a ser el dividend i el residu passa a ser el divisor i es repeteix la divisió.

Per exemple, pels dos enters 11 i 17, funcionaria de la següent manera:

42=24·1+18

24=18·1+6

18=6·3+0

Amb la qual cosa s'obté que el seu màxim comú divisor és 6.

La identitat de Bézout enuncia que per tot a i b enters existeixen x i y enters tals que es compleix la igualtat següent, on a i b són els enters del principi i d el seu màxim comú divisor.

a·x+b·y=d

Els nombres x i y es poden trobar amb l'algorisme d'Euclides extès. Per calcular-los es disposen els números en una graella com aquesta i es calcula de la de la següent manera:

x 1 0 1=1-0·1 -1=0-1·1

y 0 1 -1=0-1·1 2=1-1·(-1)

quocient (q) 1=42/24 1=24/18 3=18/6

residu (r) 42 24 18=42-24·1 6=24-18·1 0=18-6·3

Veiem que la igualtat es compleix, ja que:

a·x+b·y=d

42·(-1)+24·2=6

Si això es prova amb nombres que siguin primers entre ells es troba el seu invers multiplicatiu, ja que el seu màxim comú divisor és 1.

Aquesta particularitat s'aplica en l'AES per trobar l'invers multiplicatiu de dos polinomis.


5.4.Funcions lògiques: XOR

XOR (exclusive or) és una funció lògica que és veritat si només un dels operands és veritat, si els dos són iguals no és veritat. Per tant, donarà els següents resultats en operar:

INPUT OUTPUT A B A XOR B 0 0 0 0 1 1 1 0 1 1 1 0


6.AES

L'AES (o Advanced Encryption Standard) és un algorisme d’encriptació de clau privada que s’utilitza per assegurar la majoria de processos de transferència de dades a la xarxa com transaccions comercials online o comunicacions inalàmbriques. Els seus dissenyadors són dos criptòlegs belgues, Joan Daemen i Vincent Rijmen, tots dos estudiants de la Katholieke Universiteit Leuven i li van donar el nom de Rijndael. L'algorisme original permetia qualsevol llargada de blocs i de claus d'entre 128 i 256 bits sempre i quan tinguessin un nombre de bits múltiple de 32. Va ser dissenyat l'any 1997, arrel de la crida que va fer el NIST (National Institute of Standards and Technology) per trobar un substitut al DES (Data Encryption Standard), el qual havia estat trencat el juny d'aquell any. A partir d'una primera selecció feta l'agost del 1998, el Rijndael va ser nominat junt amb 14 algorismes més, i el novembre del 2001, després d'un llarg procés de selecció, el Rijndael va ser escollit per ser l'AES. L'AES presenta alguns canvis respecte del Rijndael, ja que té una llargada de bloc fixa de 128 bits i una mida de clau que pot variar entre 128, 196 i 256 bits, a diferència del Rijndael, que permet moltes altres llargades diferents. 6.1.Funcionament de l’AES Abans de començar el procés, el missatge es transcriu a codi ASCII (veure annex) i es divideix en blocs de 128 bits. En el cas que el nombre de bits missatge no fos múltiple de 128, es completa l'últim bloc amb bits aleatoris que s'eliminen en acabar el desxifrat. El funcionament de l’AES es basa en quatre transformacions que es van repetint en un seguit de rondes: el SubBytes, el ShiftRows, el MixColumns i l’AddRoundKey. Abans de començar el xifrat, el text pla es distribueix en blocs de 128 bits, en una matriu de 4x4 caselles amb un byte a cada una anomenada estat. Les operacions s’efectuen sobre l’estat. 6.1.1.SubBytes: En aquest pas es substitueix cada byte de l’estat per un de diferent a partir d’una S-box o taula de substitució. Aquest pas serveix per dissimular la relació entre el text pla i el xifrat.


Per obtenir els valors de la S-box utilitzada en l'AES s'han de fer dos passos: obtenir l'invers multiplicatiu del nombre donat i aplicar-hi una transformació afí. Per fer aquestes operacions amb l'estat es tracta cada byte com un polinomi de grau 8 dins del cos finit GF(23). Per exemple: Prenem el polinomi x6 + x4 + x + 1, i en trobem l'invers multiplicatiu mitjançant la identitat de Bézout. Veiem que l’invers multiplicatiu del polinomi és x7 + x6 + x3 + x. A continuació s'hi aplica una transformació afí, que consisteix a multiplicar el polinomi obtingut (invers del primer) per una matriu i després aplicar-hi l'operació XOR amb un altre vector. A continuació veiem com s'operaria utilitzant l'exemple anterior: El polinomi es llegiria, en base binària, com a 11001010 i s'operaria en la següent matriu.

Donant com a resultat: x7 + x3 + x2 + x, que es llegeix en numeració binària com 10001110. Tanmateix, a l'hora de programar s'acostuma a escriure una taula de substitució amb els valors corresponents a cada nombre ja calculats. 6.1.2.ShiftRows: En el ShiftRows es desplacen els bytes de cada fila un nombre cíclic de vegades. En l’AES la primera fila es deixa invariable, a la segona es desplacen tots els bytes una posició cap a l’esquerra, a la tercera es desplacen dos posicions, i a la quarta tres. En les extensions del bloc de 196 i 256 bits es fa el mateix, movent cada fila n un nombre n-1 de posicions a l’esquerra. La importància d’aquest pas és fer que les columnes de l’estat no siguin quatre blocs independents en el xifrat.


A la següent imatge veiem la transformació de l'estat en el pas ShiftRows:

De: http://students.mimuw.edu.pl/~mr214564/AESmr214564/shiftrows.png

Aquest pas, com el següent, serveix per trencar la linearitat del missatge. Dit d'una altra manera, serveix perquè no es pugui tractar cada fila o cada columna com un bloc a part en el conjunt del xifrat. Això, a efectes pràctics, fa que sigui molt més difícil trencar el codi. 6.1.3.MixColumns: En el MixColumns cada columna de l'estat és tractada com un polinomi dins del cos GF(28) i és multiplicada mòdul x4+1 per la següent matriu:

Per fer-ho, s'escriu cada byte en numeració hexadecimal i s'opera amb la matriu de la següent manera:

Després tornem a passar els números a base binària i continuem amb el xifratge.


6.1.4.AddRoundKey: En aquest últim pas s’afegeix una subclau, també disposada en una matriu de 4x4, a l’estat. Això es fa combinant cada byte de la clau amb el byte corresponent de l’estat mitjançant l’operació XOR. 6.1.5.Claus de ronda: La clau inicial també pateix un seguit de modificacions que fan més difícil desencriptar el missatge. A cada ronda, a partir de la segona, la clau que s'afegeix al pas AddRoundKey s'obté de l'original a partir d'un seguit d'operacions. Com hem dit al principi, el nombre de rondes de l'AES depèn de la llargada de la clau. Això passa perquè a cada ronda s'obté la clau de ronda a partir d'una columna de bytes de la clau. Per tant, depenent de la llargada de la clau el procés d'encriptat tindrà més o menys rondes. 6.1.6.Rondes: Les transformacions anteriors s’apliquen a l’estat en un seguit de rondes, que segueixen el següent esquema (foto). A la primera ronda només s’hi aplica la clau de xifrat. A les nou següents s’hi aplica, en cadascuna i en aquest ordre, el SubBytes, el ShiftRows, el MixColumns i l’AddRoundKey, amb una clau de ronda diferent cada vegada. A l’última ronda s’hi apliquen totes les operacions anteriors excepte el MixColumns, de cara a simplificar el procés de desxifrat. Després d’aquests passos s’obté el text xifrat.

De: http://www.formaestudio.com/rijndaelinspector/archivos/Rijndael_Animation_v4_eng.swf


6.2.Desencriptat de l’AES

Per desencriptar un text xifrat (òbviament sabent-ne la clau) s’han de seguir els passos fets durant el procés d’encriptat i fer-ne la funció inversa, per tal de recuperar el text pla9.

9 Veure glossari


7.Part pràctica

Com a part practica del treball he provat de programar en llenguatge C++ l’algorisme AES, que com he explicat abans, és un xifratge per blocs que divideix el missatge en blocs de 128 bits i utilitza una clau de 128, 196 o 256 bits. Jo he escrit el programa utilitzant una clau de 128 bits de cara a simplificar el procés.

He escrit dos programes. Un d'ells és el pas ShiftRows de l'AES, en el qual s'introdueixen per ordre 16 enters amb base decimal corresponents a cadascuna de les caselles de l'estat i el programa retorna aquests setze enters en l'ordre en que acaben després de passar per aquesta transformació.

L'altre programa que he escrit és un esquema de l'AES. No he pogut escriure'n l'algorisme complet perquè em falta formació en programació. Per tant, n'he programat només un esquema. No hi ha escrits cadascun dels passos, sinó només l'estructura principal, però una vegada escrits, aquests tenen una fàcil implementació al programa.


8.Conclusions

Quan em vaig plantejar el treball de recerca volia aprendre més sobre la criptografia i sobre com funciona avui en dia. El meu propòsit inicial, programar l'AES, estava fora del meu abast i no l'he pogut acomplir. Malgrat això, estic satisfeta dels resultats que he obtingut, perquè durant la realització del treball he après moltes coses, i n'he pogut consolidar moltes altres.

D'una banda m'enfrontava a un tema que, tot i que sempre m'ha interessat, no havia tractat mai amb profunditat. Per mi ha estat molt interessat de fer aquest treball per veure com influeix la criptografia en el nostre dia a dia. D'altra banda em vaig proposar programar l'AES, i això requeria que aprengués a programar ja que, tot i que en sabia una mica, no tenia ni de bon tros els coneixements necessaris per fer-ho.

El meu propòsit inicial de programar l'AES estava fora del meu abast i no l'he pogut acomplir, però tot i així he après un munt de programació, i he pogut treballar en un programa utilitzat en l'entorn real de la xarxa, no pas un prototipus utilitzat sols en contextos educatius. Això (motiva molt) Durant el redactat del treball he hagut de centrar-me en l'especificitat del tema, el que m'ha fet deixar de banda altres temes relacionats en els que m'hagués agradat d'aprofundir. D'una banda m'hagués agradat aprendre més sobre la criptografia de clau pública, i també m'hagués agradat acabar de programar l'AES, cosa que espero poder fer en un futur proper.

En tot cas, fer aquest treball de recerca tan dilatat en el temps, amb tot el que implica d'esforç personal, de buscar recursos i recolzaments externs i d’auto aprenentatge, m’ha fet organitzar-me d’una manera completament diferent a com ho he fet en treballs anteriors. El treball de recerca és un treball que fem de forma relativament autònoma. Un dels objectius d'aquest treball és precisament que puguem fer un projecte d’una certa magnitud per nosaltres mateixos, buscant nosaltres els recursos i l’ajuda necessària i decidint quina informació o fonts considerem fiables, i com ens organitzem el temps i els recursos. Crec que amb aquest treball he acomplert tots aquests objectius.


9.Agraïments

Aquest treball no hagués estat possible sense l'ajuda dels meus tutors: la Glòria Peraita, la meva tutora del treball de recerca, que és professora de matemàtiques a l'IES Montserrat, i que m'ha guiat al llarg de tot el temps que he estat fent aquest treball, i en Jordi Quer, professor de la Facultat de Matemàtiques i Estadística de la UPC, que sense coneixe'ns prèviament m'ha assessorat des d'un principi i m'ha resolt tots els dubtes que he tingut.

Vull agrair als meus pares el seu suport constant i la seva ajuda en els mil petits dubtes que he tingut en aquest temps.

També he de donar les gràcies a tots els professors que he tingut, que m'han fet descobrir i estimar les matemàtiques i en especial als professors de les sessions de preparació de les Olimpíades Matemàtiques i del Cangur10. Ells m'han ensenyat a no rendir-me quan no entenc alguna cosa i a abordar els problemes des de mil angles diferents abans de donar-me per vençuda. En especial vull agrair al senyor Grané que em presentés a en Jaume Soler, que va ajudar-me a triar el tema del treball i em va facilitar el contacte d’en Jordi Quer.

Per últim, vull expressar el meu agraïment a en Salvador Roura, en Jordi Petit i els altres professors del curset de programació d'estiu de la UPC, on he aprés tot el que sé de programació i on m'ho he passat molt bé.

10

Aquestes sessions són una activitat voluntària i gratuïta que ofereix la Societat de Matemàtiques de

l'IEC a diferents centres educatius


10.Bibliografia

- Funció resum . Dins: Wikipedia. <http://ca.wikipedia.org/wiki/Funci%C3%B3_resum> [Consulta 19-6-2013]

-Criptografia . Dins: Wikipedia. <http://ca.wikipedia.org/wiki/Categoria:Criptografia> [Consulta 23-7-2013]

- NIST. Advanced Encryption Standard (AES) (2001). Dins: Federal Information Processing Standards Publications: <http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf> [Consulta 16-6-2013]

- RSA. Dins: Wikipedia: <http://ca.wikipedia.org/wiki/RSA>[Consulta 14-6-2013]

- Field . Dins: Planetmath: <http://planetmath.org/node/30355> [Consulta 19-7-2013]

- Finite field . Dins: Planetmath: <http://planetmath.org/finitefield> [Consulta 21-7-2013]

- Teoría de números elemental: Congruencias (2006). Dins: Gaussianos. <http://gaussianos.com/teoria-de-numeros-elemental-congruencias/> [Consulta 17-6-13]

- Zabala, Enrique. Rijndael cipher . <http://www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf> [Consulta 18-6-2013]

- Cripto Serie: Advanced Encryption Standard (2009). Dins: DragonJAR. <http://comunidad.dragonjar.org/f156/cripto-serie-advanced-encryption-standard-7878/> [Consulta 18-6-2013]

- Gómez, Joan. Matemáticos, espías y piratas informáticos (2011). RBA ("El mundo es matemático")


Annex I: ShiftRows:

# include <iostream> # include <vector> using namespace std; int main () { vector <int> state (16); int a=0; while (a<=15) { int n; cin >> n; state [a] = n; ++a; } vector <int> v (16); int i=0; int j=0; int f=0; int y; while (j<16) { int u=0; while (u<4) { y = i%4+f*4; v [j] = state [y]; cout << v [j] << endl; ++i; ++j; ++u; } ++f; ++i; } getchar(); getchar(); }


Annex II: AES:

#include <iostream> #include <vector> using namespace std; int ByteSub (vector <int> State) { return (State); } int ShiftRows (vector <int> State) { return (State); } int MixColumns (vector <int> State) { return (State); } int AddRoundKey (vector <int> State, vector <int> RoundKey) { return (State); } int RoundKey (vector <int> Key) { return (Key); } int main () { vector <int> State (16,0); int i=0; while (i<16) { cin >> State [i]; ++i; } vector <int> Key (16,0); int j=0; while (j<16) { cin >> Key [j]; ++j; } int State=ByteSub (State); int State=AddRoundKey (State, Key); int i=1;


while (i<=9) { int Key=RoundKey (Key); int State=ByteSub (State); int State=ShiftRows (State); int State=MixColumns (State); int State=AddRoundKey (State, Key); ++i; } int Key=RoundKey (Key); int State=ByteSub (State); int State=ShiftRows (State); int State=AddRoundKey (State, Key); int n=0; while (n<=15) { cout << State [n] << endl; ++n; } }


Annex II: El llenguatge ASCII

El llenguatge ASCII (American Standard Code for Information Interchange) és un codi per l’intercanvi d’informació que assigna valors numèrics als caràcters (lletres, números i signes de puntuació) que utilitzem per escriure. S’utilitza sobretot a l’àmbit digital perquè permet traduir a bits i bytes un text escrit, cosa que en últim terme ens permet comunicar-nos amb i a través de les màquines. A continuació tenim una taula on es pot veure la representació binària i hexadecimal d’alguns caràcters dels que utilitzem normalment.

Binari Hex Representació 0101 0101 55 U

0010 0000 20 espai ( ) 0101 0110 56 V

0011 0000 30 0 0101 0111 57 W

0011 0001 31 1 0101 1000 58 X

0011 0010 32 2 0101 1001 59 Y

0011 0011 33 3 0101 1010 5A Z

0011 0100 34 4 0110 0001 61 a

0011 0101 35 5 0110 0010 62 b

0011 0110 36 6 0110 0011 63 c

0011 0111 37 7 0110 0100 64 d

0011 1000 38 8 0110 0101 65 e

0011 1001 39 9 0110 0110 66 f

0100 0001 41 A 0110 0111 67 g

0100 0010 42 B 0110 1000 68 h

0100 0011 43 C 0110 1001 69 i

0100 0100 44 D 0110 1010 6A j

0100 0101 45 E 0110 1011 6B k

0100 0110 46 F 0110 1100 6C l

0100 0111 47 G 0110 1101 6D m

0100 1000 48 H 0110 1110 6I n

0100 1001 49 I 0110 1111 6F o

0100 1010 4A J 0111 0000 70 p

0100 1011 4B K 0111 0001 71 q

0100 1100 4C L 0111 0010 72 r

0100 1101 4D M 0111 0011 73 s

0100 1110 4I N 0111 0100 74 t

0100 1111 4F O 0111 0101 75 u

0101 0000 50 P 0111 0110 76 v

0101 0001 51 Q 0111 0111 77 w

0101 0010 52 R 0111 1000 78 x

0101 0011 53 S 0111 1001 79 y

0101 0100 54 T 0111 1010 7A z


Annex IV: Glossari:

• Atac per força bruta (p. 4): és un tipus d’atac que intenta trobar la clau d'un determinat criptosistema. Aquest atac consisteix en intentar trobar la clau provant totes les seves possibilitats. Acostuma a ser un mètode molt lent, i s’utilitza per mesurar l’efectivitat d’altres tipus d'atac.

• Criptografia Híbrida (p. 11): és un mètode de xifratge que utilitza tant el xifrat simètric com l’asimètric. Consisteix en intercanviar una clau privada mitjançant el xifratge asimètric i després utilitzar aquesta clau privada per a l’intercanvi de la resta de missatges en xifratge simètric. Aquest mètode s’utilitza perquè el xifrat asimètric és molt lent i no és pràctic en una comunicació.

• Funció hash (p. 12): Una funció hash és una funció matemàtica que dóna com a resultat, a partir d’un fragment d’informació de llargada variable, un bloc de mida fix amb un conjunt de xifres i lletres corresponents al fragment original. Les funcions hash són unidireccionals, és a dir, no es pot obtenir el missatge original a partir de la seva funció hash; i donen resultats completament diferents si el missatge ha sofert la més mínima variació, com veiem a la següent imatge.

De: http://en.wikipedia.org/wiki/Cryptographic_hash_function

Aquestes funcions s'utilitzen per garantir la integritat d'un missatge o la seva autoria, per exemple en la signatura digital.

• Text pla (p. 20): El text pla en criptografia és aquell que no està encriptat, i que, per tant, pot ser llegit. Encara que s'anomeni text pla no ha de per què ser un text, pot ser una imatge o un so o qualsevol altra dada.


• Trencar (p. 4): Es considera que un codi ha estat trencat quan es troba un mètode d'atac que en troba la clau o en desxifra el missatge en un temps menor del que es necessitaria per fer-ho mitjançant un atac per força bruta. Tot i així, i donada la gran quantitat de temps que es necessita per trencar els codis actuals, un criptosistema no es considera trencat a no ser que realment el temps necessari per trencar un codi sigui realment petit (menys de deu anys, per exemple).


Annex V: CD

A continuació afegeixo un CD amb l'aplicatiu del programa ShiftRows i les instruccions per executar-lo.

Date post:	12-Mar-2016
Category:	Documents
Upload:	biblioteca-institut-montserrat
View:	226 times
Download:	8 times

Estudi de l'algorisme d'encriptació AES i del seu funcionament

Documents