Capítol 1

Introducció a la criptografia

La criptografia és la ciència que estudia l'escriptura de secrets, amb l'objectiu d'ocultar el missatge que s'escriu. Etimològicament, la paraula prové del grec i sorgeix de la unió de dos conceptes: kryptós, que vol dir secret i graphein, que vol dir escriptura. Els orígens de l'escriptura secreta es remunten a fa més de 4000 anys, però en aquells moments la criptografia es trobava lluny de considerar-se una ciència. A mig camí entre art i joc d'enigmes, civilitzacions com l'antic Egipte van desenvolupar els primers escrits on es transformava el missatge original. Es considera però que la criptografia com a ciència no va començar a desenvolupar-se fins a mitjans del segle XX, amb les contribucions realitzades per Claude E. Shannon.

La criptoànalisi és la ciència que se centra en trencar les tècniques que desenvolupa la criptografia, ja sigui per a descobrir el text amagat darrere un text xifrat o bé per a demostrar les febleses d'un determinat esquema criptogràfic. Així doncs, la criptoanàlisi és indispensable per a l'avenç de la criptografia, ja que s'encarrega d'avaluar la seguretat dels criptosistemes que aquesta desenvolupa. Tot i que el mot criptoanàlisi és bastant recent, tenim constància d'una criptoanàlisis realitzada al segle IX per un matemàtic àrab, Al-Kindi.

El terme general criptologia es fa servir per englobar tant criptografia com criptoanàlisi.

En aquest llibre, ens centrarem en descriure les tècniques i algorismes que es fan servir per ocultar informació, és a dir, en la criptografia. Tot i així, en aquest capítol farem una petita introducció a la criptoanàlisi, per tal d'oferir unes nocions bàsiques dels models amb els quals s'avalua habitualment la seguretat dels esquemes criptogràfics.

En aquest capítol es presenten, d'una banda, els fonaments de la criptografia i, d'altra banda, es realitza un repàs històric de la criptografia premoderna. Pel que fa als fonaments de la criptografia, descriurem els conceptes clau d'aquesta ciència, que farem servir al llarg del llibre per anar presentant les diferents tècniques que es fan servir en criptografia. En relació amb el repàs històric, veurem com va sorgir la criptografia i quines tècniques es feien servir des dels seus orígens fins a l'inici de la criptografia moderna. La resta del llibre se centrarà precisament en descriure diversos aspectes de la criptografia moderna que, com veurem, ha evolucionat molt des de les seves arrels.

Capítol 2

Fonaments matemàtics

La criptografia és una disciplina amb un fort contingut matemàtic per diferents motius. Per una banda, la matemàtica permet mesurar de forma precisa la quantitat d'informació que conté un missatge i, per tant, també pot mesurar si quan el xifrem la quantitat d'informació que revela és menor o no en revela cap, de manera que ens dóna una mesura de la qualitat del sistema de xifrat que estem utilitzant.

D'altra banda, l'explicitació de les funcions de xifrat i desxifrat de les quals hem parlat en l'anterior capítol sovint es realitza utilitzant funcions i expressions matemàtiques. Per aquest motiu, tenir uns bons coneixements de matemàtiques és fonamental per poder entedre el correcte funcionament de la criptografia.

En aquest capítol es proporcionen conceptes bàsics d'aritmètica modular així com algunes propietats dels nombres primers, necessaris en els criptosistemes de clau pública. D'altra banda, tal i com veurem al llarg d'aquesta llibre, els criptosistemes de clau pública així com algunes funcions que s'utilitzen en diferents protocols criptogràfics, basen la seva seguretat en problemes matemàtics difícils de resoldre. És per això que per entendre el grau de seguretat d'aquests sistemes és important comprendre quins són els problemes matemàtics que hi ha al darrere i quina dificultat té la seva resolució. En aquest capítol s'enuncien els problemes matemàtics més utilitzats en criptografia i se'n discuteix la seva complexitat.

Capítol 3

Ja hem vist en anteriors capítols que un criptosistema incondicionalment segur necessita tants bits de clau com bits de text a xifrar. El xifratge de Vernam és el criptosistema que aconsegueix aquesta seguretat incondicional, però el preu que en paga és la ineficiència del xifratge. Aquesta ineficiència recau justament en el fet que la clau ha de tenir la mateixa longitud del text a xifrar. Això comporta que la longitud de les claus sigui molt gran i, per tant, sigui més difícil guardar-les en secret. A més, es dóna la paradoxa que si tenim un canal segur per intercanviar les claus, aleshores també podem utilitzar-lo per intercanviar els missatges, ja que tenen la mateixa longitud.

Les xifres de flux sorgeixen com una aproximació optimitzada al xifratge de Vernam. La idea és construir una clau suficientment llarga, com a mínim de la longitud del missatge, a partir d'una clau inicial curta. Això s'aconsegueix utilitzant el que s'anomena un generador pseudoaleatori. Aquest generador expandeix una clau petita, anomenada llavor, obtenint-ne una de molt més llarga. L'operació d'expansió cal que tingui certes característiques ja que la seqüència que en resultarà és la que s'utilitzarà per xifrar el text en clar. Caldrà doncs, veure quines propietats hauran de complir les esmentades seqüències i estudiar quin tipus de generadors hi ha per obtenir-les.

Les xifres de flux són xifres de clau compartida ja que la llavor (que es fa servir per obtenir la seqüència xifrant) és utilitzada tant per a xifrar com per a desxifrar, i és per tant compartida entre l'emissor i el receptor.

Com veurem en aquest capítol, el xifrat de flux utilitza una clau diferent per cada bit d'informació. Aquesta clau depèn de l'estat inicial del generador, però també de l'estat del generador en el moment de xifrar un bit concret. Per tant, dos bits iguals es poden xifrar de maneres diferents depenent de l'estat en què es trobi el generador. En el proper capítol veurem que en el xifratge en bloc això no passa. Les xifres en bloc actuen sense memòria, i per tant el text xifrat només depèn del text en clar i de la clau.

Aquest capítol presenta les xifres de flux. En primer lloc, es defineix la noció de xifres de flux i es descriuen els conceptes bàsics relactionats amb la pseudoaleatorietat. A continuació, s'exposen els generadors lineals, tot detallant l'estructura dels generadors congruencials i dels registres de desplaçament realimentats linealment. Per acabar, es presenten els generadors no lineals i dos dels esquemes més populars actualment, l'A5 i el Trivium.

Capítol 4

Les xifres de bloc

Una alternativa a les xifres de flux són les xifres de bloc. Aquestes xifres s'inclouen també dins dels criptosistemes de clau compartida ja que la clau que s'utilitza per a xifrar i desxifrar és la mateixa i la comparteixen emissor i receptor. La diferència bàsica entre el xifratge en flux i el xifratge en bloc és la utilització de la memòria en els algorismes de xifratge.

Ja hem vist en el capítol anterior que el xifrat de flux utilitza una clau diferent per cada bit d'informació. Aquesta clau depèn de l'estat inicial del generador, però també de l'estat del generador en el moment de xifrar un bit concret. Per tant, dos bits iguals es poden xifrar de maneres diferents depenent de l'estat en què es trobi el generador. En el xifratge en bloc això no passa ja que les xifres en bloc actuen sense memòria, i per tant el text xifrat només depèn del text en clar i de la clau. D'aquesta manera, dos blocs de text en clar iguals es xifren sempre de la mateixa manera quan s'utilitza la mateixa clau. Caldrà estudiar aquest fet en detall ja que si no es corregeix, els sistemes de xifrat que en resulten són força vulnerables, ja que es poden inserir o esborrar blocs de text xifrat sense que es pugui detectar. A més, el fet que dos blocs de text en clar quedin xifrats d'una mateixa manera, pot donar pistes per a una possible criptoanàlisi de tipus estadístic.

Pel que fa a la seva utilització, les xifres de bloc són força utilitzades ja que aconsegueixen una velocitat acceptable de xifratge. En concret, el xifrador en bloc més utilitzat és l'AES (Advanced Encryption Standard) ja que està establert com a estàndard per el NIST des de l'any 2002.

Aquest capítol presenta les xifres de bloc. En primer lloc, es defineix la noció de xifres de bloc i es descriuen els diferents modes d'operació de les xifres de bloc. A continuació, el capítol s'endinsa en la descripció detallada del funcionament de l'AES, el criptosistema triat pel NIST com a estàndard de xifrat de bloc.

Capítol 5

Funcions hash

Les funcions hash són una primitiva criptogràfica cada vegada més important en diferents protocols i aplicacions criptogràfiques.

Com veurem, una funció hash és una funció que permet obtenir un valor fixat de mida reduïda a partir d'una entrada arbitràriament gran. Gràcies a les propietats que ofereixen a aquest valor de sortida, els usos de les funcions hash són múltiples, des de la seva utilització per a l'autentificació d'informació sense l'ús de signatures digitals (fent servir criptografia simètrica) fins a la verificació de proves de treball en criptomonedes, passant per la generació de contrasenyes o la reducció de la complexitat de càlcul en un procés de signatura digital.

L'ús de les funcions hash cada vegada en més contextos implica que la seva importància també hagi anat augmentant. Com és sabut, la seguretat que ofereix un sistema criptogràfic és equivalent a la seguretat que ofereix el seu component més feble o insegur. Per tant, a mida que les funcions hash han anat incloent-se en nous sistemes, la robustesa de les funcions hash afecta de ple en la seguretat d'aquests sistemes. Aquest punt és molt rellevant perquè una vulnerabilitat en una funció hash implicaria una vulnerabilitat en tots els sistemes criptogràfics que l'utilitzen. Per exemple, si un atacant pogués predir la sortida d'una funció hash donada una entrada fixada, podria arribar a trencar la seguretat d'algunes criptomonedes.

En aquest capítol definirem què són les funcions hash i quines propietats presenten. Posteriorment, veurem com es poden construir utilitzant com a base un criptosistema de bloc. Repassarem també quines són les funcions hash més utilitzades, funcions hash construïdes específicament per a aquest propòsit i que no es basen en cap criptosistema de bloc. En concret, veurem en detall el funcionament de la funció hash SHA256. Finalment, enumerarem algunes de les múltiples aplicacions que tenen les funcions hash i també algunes propietats addicionals que es poden demanar a les funcions hash que són útils en algunes de les aplicacions esmentades.

Capítol 6

Criptografia de clau pública

La criptografia de clau simètrica es caracteritza per fer servir una mateixa clau tant per xifrar com per a desxifrar. És a dir, en criptografia simètrica, tant l'emissor d'un missatge (que el xifrarà abans d'enviar-lo), com el receptor (que l'haurà de desxifrar per poder-lo interpretar), comparteixen una única clau.

La criptografia de clau simètrica presenta algunes limitacions:

• La distribució de claus s'ha de realitzar sobre un canal segur. Com que els dos usuaris comparteixen la mateixa clau i aquesta clau pot ser utilitzada directament per xifrar i desxifrar missatges, la clau no pot ser transmesa per un canal insegur, ja que aleshores un atacant que estigués escoltant el canal podria capturar-la i utilitzar-la. Per tant, per aconseguir que dos usuaris, l'Alice i en Bob, aconsegueixin tenir una clau simètrica amb què comunicar-se, caldrà que aquests dos usuaris hagin tingut un canal segur amb què transmetre-la amb anterioritat. Per exemple, caldrà que l'Alice i en Bob s'hagin trobat presencialment o bé que ja disposin d'un canal segur per on transmetre la clau.
• La gestió de claus es complica quan el número d'usuaris creix: el número de claus d'un sistema creix quadràticament amb el número d'usuaris d'aquest. Així doncs, apareixen problemes d'escalabilitat a l'hora de gestionar totes aquestes claus.
• No es disposa de la propietat de no-repudi. Diem que un criptosistema ofereix la propietat de no-repudi si l'autor d'un missatge no en podrà negar posteriorment l'autoria. En criptografia simètrica, com que més d'un usuari comparteixen una mateixa clau, no es pot garantir que un usuari en concret ha realitzat una acció donada, ja que sempre hi haurà algun altre usuari que podria haver-la realitzat.

La criptografia de clau pública o asimètrica permet superar aquestes limitacions. D'una banda, la criptografia de clau pública proporciona mètodes d'establiment de clau, és a dir, mètodes per aconseguir que dos usuaris que es comuniquen per un canal insegur puguin crear claus que els permetin comunicar-se de manera segura. D'altra banda, la criptografia de clau pública permet que un conjunt d'usuaris es comuniquin dos a dos de manera segura fent servir únicament un parell de claus per cada usuari. Així, el nombre de claus d'un sistema de clau pública creix linealment amb el número d'usuaris d'aquest sistema (en contraposició al creixement quadràtic que presenten els esquemes de criptografia simètrica). Finalment, a través de les signatures digitals, la criptografia de clau pública ens ofereix la propietat de no-repudi.

En aquest capítol ens introduirem en el món de la criptografia de clau pública. En primer lloc, descriurem el concepte de criptografia de clau pública o asimètrica, així com les característiques més destacades d'aquest tipus d'algorismes. Seguidament, veurem dos dels algorismes de xifrat de clau pública més utilitzats avui en dia: l'RSA i l'ElGamal. Després presentarem el concepte de signatura digital i descriurem tres dels algorismes més populars de signatura digital: l'esquema de signatura RSA, el d'ElGamal, i el DSA.

A continuació, compararem els algorismes de clau pública presentats amb els algorismes de criptografia simètrica que havíem vist en capítols anteriors, destacant-ne les seves fortaleses i debilitats. Després, descriurem alguns detalls a tenir en compte a l'hora d'implementar els algorismes de clau pública descrits. Finalment, presentarem una pinzellada d'altres famílies de criptografia de clau pública que, a diferència de les presentades amb detall en aquest capítol, no estan basades en els problemes de factorització d'enters i càlcul del logaritme discret.

Capítol 7

Infraestructura de clau pública

En el capítol anterior s'ha vist com l'aparició de la criptografia de clau pública permetia solucionar el problema de la distribució de claus. Ara bé, quan dues entitats volen iniciar una comunicació segura, com poden saber quina és la clau pública que correspon a cada una?

Per cobrir aquesta necessitat, és a dir, per vincular identitats amb les seves respectives claus públiques, apareixen els certificats digitals i, amb ells, la infraestructura de clau pública (en anglès Public Key Infrastructure, PKI), un conjunt de processos, rols i especificacions que permeten gestionar aquests certificats. Així, la infraestructura de clau pública permet transferir informació de manera segura, tot oferint serveis d'autenticació, integritat i confidencialitat.

En aquest capítol, es detallen quines són les principals entitats que formen part d'una infraestructura de clau pública i la seva funció, es descriu què són els certificats digitals i quin n'és el seu cicle de vida, s'exposen diferents estàndards que es fan servir en l'àmbit de les PKIs i, finalment, es discuteix sobre els problemes que pateixen els desplegaments de PKIs a nivell pràctic.

Capítol 8

Criptografia de corbes el·líptiques

En capítols anteriors s'ha vist com la criptografia de clau pública permetia solucionar alguns dels problemes presentats per la criptografia simètrica (com ara la distribució de claus) i alhora oferia propietats addicionals més enllà del xifratge (com ara el no repudi a través de signatures digitals). Ara bé, la criptografia de clau pública requereix de recursos computacionals més elevats que la criptografia simètrica, cosa que en dificulta la seva execució en dispositius amb poc recursos i en limita el nivell de seguretat com a conseqüència del compromís amb el temps d'execució. De fet, en el cas del xifratge, sovint es combina l'ús de la criptografia de clau pública amb criptografia simètrica a través de la tècnica del sobre digital, cosa que permet xifrar continguts de gran mida amb claus públiques més petites.

En aquest capítol es presenta la criptografia de corbes el·líptiques. Entre els seus principals avantatges hi trobem que la criptografia de corbes el·líptiques ofereix el mateix nivell de seguretat que la criptografia de clau pública tradicional però amb claus més petites. D'aquesta manera, s'aconsegueix també que les operacions criptogràfiques siguin més ràpides d'executar i requereixin de menys recursos computacionals, fent-les possibles en dispositius amb recursos limitats. A més, la criptografia de corbes el·líptiques permet la definició de pairings, amb els quals es poden crear construccions criptogràfiques amb propietats addicionals a les que ens oferia la criptografia de clau pública bàsica.

Així doncs, en primer lloc aquest capítol detalla els beneficis de la criptografia de corbes el·líptiques. A continuació, es presenten les corbes el·líptiques, la seva aritmètica, i es descriu com es fan servir les corbes el·líptiques en criptografia. Després s'explica el problema del logaritme discret sobre corbes el·líptiques i es detallen els algorismes criptogràfics més populars basats en aquest problema.

Capítol 9

Criptografia basada en pairings

En el capítol anterior s'han presentat les corbes el·líptiques i alguns dels seus usos en criptografia. Tot i això, no ens hem endinsat en una de les construccions més populars en els últims anys en criptografia basada en corbes el·líptiques: els pairings.

Algunes corbes el·líptiques tenen una estructura addicional anomenada aparellament (en anglès, es coneix com a pairings), que obre la porta a tot un nou conjunt d'eines criptogràfiques. En particular, els pairings es fan servir en criptografia per a atacar criptosistemes basats en el logaritme discret i també en la construcció de noves primitives criptogràfiques.

En aquest capítol descriurem les propietats dels pairings i la seva definició (tot explicant les eines matemàtiques necessàries per a construir-los), i veurem alguns algorismes criptogràfics basats en aquests.

Capítol 10

Protocols criptogràfics

Més enllà dels mecanismes per xifrar i desxifrar missatges el cert és que la criptografia permet construccions més elaborades que continuen tenint el mateix objectiu que els criptosistemes: protegir la informació. Així, ens podem trobar diferents situacions on calguin protocols que ens garanteixin un seguit de propietats de seguretat que els criptosistemes per si sols no poden proporcionar. És en aquest punt on intervenen els protocols criptogràfics, protocols entre dos o més usuaris que utilitzen mecanismes criptogràfics per protegir la informació.

En aquest capítol estudiarem diversos protocols criptogràfics cada un d'ells amb un propòsit diferent. Llevat de l'esquema de compartició de secrets, els protocols descrits en aquest capítol són protocols en els que hi intervenen dos usuaris i no es contempla l'existència de cap tercera part de confiança. Així, les operacions es realitzen, sovint de forma conjunta, entre els dos usuaris per aconseguir l'objectiu del protocol. La suposició que es fa en tot moment és que els usuaris poden actuar de forma deshonesta de manera que és important que els propis protocols incorporin els mecanismes de seguretat necessaris per tal que, en cas que una part actuï de forma maliciosa, l'altra part no se'n vegi afectada o, com a mínim, pugui detectar l'engany.

Aquest capítol presenta diversos protocols criptogràfics, cada un d'ells amb un propòsit diferent. Així, es descriuran protocols que permeten, entre d'altres objectius, compartir un secret entre un conjunt d'usuaris de forma segura, demostrar el coneixement d'un secret sense revel·lar-ne informació, transferir informació a un receptor sense que l'emissor coneixi quina part d'aquesta s'ha transmès o signar un missatge sense conèixer-ne el contingut.