Poly de Cryptographie

Pierre-Alain Fouque

1 Introduction : Principes de Cryptographie Moderne

La cryptographie historique est plus un art qu’une science. Les schemas etaient concus defacon ad-hoc et evalues sur leur complexite. Un schema etait analyse en etudiant les attaquess’il y en avait ; si oui, le schema etait modifie pour eviter les attaques et le processus se repetait.Bien qu’il y avait un accord sur le fait que certains schemas n’etaient pas sur, il n’y avait pasd’accord sur ce qu’un schema ”sur” devait satisfaire, et aucun moyen pour donner des indicationssur le fait qu’un schema etait sur.

Ces dernieres decennies, la cryptographie s’est developpee en une science. Les schemas ontete concus et analyses de facon plus systematique, avec comme objectif ultime de donner despreuves rigoureuses qu’une construction etait sure. Afin de donner de telles preuves, on a besoinde definitions formelles qui decrivent exactement ce que signifie ”sur”; de telles definitions sontutiles et interessantes en elle-meme. De cette facon, la plupart des preuves cryptographiques sontbasees sur des hypotheses non prouvees (conjectures), sur la difficulte algorithmique a resoudrecertains problemes mathematiques ; de telles conjectures doivent etre explicites et precisementetablies. L’accent sur les definitions, hypotheses, et preuves distinguent la cryptographie modernede la cryptographie classique.

1.1 Principe 1 : Definitions formelles

Une des contributions majeures de la cryptographie moderne a ete la reconnaissance que lesdefinitions formelles de securite sont essentielles pour une conception, etude, evaluation et utili-sation des primitives cryptographiques : Si on ne comprend pas ce qu’on veut obtenir, commentpeut-on savoir quand et comment l’atteindre ? Les definitions formelles permettent de comprendreen donnant une definition claire des menaces et des garanties de securite que l’on desire. De cettefacon, elles aident la conception des schemas cryptographiques. En effet, il est preferable de for-maliser ce qui est exige avant le debut de la conception, plutot que d’arriver a une definition defait quand la conception est terminee.

Les definitions permettent aussi d’evaluer et d’analyser les constructions. Avec une bonnedefinition, on peut etudier un schema propose afin de voir s’il satisfait les garanties demandees ;dans certains cas, on peut montrer une construction sure en montrant qu’elle satisfait les hypo-theses. De facon opposee, les definitions permettent aussi de montrer qu’un schema donne n’estpas sur, car le schema ne satisfait pas les definitions.

Les definitions permettent aussi de comparer les schemas entre eux. Comme on le verra, ilexiste diverses facons de definir la securite ; la ”bonne” facon depend du contexte dans lequel leschema est utilise. Un schema satisfaisant une definition faible peut etre plus efficace qu’un autreschema satisfaisant une definition plus forte ; avec les definitions on peut evaluer proprement lescompromis entre les schemas. Elles permettent aussi d’utiliser les schemas de facon sure. Conside-rons la question de decider quel schema de chiffrement utiliser pour une application donnee. Unebonne approche du probleme est de comprendre quelle notion de securite est demandee pour cette

1

application, et de trouver un schema de chiffrement qui satisfasse la notion. Une consequencede cette approche est la modularite : un concepteur peut eliminer un schema de chiffrement etle remplacer par un autre (qui satisfasse aussi la definition necessaire de securite) sans avoir asinquieter de comment la securite est affectee sur l’application globale.

L’ecriture d’une definition formelle oblige a penser a ce qui est essentiel au probleme et quellesproprietes sont en trop. En allant en detail, le processus revele des subtilites du probleme quin’etaient pas evidentes au premier abord. On illustre cela dans le cas du chiffrement.Un exemple : le chiffrement sur. Une erreur courante est de penser que les definitions

formelles ne sont pas necessaires, ou sont triviales a trouver, car ”tout le monde a une ideeintuitive de ce que signifie la securite.” Ce n’est pas le cas. Considerons le cas du chiffrement.(Comment peut-on definir formellement ce que signifie qu’un chiffrement est sur.) Bien quel’on reporte la definition formelle aux sections suivantes, on decrit ici informellement ce qu’unedefinition doit couvrir.

En general, la definition de securite a deux composantes : une garantie de securite (ou, dupoint de vue de l’adversaire, ce que constitue une attaque reussie sur le schema) et un modelede menace. La garantie de securite definit le but de l’adversaire (ce qu’il cherche a faire sur leschema), alors que le modele definit ses moyens (les actions que l’adversaire est capable de faire).

Commencons par les buts. Qu’est-ce que doit garantir un schema de chiffrement ?— Il doit etre impossible pour l’adversaire de retrouver la cle. On a vu precedemment que

si un adversaire peut determiner la cle partagee par les deux parties, alors le schema nepeut pas etre sur. Cependant, il est facile de trouver des schemas pour lesquels retrouverla cle est impossible, mais le schema n’est pas sur trivialement. Par exemple, le schema ouEnck(m) = m. Le chiffre ne fait fuir aucune information sur la cle (et donc, la cle ne peutpas etre retrouvee si elle est suffisamment longue) mais le message est envoye en clair !Nous voyons donc que l’incapacite a retrouver la cle n’est pas suffisante pour garantirla securite. Le but du chiffrement est de proteger le message ; la cle est un moyen pouratteindre ce but, mais ce n’est pas important.

— Il doit etre impossible pour l’adversaire de retrouver le clair a partir du chiffre. Cettedefinition est meilleure, mais elle n’est pas encore satisfaisante. En particulier, cette defi-nition considere un schema de chiffrement sur si les chiffres revelent 90% du clair, aussilongtemps que 10% du clair reste difficile a retrouver. Cela est clairement inacceptabledans la plupart des applications du chiffrement ; par exemple, quand on chiffre une basede donnees, il est inadmissible si 90% des salaires des employes est revele.

— Il doit etre impossible de retrouver tout caractere du clair a partir du chiffre. Ceci paraıtune bonne definition, mais elle n’est pas encore suffisante. En revenant a l’exemple de labase de donnees, on ne peut pas considerer un schema de chiffrement sur s’il revele si unemploye gagne plus ou moins de 100,000 euros meme s’il ne revele aucun chiffre du salaire.De facon similaire, on ne peut pas considerer un schema de chiffrement sur s’il revele siun employe A gagne plus que l’employe B.Un autre probleme est comment formaliser ce que signifie pour un adversaire de ”retrouverle caractere d’un clair.” Si un attaquant devine correctement par chance ou une informa-tion externe, que le chiffre de poids faible du salaire est 0 ? Ceci ne doit clairement pasrendre le schema de chiffrement non sur, et donc toute definition viable doit eviter un telcomportement comme etant une attaque reussie.

— La ”bonne” reponse : independamment de toute information qu’un adversaire a deja, unchiffre ne doit pas laisser fuire des informations supplementaires sur le clair sous-jacent.Cette definition informelle capture tous les problemes precedemment cites. Notons enparticulier que l’on n’essait pas de definir quelle information sur le clair est ”significative”;elle demande simplement qu’aucune information fuit. Ceci est important, car il signifie

2

qu’un schema de chiffrement sur peut etre utilise dans toutes les applications potentiellesdans lesquelles la securite est demandee.Mais il manque ici, une formulation mathematique et precise de la definition. Commentpeut-on capturer la connaissance a priori de l’attaquant sur le clair ? Et que signifie nelaisser fuir aucune information ?

Maintenant que l’on a fixe un but de securite, il reste a specifier un modele d’attaque. Cecidefinit quelle ”puissance” l’adversaire est suppose avoir, mais ne pose aucune restriction sur lastrategie de l’adversaire. C’est une distinction importante : on definit ce qu’on suppose si lescapacites de l’adversaire, mais on ne suppose rien sur comment il utilise ces capacites. Il estimpossible de prevoir quelle strategie va etre utilisee par l’adversaire.

Il y a plusieurs options possibles pour les moyens selon le contexte d’utilisation, en ordrecroissant de puissance de l’adversaire :

— attaque a chiffres seuls : Il s’agit de l’attaque de base et considere seulement un scenarioou l’attaquant observe juste les chiffres et tente de determiner des informations sur lesclairs sous-jacents. Il s’agit des moyens que l’on suppose implicitement quand on considereles schemas de chiffrement classiques.

— attaque a clairs connus : L’adversaire est capable d’apprendre des paires clair/chiffregeneres en utilisant une cle . Le but de l’adversaire est de deduire des informations sur leclair sous-jacent d’autres chiffres produit en utilisant la meme cle. Les schemas historiquessont en general trivials a casser dans ce modele.

— attaque a clairs choisis.Dans cette attaque, l’adversaire peut obtenir des paires clair/chiffrepour des clairs de son choix.

— attaque a chiffres choisis. Dans ce dernier type d’attaque, l’adversaire est en plus ca-pable d’obtenir (des informationssur le dechiffrement de chiffres de son choix, par exemplesi le dechiffrement de chiffres choisis par l’adversaire donne un clair valide en anglais. Lebut de l’adversaire est d’apprendre des informations sur le clair correspondant d’autreschiffres (dont le dechiffrement n’est pas possible par l’adversaire).

Aucun de ces modeles n’est meilleur qu’un autre ; celui qu’il faut utiliser depend de l’envi-ronnement dans lequel le chiffrement est utilise. Les deux premiers modeles sont faciles a mettreen oeuvre. Les deux derniers paraissent plus difficilement credibles, mais nous donnerons desexemples.

1.2 Principe 2 : Conjectures Precises

La plupart des constructions cryptographiques modernes ne peuvent pas etre prouvees sure-sinconditionnellement ; de telles preuves demandent de resoudre des questions en theorie de lacomplexite calculatoire qui paraissent inaccessibles actuellement. Le resultat de ce malheureuxetat de fait est que les preuves de securite sont basees sur des hypotheses. La cryptographiemoderne exige que ces hypotheses soient rendues explicites et mathematiquement precises. Onpourrait dire que les preuves de securite mathematiques le demandent, mais il y a d’autres bonnesraisons :

1. Validation des hypotheses. Les hypotheses sont des enonces qui ne peuvent pas etre prou-ves mais sont conjectures comme etant vrais. Afin de renforcer notre croyance dans ceshypotheses, il est necessaire de les etudier. Plus l’hypothese est etudiee sans etre refutee,plus on est confiant de sa veracite. De plus, l’etude de cette hypothese peut fournir despreuves de sa validite en montrant qu’elle implique une autre hypothese qui est cru parbeaucoup de monde.

Si l’hypothese sur laquelle on se repose n’est pas precisement enoncee, elle ne peut pasetre etudiee ou refutee. Donc, une pre-condition pour augmenter notre croyance dans cette

3

hypothese est d’avoir un enonce precis de ce qui est exactement suppose.

2. Comparaisons des schemas. Souvent en cryptographie, on est confronte a deux schemasqui peuvent tous les deux etre prouves pour satisfaire une hypothese, mais bases sur deshypotheses differentes. Supposant que tout le reste est identique, quel schema prefere ?Si l’hypothese sur laquelle repose le premier schema est plus faible que l’hypothese dusecond schema (c’est-a-dire que l’hypothese du second schema implique la premiere), alorsle premier schema est preferable car il peut arriver que la seconde hypothese soit faussealors que la premiere est vraie. Si les hypotheses utilisees par les deux schemas ne sontpas comparables, alors la regle generale est de preferer le schema qui est base sur unehypothese bien etudiee dans laquelle on a pleine confiance.

3. Comprehension des hypotheses necessaires. Un schema de chiffrement peut etre construitautour d’une autre construction. Si des faiblesses sont trouvees sur cette derniere, commentpeut-on dire si la premiere construction est toujours sur ? Si les hypotheses sous-jacentesconcernant la seconde construction sont claires dans la preuve de securite du schema, alorson a juste besoin de verifier si les hypotheses sont affectees par les faiblesses que l’on atrouvees.

On peut se poser la question : au lieu de prouver un schema sur sur une hypothese, pourquoine pas simplement supposer que la construction en elle-meme est sure ? Dans certains cas, parexemple, quand un schema a resiste a plusieurs attaques pendant de longues annees, cette ap-proche peut etre raisonnable. Mais cette approche n’est jamais a privilegier car elle comporte descontreparts dangereuses quand un nouveau schema est introduit. Une hypothese qui a ete testeependant de longues annees est preferable a une nouvelle ad-hoc hypothese introduite avec unnouveau schema. Ensuite, il y a une preference aux hypotheses simples a enoncer, car elles sontplus simples a etudier ou a refuter. Par exemple, une hypothese qu’un probleme mathematiquesoit difficile a resoudre est plus simple a etudier et evaluer qu’une hypothese qu’un schema dechiffrement satisfait une definition complexe de securite. Un autre avantage de s’appuyer sur deshypotheses ”bas niveau” (plutot que de simplement supposer qu’une construction est sure) estque ces hypotheses bas-niveau peuvent etre reutilisees pour d’autres constructions. Finalement,des hypotheses bas niveau fournissent de la modularite. Considerons un schema de chiffrementdont la securite repose sur une propriete d’un de ces composants. Si la propriete du composant estrefutee, le schema peut quand meme etre instancie en utilisant un autre composant satisfaisantla propriete.

1.3 Principe 3 : Preuves de securite

Les deux principes precedents permettent d’atteindre notre but en fournissant des preuvesrigoureuses qu’une contruction satisfait une definition donnee sous des hypotheses precises. Detelles preuves sont tres importantes dans le contexte de la cryptographie ou un adversaire tentede ”casser” un schema. Les preuves de securite donnent une garantie - relativement aux defini-tions et hypotheses - qu’aucun attaquant ne reussira ; c’est bien mieux que choisir une approcheheuristique sans principe du probleme. Sans une preuve qu’aucun adversaire avec des ressourceslimitees peut casser un schema, on n’a que notre intuition pour esperer que le schema soit sur.L’experience a souvent ete desastreuse en cryptographie et en securite informatique.

Resume : Approches de la securite Ad Hoc versus Rigoureuse. S’appuyer sur des de-finitions, hypotheses et preuves constitue une approche rigoureuse de la cryptographie qui estdifferente d’une approche informelle de la cryptographie classique.

4

1.4 Principe 4 : Securite Prouvable et Monde Reel

La plupart de la cryptographie moderne s’appuie maintenant sur des fondations mathema-tiques rigoureuses. Mais cela ne signifie pas que le domaine n’est plus un art non plus. L’ap-proche rigoureuse laisse de la place pour la creativite en developpant des definitions adapteesaux applications contemporaines et aux environnements, en proposant de nouvelles hypothesesmathematiques, en concevant de nouvelles primitives, et en construisant de nouveaux schemas eten les prouvant surs. Il y a aussi toujours l’art de l’attaque sur les cryptosystemes concus, memes’ils sont prouves.

L’approche prise par la cryptographie moderne a revolutionne le domaine, et aide a donnerconfiance dans la securite des schemas deployes dans le monde reel. Cependant, il est importantde ne pas surestimer ce qu’une preuve de securite garantit. Une preuve de securite est toujoursrelative a une definition donnee et des hypotheses. Si la securite garantie ne correspond pas a cedont on a besoin, ou les moyens de l’adversaire ne capturent pas tout ce que l’adversaire peutfaire, alors la preuve n’est pas utile. De maniere similaire, si les hypotheses s’averent fausse, lapreuve est inutile.

La securite prouvable d’un schema n’implique pas necessairement la securite du schema dansle monde reel. Certains ont vu cela comme un inconvenient de la securite prouvable, on peutaussi dire de facon optimiste que cela renforce l’approche. Pour attaquer un schema prouve surdans le monde reel, il suffit de se concentrer sur la definition (c’est-a-dire explorer si la definitionidealisee differt de l’environnement dans lequel le schema est utilise) ou des hypotheses sous-jacentes (pour voir si elles sont satisfaites). C’est le but des cryptographes de continuellementrafiner les definitions pour etre plus pres du monde reel, et d’etudier les hypotheses. La securiteprouvable ne clot pas la bataille entre attaquant et defenseur, mais elle fournit un cadre qui aidea eliminer les erreurs a la faveur des defenseurs.

2 Cryptographie Symetrique

2.1 Securite Parfaite

2.1.1 Definitions

Un systeme de chiffrement est defini par trois algorithmes Gen, Enc et Dec ainsi qu’un ensemblefini de messages M avec |M| > 1. L’algorithme de generation de cle Gen est un algorithmeprobabiliste qui retourne une cle k choisie selon une distribution de probabilite. On representepar K l’espace fini des cles, i.e. l’ensemble de toutes les cles possibles qui peuvent etre retourneespar Gen. L’algorithme de chiffrement Enc qui prend comme entree la cle k ∈ K et un messagem ∈ M et retourne un chiffre c. On autorise l’algorithme de chiffrement d’etre probabiliste(donc Enck(m) peut retourner un chiffre different quand on l’execute plusieurs fois), et on ecritc ← Enck(m) pour representer le processus aleatoire par lequel le message m est chiffre sous lacle k pour donner le chiffre c. (Dans le cas ou Enc est deterministe, on ecrira c := Enck(m). Onutilise aussi la notation x← S pour representer un choix aleatoire de x dans l’ensemble S.) Ondenote par C l’ensemble de tous les chiffres possibles qui sont retournes par Enck(m), pour toutesles cles k ∈ K et les messages m ∈ M (et pour tous les choix aleatoires de Enc dans le cas oul’algorithme est randomise). L’algorithme de dechiffrement Dec prend comme cle k ∈ K et unchiffre c ∈ C et retourne un message m ∈M. On suppose une correction parfaite, c’est-a-dire quepour tout k ∈ K, m ∈ M, et tout chiffre c retourne par Enck(m), Deck(c) = m avec probabilite1. La correction parfaite implique que Dec est deterministe sans perte de generalite, car Deck(c)doit toujours retourne m a chaque execution. On ecrira donc m := Deck(c) pour representer leprocessus de dechiffrement du chiffre c en utilisant la cle k qui donne le message m.

5

Dans les definitions et theoremes ci-dessous, on utilise des distributions de probabilites surK,M et C. La distribution sur K est celle definie en executant l’algorithme Gen et retournant lasortie. (Dans presque tous les cas, Gen choisit une cle uniformement au hasard et on le supposeradans la suite.) On denote par K la variable aleatoire representant la valeur de la cle retourneepar Gen ; donc, pour tout k ∈ K, Pr[K = k] represente la probabilite que la cle retournee parGen soit k. De facon similaire, soit M la variable aleatoire representant le message a chiffreret donc Pr[M = m] represente la probabilite que le message prend pour la valeur m ∈ M. Ladistribution de probabilite du message n’est pas definie par le schema de chiffrement, mais re-presente la probabilite des differents messages qui doivent etre envoyes par les parties utilisantle schema, ainsi que par l’incertitude de l’adversaire sur ce qui est envoye. Comme exemple, l’ad-versaire peut savoir que les messages seront soit attack today ou don’t attack. L’adversairepeut meme savoir par d’autres moyens que la probabilite du premier message est 0.7. Dans cecas, on a Pr[M = attacktoday] = 0.7 et Pr[M = don′tattack] = 0.3. K et M sont supposesindependants, i.e. ce qui est communique par les parties est independant de la cle. C’est raison-nable car la distribution sur K est determinee par le schema de chiffrement par l’algorithme Gen,alors que la distribution surM depend du contexte d’utilisation.

La definition d’un schema de chiffrement et d’une distribution sur M determine une distri-bution sur l’espace des chiffres C donnee en choisissant une cle k ∈ K (selon Gen) et un messagem ∈ M (selon la distribution donnee), et ensuite en calculant le chiffre c← Enck(m). Soit C lavariable aleatoire representant le chiffre resultant et donc, pour c ∈ C, on ecrit Pr[C = c] pourrepresenter la probabilite que le chiffre soit egal a la valeur c.

Exemple : Considerons un chiffrement par decalage a la Cesar. Par definition, K = {0, . . . , 25}avec Pr[K = k] = 1/26 pour chaque cle k ∈ K. Soit la distribution suivante sur les messages del’ensembleM :

Pr[M = a] = 0.7 et Pr[M = z] = 0.3.

Quelle est la probabilite que le chiffre soit B ? Il y a seulement 2 cas pour que cet evenementarrive : soit M = a et K = 1 ou M = z et K = 2. Par independance de M et K, on a :

Pr[M = a ∧K = 1] = Pr[M = a].Pr[K = 1] = 0.7.

(1

26

).

De facon similaire, Pr[M = z ∧K = 2] = 0.3.(1/26). Par consequent,

Pr[C = B] = Pr[M = a ∧K = 1] + Pr[M = z ∧K = 2]

= 0.7.

(126

)+ 0.3.

(126

)= 1/26.

On peut calculer ensuite la probabilite conditionnelle. Par exemple, quelle est la probabiliteque le message a soit chiffre, etant donne que l’on observe le chiffre B ? En utilisant le theoremede Bayes, on a :

Pr[M = a|C = B] = Pr[C=B|M=a]·Pr[M=a]Pr[C]=B

= 0.7·Pr[C=B|M=a]1/26 .

En remarquant que Pr[C = B|M = a] = 1/26, car si M = a, alors le seul moyen pour C = B

est que K = 1 (ce qui arrive avec probabilite 1/26). On en conclut que Pr[M = a|C = B] = 0.7.Exemple 2 : Considerons encore le chiffrement de Cesar mais avec la distribution suivante sur

M :Pr[M = kim] = 0.5,Pr[M = ann] = 0.2, et Pr[M = boo] = 0.3.

6

Quelle est la probabilite que C = DQQ ? La seule facon que ce chiffre peut etre obtenu est si M =ann et K = 3 ou si M=boo et K = 2, ce qui arrive avec probabilite 0.2 · 1/26+0.3 · 1/26 = 1/52.

Donc quelle est la probabilite que ann ait ete chiffre, conditionne par l’observation que lechiffre soit DQQ ? En utilisant le theoreme de Bayes, on obtient Pr[M = ann|C = DQQ] = 0.4.

2.1.2 Securite Parfaite

On est pret pour definir la notion de securite parfaite. On imagine un adversaire qui connaıtla distribution surM ; c’est-a-dire que l’adversaire connaıt la probabilite de chacun des messages.L’adversaire connaıt aussi le schema de chiffrement ; la seule chose qu’il ne connaıt pas est la cle.Un message est choisi par une partie et chiffre, le chiffre resultant est transmis a l’autre partie etl’adversaire peut l’intercepter. (C’est une attaque a chiffre seul.) Un schema garantit la securiteparfaite si observer le chiffre ne donne pas d’information a l’adversaire concernant le messagem ; en d’autres termes la probabilite a posteriori qu’un message m ∈M soit envoye conditionnepar le fait que l’on connaıt le chiffre c, ne doit pas etre different de la probabilite a priori quele message soit envoye. Ceci signifie que le chiffre ne revele rien sur le clair sous-jacent et quel’adversaire apprend absolument rien sur le clair. Plus formellement :

Definition 1. Un schema de chiffrement (Gen,Enc,Dec) avec comme espace de messagesM estparfaitement sur si pour toute distribution sur M, chaque message m ∈ M et tout chiffre c ∈ Ctel que Pr[C = c] > 0 :

Pr[M = m|C = c] = Pr[M = m].

(La condition Pr[C = c] > 0 est juste technique pour eviter une division par zero.)

On donne maintenant une formulation equivalente de la securite parfaite. Informellement,cette formulation demande que la distribution de probabilite du chiffre ne depende pas de celledes clairs, i.e., pour tous messages m,m′ ∈M, et tout c ∈ C,

Pr[EncK(m) = c] = Pr[EncK(m′) = c]

(ou les probabilites sont sur le choix de K et sur l’alea utilise par Enc.) Ceci implique que lechiffre contient aucune information sur le clair, et qu’il est impossible de distinguer le chiffre dem d’un chiffre de m′ car les distributions sur le chiffre sont les memes dans chaque cas.

Lemme 1. Un schema de chiffrement (Gen,Enc,Dec) avec espace de messageM est parfaitementsur si et seulement si l’equation Pr[EncK(m) = c] = Pr[EncK(m′) = c] est satisfaite pour toutm,m′ ∈M et tout c ∈ C.

Demonstration. On montre que si la condition est satisfaite, alors le schema est parfaitementsur (la reciproque est laissee en exercice). Fixons une distribution surM, un message m, et unchiffre c tel que Pr[C = c] > 0. Si Pr[M = m] = 0, alors on a trivialement :

Pr[M = m|C = c] = 0 = Pr[M = m].

Donc, supposons que Pr[M = m] > 0. On remarque d’abord que :

Pr[C = c|M = m] = Pr[Enck(M) = c|M = m] = Pr[Enck(M) = c],

ou la premiere egalite est la definition de la variable aleatoire C, et la seconde car on conditionnesur l’evenement M = m. Soit δc := Pr[Enck(m) = c] = Pr[C = c|M = m]. Si la condition dulemme est satisfaite, alors pour tout m′ ∈ M, on a Pr[Enck(m

′) = c] = Pr[C = c|M = m′] = δc.En utilisant le theoreme de Bayes, on a :

7

Pr[M = m|C = c] = Pr[C=c|M=m]·Pr[M=m]Pr[C=c]

= Pr[C=c|M=m]·Pr[M=m]∑m′∈M Pr[C=c|M=m′]·Pr[M=m′]

= δc·Pr[M=m]∑m′∈M δc·Pr[M=m′]

= Pr[M=m]∑m′∈M Pr[M=m′] = Pr[M = m]

ou la sommation est sur m′ ∈M avec Pr[M = m′] = 0. On en conclut que pour tout m ∈Met c ∈ C tel que Pr[C = c] > 0, et il vient Pr[M = m|C = c] = Pr[M = m], et donc le schema estparfaitement sur.

2.1.3 Indistinguabilite parfaite

On conclut cette section en donnant une definition equivalente de la securite parfaite. Cettedefinition est basee sur une experience impliquant un adversaire qui observe passivement leschiffres et ensuite en essayant de deviner lequel des deux messages est chiffre. On presente cettenotion car elle sert de base pour definir la securite calculatoire dans la section suivante. En effet,dans le reste du poly, on utilise des experiences pour definir les definition de securite.

On considere l’experience suivante : un adversaire A choisit d’abord deux messages arbitrairesm0,m1 ∈ M. Un de ces deux messagesest choisi uniformement au hasard et chiffre en utilisantune cle aleatoire ; le chiffre resultat est donne a A. Finalement, A retourne un pari sur lequel desdeux messages a ete chiffre ; A reussit s’il devine correctement. Un schema de chiffrement estparfaitement indistinguable si aucun adversaire peut reussir avec une probabilite meilleure que1/2. (On remarque que A peut toujours reussir avec probabilite 1/2 en retournant un bit alea-toire ; l’exigence est simplement que l’adversaire ne peut pas faire mieux que cela.) On remarquequ’aucune limitation n’est faite sur les capacites de calcul de A.

Formellement, soit Π = (Gen,Enc,Dec) un schema de chiffrement avec comme espace demessage M. Soit A un adversaire, qui est formellement juste un algorithme (avec etat). Ondefinit l’experience PrivKeav

A,Π :

1. L’adversaire A retourne un couple de messages m0,m1 ∈M ;

2. Une cle k est generee en utilisant Gen, et un bit est choisi au hasard b ∈ {0, 1}. Un chiffrec← Enck(mb) est calcule et donne a A. On dit que c est le chiffre challenge.

3. A retourne un bit b′.

4. La sortie de l’experience est definie a 1 si b′ = b et 0 sinon. On ecrit PrivKeavA,Π = 1 si la

sortie de l’experience est 1 et dans ce cas, on dit que A reussit.

Il est trivial pour A de gagner avec probabilite 1/2 en retournant un bit aleatoire. L’indistin-guabilite parfaite dit qu’il est impossible pour A de faire mieux.

Definition 2. Un schema de chiffrement Π = (Gen,Enc,Dec) avec espace de message M estparfaitement indistinguable si pour tout adversaire A,

Pr[PrivKeavA,Π = 1] = 1/2.

Lemme 2. Un schema de chiffrement Π est parfaitement sur si et seulement si il est parfaitementindistinguable.

Demonstration. Exercice.

Lemme 3. Le chiffrement de Vigenere n’est pas parfaitement indistinguable.

Demonstration. Exercice.

8

2.1.4 Masque Jetable (One-Time Pad)

Theoreme 1. Le schema de chiffrement one-time pad est parfaitement sur.

Demonstration. On calcule d’abord Pr[C = c|M = m′] pour un chiffre c ∈ C arbitraire etm′ ∈M. Pour le one-time pad,

Pr[C = c|M = m′] = Pr[EncK(m′) = c] = Pr[m′ ⊕K = c]= Pr[K = m′ ⊕ c]= 2−ℓ,

ou l’egalite finale est satisfaite car la cle K est une chaıne de ℓ bits. Fixons une distributionsurM. Pour tout chiffre c ∈ C, on a :

Pr[C = c] =∑

m′∈M Pr[C = c|M = m′] · Pr[M = m′]= 2−ℓ ·

∑m′∈M Pr[M = m′]

= 2−ℓ,

ou la somme est sur m′ ∈M avec Pr[M = m′] = 0. Le theoreme de Bayes donne :

Pr[M = m|C = c] = Pr[C=c|M=m]·Pr[M=m]Pr[C=c]

= 2−ℓ·Pr[M=m]2−ℓ

= Pr[M = m].

On conclut que le one-time pad est parfaitement sur.

Limitations de la securite parfaite .

Theoreme 2. Si (Gen,Enc,Dec) est un schema de chiffrement parfaitement sur avec commeespace de messagesM et espace de cles K, alors |K| ≥ |M|.

Demonstration. On montre que si |K| < |M|, alors le schema ne peut pas etre parfaitement sur.Supposons que |K| < |M|. Considerons la distribution uniforme sur M et soit c ∈ C un chiffrequi arrive avec probabilite non nulle. Soit M(c) l’ensemble des messages possibles qui sont desdechiffres possibles de c ; c’est-a-dire :

M(c) := {m|m = Deck(c) pour un certain k ∈ K}.

Clairement |M(c)| ≤ |K|. (On rappelle que l’on peut supposer Dec deterministe.) Si |K| < |M|,il existe un m′ ∈M tel que m′ ∈ M(c). Mais alors,

Pr[M = m′|C = c] = 0 = Pr[M = m′],

et donc le schema ne peut pas etre parfaitement sur.

Montrer le theoreme de Shannon :

Theoreme 3. Soit (Gen,Enc,Dec)un schema de chiffrement avec comme espace de messagesM,tel que |M| = |K| = |C|. Le schema est parfaitement sur ssi :

1. Chaque cle k ∈ K est choisie avec probabilite egale 1/|K| par Gen,

2. pour chaque m ∈ M et tout c ∈ C, il existe une unique cle k ∈ K telle que Enck(m)retourne c.

9

Demonstration. L’intuition est la suivante. Pour montrer que les conditions impliquent la securiteparfaite, on remarque que la condition 2 signifie que tout chiffre pourrait etre le resultat duchiffrement d’un message m, car il existe une cle k envoyant m sur c. Comme il existe une uniquetelle cle, et que chaque cle est choisie avec probabilite egale, la securite parfaite s’ensuit commedans le cas du one-time pad. Pour l’autre direction, la securite parfaite implique immediatementque pour tout m et c, il existe au moins une cle envoyant m sur c. Le fait que |M| = |K| = |C|signifie de plus que pour tout m et c, il y a exactement une telle cle. Etant donne cela, chaquecle doit etre choisie avec probabilite egale ou sinon la securite parfaite ne peut pas etre satisfaite.Fixons c ∈ C and m ∈M. Soir k l’unique cle, garantie par la condition 2, telle que Enck(m) = c.Alors,

Pr[C = c|M = m] = Pr[K = k] = 1/|K|,

ou la derniere egalite est satisfaite d’apres la condition 1. Donc,

Pr[C = c] =∑

m∈MPr[EncK(m) = c] · Pr[M = m] = 1/|K|.

Ceci est vrai pour toute distribution surM. Ainsi, pour toute distribution surM, tout m ∈Mtel que Pr[M = m] > 0, et tout c ∈ C, on a :

Pr[M = m|C = c] = Pr[C=c|M=m]·Pr[M=m]Pr[C=c]

= Pr[EncK(m)=c]·Pr[M=m]Pr[C=c]

= |K|−1·Pr[M=m]|K|−1 = Pr[M = m],

et le schema est parfaitement sur.Pour la seconde direction, supposons que le chiffrement soit parfaitement sur ; et montrons

que les conditions 1 et 2 sont satisfaites. Fixons c ∈ C. Il doit exister un message m∗ pour lequelPr[EncK(m∗) = c] = 0. Le lemme 1 implique que Pr[EncK(m) = c] = 0 pour tout m ∈ M. End’autres mots, si on pose M = {m1,m2, . . .}, alors pour tout mi ∈ M, on a un ensemble nonvide de cles Ki ⊂ K tel que Enck(mi) = c si et seulement si k ∈ Ki. De plus, quand i = j, alorsKi et Kj doivent etre disjoint ou sinon la correction va echouer. Comme |K| = |M|, on voit quechaque Ki contient une unique cle ki comme la condition 2 l’indique. Maintenant, le lemme 1montre que pour tout mi,mj ∈M, on a :

Pr[K = ki] = Pr[EncK(mi) = c = Pr[EncK(mJ ) = c] = Pr[K = kj ].

Comme cela est vrai pour tout 1 ≤ i, j ≤ |M| = |K|, et ki = kj pour i = j, ceci signifie quechaque cle est choisie avec probabilite 1/|K|, comme le demande la condition 1.

Le theoreme de Shannon est utile pour decider si un schema donne est parfaitement sur.La condition 1 est facile a verifier, et la condition 2 peut etre demontree (ou contredite) sansavoir a calculer des probabilites. La securite du one-time pad est facile a montrer en utilisant cetheoreme. Mais le theoreme ne s’applique que si |M| = |K| = |C|.

2.2 Chiffrement a cle secrete

Dans le chapitre precedent, nous avons montre les limitations fondamentales du chiffrementparfaitement sur. Dans ce chapitre, nous commencons l’etude de la cryptographie moderne enintroduisant la notion plus faible (mais suffisante) de securite calculatoire. Nous montrerons com-ment cette definition peut etre utilisee pour contourner les resultats d’impossibilite precedents,

10

et en particulier comment une cle courte (disons de 128 bits) peut etre utilisee pour chiffrer delongs messages (plusieurs gigabits).

En passant, nous etudirons la notion fondamentale de pseudo-alea, qui capture l’idee quequelque chose peut avoir l’air completement aleatoire meme s’il ne l’est pas. Ce concept puissanta plusieurs applications en cryptographie moderne et au-dela de ce domaine.

2.2.1 Securite calculatoire

Dans le chapitre precedent, nous avons introduit la notion de securite parfaite. Alors que cettederniere est un but important, elle est sans raison particuliere trop forte. Elle exige qu’absolumentaucune information sur le chiffre fuit a l’adversaire, meme a un attaquant avec une puissance decalcul infinie. Pour toutes les applications pratiques, cependant, un schema de chiffrement pourratoujours etre considere sur s’il laisse fuir une petite quantite d’information a un adversaire avec desressources de calcul bornees. Par exemple, un schema qui fuit des informations avec probabilite auplus 2−60 a un adversaire ayant au plus 200 ans de calcul sur l’ordinateur le plus rapide au mondeest admissible pour la plupart des applications dans le monde reel. Les definitions de securitequi prennent en compte les limites en temps de calculs de l’attaquant et autorisent une petiteprobabilite d’echec, sont dites calculatoires, pour les distinguer des notions (comme la securiteparfaite) qui sont issues de la theorie de l’information. La securite calculatoire est maintenant lestandard dans lequel la securite est definie pour tous les objectifs cryptographique.

On insiste sur le fait que bien que l’on abandonne d’atteindre la securite parfaite, ceci ne signi-fie pas que l’on abandonne la rigueur mathematique. Les definitions et preuves sont essentielles,et la seule difference est que l’on considere des definitions de securite (plus faibles).

La securite calculatoire s’appuie sur deux affaiblissements relatives de la securite au sens dela theorie de l’information (dans le cas des schemas de chiffrement, ces deux affaiblissements sontnecessaires pour aller au-dela des limitations de la securite parfaite) :

1. La securite est seulement garantie contre des adversaires efficaces qui s’executent pendantun temps borne. Ceci signifie qu’etant donne un temps suffisamment long (ou des ressourcescalculatoires) un attaquant peut etre capable de briser la securite. Si on peut rendre lesressources exigee pour casser le schema plus grande que n’importe quel adversaire realiste,alors pour toutes les applications pratiques le schema est incassable.

2. Les adversaires peuvent eventuellement reussir (i.e. la securite peut eventuellement echouee)avec une probabilite de succes tres petite. Si on peut rendre cette probabilite suffisammentpetite, on n’a pas besoin de s’inquieter.

Pour obtenir une theorie utile, on a besoin de definir precisement les deux affaiblissements.Il existe deux approches pour ce faire : l’approche concrete et l’approche assymptotique.

L’approche concrete. L’approche concrete de la securite calculatoire quantifie la securited’un schema cryptographique en donnant explicitement des bornes sur la probabilite maximalede succes de tout (eventuellement probabiliste) attaquant s’executant pendant une quantite detemps limitee.

Le schema est (t, ε)-sur si tout adversaire s’executant en temps au plus t reussit a casser leschema avec probabilite au plus ε.

Dans la suite, on definira bien sur ce que veut represente la securite en question. Consideronsun schema avec la garantie qu’aucun adversaire s’executant en au plus 200 ans en utilisant leplus rapide super-ordinateur ne peut reussir a casser le schema avec probabilite meilleure que2−60. Il peut etre plus simple de mesurer le temps en cycles CPU et de construire un schema tel

11

qu’aucun adversaire en utilisant au plus 280 cycles, ne peut le casser avec probabilite meilleureque 2−60. Il est important d’avoir en tete les valeurs courantes de t et ε typiques.

Exemple. Les schemas de chiffrement a cle symetrique modernes sont supposes garantir unesecurite optimale au sens suivant : quand la cle est de taille n - et donc l’espace de recherche aune taille 2n - un adversaire s’executant en temps t (mesure en cycles CPU) reussit a casser leschema avec probabilite au plus ct/2n pour une constante c fixee. (Ceci correspond a une attaquepar force brute sur l’espace des cles et suppose qu’aucun precalcul n’est fait).

Supposons que c = 1 par simplicite et une longueur de cle n = 60 fournisse une securitesuffisante contre un adversaire ayant un ordinateur de bureau. En effet, sur un processeur a 4GHz(qui execute 4× 109 cycles par secondes) 260 cycles CPU demandent 260/(4× 109) secondes, soitenviron 9 ans. Cependant, le super-calculateur le plus rapide en ce moment peut effectuer environ2× 1016 operations flottantes par seconde et 260 operations demandent environ 1 minute. Si onchoisit n = 80, un choix plus prudent, meme l’ordinateur precedent demanderait 2 ans pourvenir a bout des 280 operations. (Ces nombres ne servent que d’exemples ; en pratique c > 1 etplusieurs facteurs – comme le temps necessaire pour faire les acces memoire et les possibilitesde parallelisation des reseaux d’ordinateurs – ce qui affecte les performances des attaques parrecherche brute.)

Aujourd’hui, le niveau recommande de taille de cle est n = 128. Les differences entre 280 et2128 sont un facteur multiplicatif de 248. Pour avoir une intuition de la taille de ce facteur, disonsque selon les physiciens le nombre de secondes depuis le Big Bang est de l’ordre de 258. Si laprobabilite qu’un attaquant reussisse a dechiffrer un message chiffre en un an est au plus 2−60,alors il est plus probable que l’emetteur et le receveur soient tous les deux touches par la foudrependant cette duree. Un evenement qui apparaıt une fois tous les 100 ans peut etre estime aavoir lieu avec probabilite 2−30 a toute seconde. Quelque chose qui arrive avec probabilite 2−60

a toute seconde est 230 fois moins probable et on peut s’attendre a ce qu’il arrive une fois tousles 100 milliard d’annees.

L’approche concrete est importante en pratique, car les garanties concretes sont interessantespour les utilisateurs de ces schemas. Cependant, les garanties concretes precises sont difficiles adonner. De plus, on doit faire attention pour interpreter ces resultats de securite. Par exemple,dire qu’aucun adversaire s’executant pendant 5 ans peut casser un schema donne avec proba-bilite meilleure que ε pose la question : quel genre de puissance de calcul (e.g. ordinateur debureau, super-calculateur, reseau de centaines d’ordinateurs) suppose-t-on ? Est-ce que cela tienten compte les avancees futures de la puissance de calcul (Loi de Moore, qui double tous les 18mois) ? Est-ce que cette estimation suppose des algorithmes classiques, ou des implementationsoptimisees de l’attaque ? De plus, une telle garantie ne dit pas grand chose sur la probabilite desucces de l’adversaire s’executant pendant 2 ans (autre le fait qu’elle est au plus ε) et ne dit riensur la probabilite de succes d’un adversaire s’executant pendant 10 ans.

L’approche asymptotique. Comme on l’a partiellement indiquee plus haut, il y a des dif-ficultes theoriques et techniques a l’approche concrete. Ces difficultes peuvent etre evitees enpratique, mais quand la securite concrete n’est pas un soucis immediat, il est possible d’utiliserune approche asymptotique de la securite ; c’est l’approche choisie ici. Cette approche a ses ori-gines en theorie de la complexite et introduit un parametre de securite qui est un entier (note n)qui parametrise les schemas cryptographiques et les parties impliquees (les participants honneteset les adversaires). Quand les participants initialisent un schema (c’est-a-dire quand ils generentles cles), ils choisissent une valeur n pour le parametre de securite ; ici, on peut penser que ceparametre definit la longueur de la cle. Le parametre de securite est suppose etre connu parl’adversaire attaquant le schema, et on voit maintenant le temps de calcul de l’adversaire et saprobabilite de succes comme des fonctions de n plutot que des entiers. Alors :

12

1. On remplace ”adversaires efficaces” par algorithmes probabilistes s’executant en tempspolynomial en n. Ceci signifie qu’il existe un polynome p tel que l’adversaire s’execute entemps au plus p(n) quand le parametre de securite est n. On demande aussi - pour uneefficacite reelle - que les participants honnetes s’executent en temps polynomial, bien quel’on insiste sur le fait que l’adversaire peut etre plus puissant (et s’execute plus longtemps)que les parties honnetes.

2. On remplace la notion de ”petite probabilite de succes” avec la probabilite de succes estplus petite que l’inverse de tout polynome en n (voir plus loin). On dira dans ce cas, queces probabilites sont negligeables.

Soit PPT un raccourci pour ”probabilistic polynomial-time”. Une definition de securite asymp-totique prend la forme generale :

Un schema est sur si aucun PPT adversaire ne reussit a casser le schema avec probabilite auplus negligeable.

Cette notion de securite est asymptotique car la securite depend du comportement du schemapour des valeurs de n suffisamment grandes. L’exemple suivant explique ceci.

Exemple : Supposons que l’on ait un schema asymptotiquement sur. Alors il se peut qu’unadversaire s’executant en n3 minutes puisse reussir a casser le schema avec probabilite 240 · 2−n(qui est une fonction negligeable de n). Quand n ≤ 40, ceci signifie qu’un adversaire tournantpendant 403 minutes (environ 6 semaines) peut casser le schema avec probabilite 1, donc de tellesvaleurs de n ne sont pas tres utiles. Meme pour n = 50, un adversaire tournant en (50)3 minutes (3mois) peut casser le schema avec probabilite 1/1000, ce qui peut ne pas etre acceptable. D’autrepart, si n = 500, un adversaire tournant pendant 200 ans cassera le schema avec probabiliteenviron 2−500.

Comme le montre l’exemple precedent, on peut voir le parametre de securite comme unmecanisme qui permet aux parties honnetes d”affiner” la securite d’un schema a un niveau donne.(Augmenter le parametre de securite, augmente aussi le temps requis pour executer le schema,ainsi que la longueur de la cle, donc les participants souhaitent fixer le parametre de securiteaussi petit que possible sans que des attaques puissent avoir lieues.) Voir le parametre de securitecomme la longueur de la cle, ceci correspond au fait que le temps de l’attaque par recherchebrute grossit exponentiellement avec la longueur de la cle. La capacite d’augmenter la securiteen augmentant le parmetre de securite a des consequences importantes car elle permet auxparticipants de se proteger contre la croissance des ordinateurs. L’exemple suivant donne un sensa comment utiliser cela en pratique.

Exemple. Etudions l’effet de l’arrivee des super-calculateurs pourrait avoir sur la securite enpratique. Disons que l’on ait un schema cryptographique pour lequel les participants honnetestournent en 106 · n2 cycles, et pour lequel les adversaires tournent en 108 · n4 cycles pour reussira ”casser” le schema avec probabilite au plus 2−n/2.

Disons que toutes les parties ont des ordinateurs cadenses a 2GHz et que les parties honnetesfixent n = 80. Alors ces dernieres tournent pendant 106 · 6400 cycles, ou 3.2 secondes, et unadversaire s’executant pendant 108 · (80)4 cycles, environ 3 semaines, peut casser le schema avecprobabilite 2−40.

Disons que toutes les parties ont des ordinateurs cadenses a 8GHz et que les parties honnetesfixent n = 160. Alors ces dernieres tournent pendant le meme temps car 106 · (160)2 cyclescorrespond a 3.2 secondes. Alors que l’adversaire tournant pendant 108 · (160)4 cycles, environ 8millions d’annees, pourra casser le schema avec probabilite 2−80. L’effet d’un super-calculateura rendu la tache de l’adversaire plus difficile.

13

L’approche asymptotique en detail. On va maintenant traiter plus formellement les notionsde ”d’algorithmes en temps polynomial” et de ”probabilites de succes negligeables”.

Algorithmes efficaces. On a defini un algorithme efficace s’il s’execute en temps polynomial.Un algorithme A tourne en temps polynomial s’il existe un polynome p tel que pour tout entreex ∈ {0, 1}∗, le calcul de A(x) termine apres au plus p(|x|) pas de calcul. (Ici, |x| representela longueur en bits de la chaıne x.) On s’interesse aux adversaires dont le temps de calcul estpolynomial en le parametre de securite n. Comme on mesure le temps de calcul d’un algorithmeen fonction de la taille de son entree, on fournit quelque fois le parametre de securite commeentree ecrit en notation unaire (i.e., 1n, une chaıne de n 1). Les participants (ou plus precisementles algorithmes qu’ils executent) prennent d’autres entrees en plus du parametre de securite,comme le message a chiffrer et on autorise leur temps de calcul d’etre polynomial en la tailletotale de leurs entrees.

Par defaut, on autorise tous les algorithmes d’etre probabiliste. De tels algorithmes peuventtirer un bit aleatoire a chaque etape de calcul. On peut egalement voir ces algorithmes commeayant une autre entree avec des bits uniformement distribues. On considere des algorithmesprobabilistes pour deux raisons : d’une part, l’alea est essentiel en cryptographie (pour genererdes cles aleatoires par exemple) et donc les participants honnetes doivent etre probabilistes,etant donne cela, c’est aussi naturel de considerer des adversaires probabilistes (cela permet deconsiderer une classe plus importante d’adversaires).

Probabilite de succes negligeable. Une fonction negligeable est asymptotiquement plus petiteque l’inverse de n’importe quel polynome.

Definition 3. Une fonction f des nombres naturels vers les reels positifs est negligeable si pourtout polynome p positifs, il existe un entier N tel que pour tout entier n > N , f(n) < 1/p(n).

2.2.2 Definir la securite calculatoire de schema de chiffrement

Definition 4. Un schema de chiffrement a cle secrete est un tuple d’algorithmes probabilistes entemps polynomiaux (Gen,Enc,Dec) tels que :

1. L’algorithme de generation de cle Gen prend en entree 1n (c’est-a-dire le parametre desecurite ecrit en notation unaire afin que le temps d’execution de l’algorithme soit poly-nomial : il faut au moins ecrire la cle, i.e. n bits. Si on avait mis n, la taille en bits estlog2 n et on ne peut pas avoir Gen en temps polynomial pour ecrire les n bits.) et retourneune cle k ; on ecrit k ← Gen(1n) (pour montrer que cet algorithme est probabiliste). Onsuppose sans perte de generalite que toute cle k retournee par Gen satisfait |k| ≥ |n|.

2. L’algorithm de chiffrement Enc prend en entree une cle k et un message en clair m ∈ {0, 1}∗et retourne un chiffre c. Comme Enc peut etre probabiliste, on ecrit c← Enck(m).

3. L’algorithme de dechiffrement Dec prend en entree une cle k, un message chiffre c, etretourne un message clair m ou une erreur. On suppose que l’algorithme Dec est de-terministe, et on ecrit m := Deck(c) (on suppose Dec ne retourne pas une erreur). Onrepresente une erreur generique par le symbole ⊥.

On demande que pour tout entier n et toute cle k retournee par l’algorithme Gen(1n), et toutmessage m ∈ {0, 1}∗, Deck(Enck(m)) = m.

Si (Gen,Enc,Dec) est tel que pour toute cle k retournee par Gen(1n), l’algorithme Enck estseulement defini pour les messages m ∈ {0, 1}ℓ(n), alors on dit que (Gen,Enc,Dec) est un schemade chiffrement pour des messages de taille fixe de longueur ℓ(n).

14

Indistinguabilite. On decrit maintenant la definition de securite en decrivant l’experiencepour un schema de chiffrement Π = (Gen,Enc,Dec), un adversaire A, et un parametre de securiten :Experience d’indistinguabilite PrivKeav

A,Π(n) :

1. L’adversaire A recoit en entree 1n et retourne une paire de messages m0 et m1 tels que|m0| = |m1|.

2. une cle k est generee en executant Gen(1n), et un bit uniforme b ∈ {0, 1} est choisi. Lechiffre c← Enck(mb) est calcule et donne a A. On dit que c est le chiffre challenge.

3. A retourne un bit b′.

4. La sortie de l’experience est defini a 1 si b′ = b et 0 sinon. Si PrivKeavA,Π(n) = 1, on dit A

reussit.

La definition d’indistinguabilite dit qu’un schema de chiffrement est sur s’il n’existe pasd’adversaire PPT (probabiliste en temps polynomial) qui gagne l’experience precedente avecprobabilite significativement meilleure que deviner ce bit au hasard (ce qui donnera un resultatcorrect avec probabilite 1/2) :

Definition 5. Un schema de chiffrement a cle secrete Π = (Gen,Enc,Dec) garantit l’indistinguabilitedes chiffres en presence d’un adversaire passif, ou EAV (eavesdropper), si pour tout adversaire pro-babiliste en temps polynomial (PPT) A, il existe une fonction negligeable negl, telle que pour toutn,

Pr[PrivKeavA,Π(n) = 1] ≤ 1

2+ negl(n),

ou la probabilite est prise sur les randoms utilises par A et ceux utilises pendant l’experience (enchoisissant la cle k, le bit b et les aleas pour le chiffrement).

Une definition equivalente est que pour tout PPT adversaire se comporte de la meme faconqu’il voit un chiffrement de m0 ou un chiffrement de m1. Comme A ne retourne qu’un bit,”se comporter de la meme facon” signifie qu’il retourne 1 avec la meme probabilite dans lesdeux cas. Pour formaliser cela, on definit PrivKeav

A,Π(n, b) comme precedemment sauf que le bit best utilise (plutot que choisit au hasard). Soit outA(PrivK

eavA,Π(n, b)) representant le bit b′ de A

dans l’experience. La definition suivante affirme qu’aucun adversaire A ne peut determiner s’ils’execute contre l’experience outA(PrivK

eavA,Π(n, 0)) ou outA(PrivK

eavA,Π(n, 1)).

Definition 6. Un schema de chiffrement a cle secrete Π = (Gen,Enc,Dec) garantit l’indistinguabilitedes chiffres en presence d’un adversaire passif, si pour tout adversaire PPT A, il existe une fonctionnegligeable negl telle que :∣∣∣∣Pr[outA(PrivKeav

A,Π(n, 0)) = 1]− Pr[outA(PrivKeavA,Π(n, 1)) = 1]

∣∣∣∣ ≤ negl(n).

On laisse la demonstration d’equivalence en exercice.

2.2.3 Generateurs pseudo-aleatoires et stream cipher

Maintenant que nous avons defini la securite d’un schema de chiffrement, on peut se de-mander s’il existe des schemas de chiffrement surs au sens de la definition precedente. Avantd’en contruire, nous allons introduire la definition de generateurs pseudo-aleatoires (PRG) et destream-cipher (chiffrement par flot), qui sont des fonctions importantes pour les schemas de chif-frement a cle secrete. Ceci nous amenera a une discussion sur le pseudo-alea (pseudorandomness),qui joue un role fondamental en general et en particulier en chiffrement a cle secrete.

15

Un generateur pseudo-aleatoire G est un algorithme efficace et deterministe pour transformerune chaıne de bits uniforme et petite, appelee la graine seed, en une chaıne de sortie plus longue”qui semble uniforme” (pseudo-aleatoire). Autrement dit, un generateur pseudo-aleatoire utiliseune petite quantite de ”vrai alea” afin de generer une grande quantite de pseudo-alea. C’est utilequand une grande quantite de bits (semblant) aleatoires sont necessaires, car generer des bitsvraiment aleatoires est difficile et lent.

Par exemple, les generateurs ont ete utilises pour des simulations statistiques. Des chercheursont proposes differents tests statistiques qu’un generateur doit passer pour etre considere comme”bon”. Par exemple, le premier bit de sortie d’un generateur pseudo-aleatoire doit etre egal a 1avec probabilite (proche) 1/2 (ou la probabilite est prise sur l’ensemble des choix uniformes dela graine, car pour une chaıne aleatoire le premier bit est un 1 avec probabilite 1/2. D’autrestests plus compliques ont ete concus. La securite peut etre compromise dans les utilisationsde generateurs pseudo-aleatoires cryptographiques si l’adversaire peut distinguer la sortie dugenerateur d’une chaıne aleatoire et on ne sait pas a l’avance quelle strategie il va utiliser.

Les considerations precedentes ont motive une approche cryptographique pour definir lesgenerateurs pseudo-aleatoires au debut des annees 1980. La realisation de base est qu’un bongenerateur pseudo-aleatoire doit passer tous les tests statistiques (efficaces). C’est-a-dire que,pour tout test statistique efficace (ou distingueur D), la probabilite que D retourne 1 quand ilrecoit la sortie d’un generateur pseudo-aleatoire doit etre proche de la probabilite que D retourne1 quand il recoit une chaıne uniforme de bits de la meme longueur. Informellement, la sortie dugenerateur pseudo-aleatoire doit ”ressembler” a une chaıne uniforme pour tout observeur efficace.

(On insiste que formellement, il n’y a pas de sens de dire qu’une chaıne fixee est ”pseudo-aleatoire”, de la meme facon qu’il n’y a pas de sens a dire qu’une chaıne fixe est aleatoire. Lapropriete de ”pseudo-aleatoire” est une propriete des distributions des chaınes de bits. Nean-moins, on dira informellement qu’une chaıne echantillonnee selon la distribution uniforme, une”chaıne uniforme”, et une chaıne retournee par un generateur pseudo-aleatoire de ”chaıne pseudo-aleatoire”.)

Une autre direction est de definir ce que cela signifie pour une distribution d’etre pseudo-aleatoire. Soit Dist une distribution sur les chaınes de bits de longueur ℓ. (Ceci signifie que Distassigne une probabilite a chacune des chaınes de {0, 1}ℓ ; echantillonner dans Dist signifie quel’on choisit une chaıne de ℓ bits selon cette distribution de probabilite.) Informellement, Dist estpseudo-aleatoire si l’experience dans laquelle une chaıne est choisie selon Dist est indistinguablede l’experience ou une chaıne aleatoire de longueur ℓ est choisie. (Plus precisement, comme onest dans une approche asymptotique, pour parler de pseudo-alea, il faut considerer une suitede distributions Dist = {Distn}, ou Distn est une distribution pour un parametre de securiten.) Plus precisement, il doit etre impossible pour tout adversaire en temps polynomial de dire(mieux qu’en devinant au hasard) s’il a recu une chaıne de bits echantillonnee selon Dist, ou s’il arecu une chaıne aleatoire (uniforme). Ceci signifie qu’une chaıen pseudo-aleatoire est aussi bonnequ’une chaıne aleatoire. Indistinguabilite est une relaxation calculatoire de la securite parfaite.

Definition 7. Soit ℓ un polynome et soit G un algorithme deterministe en temps polynomial telque pour tout n et toute chaıne s ∈ {0, 1}n, le resultat G(s) est une chaıne de longueur ℓ(n). Ondit que G est un generateur pseudo-aleatoire s’il satisfait les conditions suivantes :

1. (Expansion :) Pour tout n, ℓ(n) > n.

2. (Pseudo-alea :) Pour tout algorithme PPT D, il existe une fonction negligeable negl,telle que :

|Pr[D(G(s)) = 1]− Pr[D(r) = 1]| ≤ negl(n),

ou la premiere probabilite porte sur un choix uniforme de s ∈ {0, 1}n et l’alea de D, et laseconde sur un choix uniforme de r ∈ {0, 1}ℓ(n) et les aleas de D.

16

Un stream-cipher est une paire d’algorithmes deterministes (Init,GetBits) ou :— Init prend en entree une graine s et optionnellement un vecteur d’initialisation IV et

retourne un etat initial st0.— GetBits prend en entree un etat sti et retourne un bit y et un etat mis a jour sti+1. (En

pratique y peut etre un bloc de plusieurs bits ; on traite ici y de longueur 1 pour plus degeneralite et simplicite.

Theoreme 4. Si G est un generateur pseudo-aleatoire, la construction d’un stream-cipher estun schema de chiffrement a cle secrete qui garantit l’indistinguabilite des chiffres en presenced’un adversaire passif.

Demonstration. Soit Π la construction precedente de stream-cipher. On montre que Π satisfaitla definition de securite. En particulier, on va montrer que pour tout adversaire probabiliste entemps polynomial A, il existe une fonction negligeable negl telle que :

Pr[PrivKeavA,Π(n) = 1] ≤ 1

2+ negl(n).

L’intuition est que si Π utilise un pad uniforme a la place du pad pseudo-alea G(k), le schemaresultant sera identique au one-time pad et A sera incapable de deviner correctement avec uneprobabilite meilleure que 1/2. Ainsi, si l’inegalite precedente n’est pas verifiee, alors A devraimplicitement savoir distinguer la sortie de G d’une chaıne aleatoire. On va rendre cette intuitionexplicite en exhibant une reduction ; c’est-a-dire en montrant comment utiliser A pour construireun distingueur efficace D, avec la propriete que la capacite de D a distinguer les sorties de Gd’une chaıne aleatoire est directement reliee a la capacite de A a determiner quel message a etechiffre par Π. La securite de G se deduira de celle de Π.

Soit A un adversaire PPT arbitraire. On va construire un distingueur D qui prend en entreeune chaıne w comme entree, et dont le but est de determiner si w a ete choisi uniformement (i.e.est une ”chaıne uniforme”) ou si w est une chaıne pseudo-aleatoire (i.e. w = G(k) ou k a etechoisie uniformement). On construit D de facon a emuler l’experience de l’adversaire passif pourA, et en observant si A reussit ou non. Si A reussit, alors D devine que w doit etre une chaınepseudo-aleatoire, alors que si A ne reussit pas, D devinera que w est une chaıne aleatoire. Endetail :

Distingueur D :D recoit en entree une chaıne w ∈ {0, 1}ℓ(n). (On suppose que n peut etre determine a partir deℓ(n).)

1. Executer A(1n) pour obtenir une paire de messages m0,m1 ∈ {0, 1}ℓ(n).2. Choisir un bit b ∈ {0, 1} uniformement. Poser c := w ⊕mb.

3. Donner c a A et obtenir le bit b′. Retourner 1 si b = b′, 0 sinon.

Clairement, D s’execute en temps polynomial (en supposant que A le fait aussi).Avant d’analyser le comportement de D, on definit un schema de chiffrement modifie Π =

(Gen, Enc, Dec) qui est exactement comme le one-time pad, sauf que l’on incorpore un parametre

de securite qui determine la longueur du message a chiffrer. C’est-a-dire, Gen(1n) retourne unecle uniforme k de longueur ℓ(n), le chiffrement du message m ∈ {0, 1}ℓ(n) en utilisant la clek ∈ {0, 1}ℓ(n) est le chiffre c := k ⊕ m. (Le dechiffrement est execute comme d’habitude.) Lasecurite parfaite du one-time pad implique :

Pr[PrivKeavA,Π

(n) = 1] ≤ 1

2.

Pour analyser le comportement de D, les observations principales sont :

17

1. Si w est choisi uniformement dans {0, 1}ℓ(n), alors la vue de A quand il est executecomme sous-routine de D est distribuee de facon identique a la vue de A dans l’experiencePrivKeav

A,Π(n). Ceci est vrai car quand A est execute par D, A recoit un chiffre c = w⊕mb

ou w ∈ {0, 1}ℓ(n) est uniforme. Comme D retourne 1 exactement quand A reussit dansl’experience, on a par consequent :

Prw←{0,1}ℓ(n)

[D(w) = 1] = Pr[PrivKeavA,Π

(n) = 1] =1

2.

(L’espace de la premiere probabilite porte sur w choisit uniformement dans {0, 1}ℓ(n).)2. Si w est genere en choisissant k ∈ {0, 1}n, puis w := G(k), la vue de A quand il est

execute comme une sous-routine par D est distribue de facon identique a la vue de A dansl’experience PrivKeav

A,Π(n). Ceci, parce que A recoit un chiffre c = w ⊕ mb ou w = G(k)pour un k ∈ {0, 1}n uniforme. Ainsi,

Prk←{0,1}n

[D(G(k)) = 1] = Pr[PrivKeavA,Π(n) = 1].

Comme G est un generateur pseudo-aleatoire (et comme D s’execute en temps polynomial),on sait qu’il existe une fonction negligeable negl telle que :∣∣∣∣ Pr

w←{0,1}ℓ(n)[D(w) = 1]− Pr

k←{0,1}n[D(G(k)) = 1]

∣∣∣∣ ≤ negl(n).

En utilisant les equations precedentes, on en deduit :∣∣∣∣12 − Pr[PrivKeavA,Π

(n) = 1]

∣∣∣∣ ≤ negl(n),

ce qui implique que Pr[PrivKeavA,Π

(n) = 1] ≤ 12 + negl(n). Comme A etait un adversaire arbitraire

PPT, ceci complete la preuve que Π est un schema de chiffrement indistinguable en presenced’un adversaire passif.

2.2.4 Securite CPA (attaque ) clairs choisis)

Les attaques a clairs choisis prennent en compte la capacite d’un adversaire a exercer uncontrole (partiel) sur les participants honnetes du chiffrement. On imagine un scenario danslequel deux parties partagent une cle k, et l’attaquant peut demander a ces parties de chiffrerles messages m1,m2, . . . (en utilisant k) et en envoyant les chiffres correspondant sur le canalque l’adversaire observe. Un instant plus tard, l’attaquant observe un chiffre correspondant a unmessage m chiffre sous la meme cle k ; on supposera meme que l’adversaire sait que m est m0 oum1. La securite contre les attaques a clairs choisis signifie que meme dans ce cas, l’attaquant nepeut pas dire lequel des deux messages est chiffre avec une probabilite meilleure que de devinerau hasard.

Est-ce que ce type d’attaque est realiste dans la vie courante ? Durant la Seconde GuerreMondiale, les Britanniques ont places des mines a certaines localisations, sachant que quand lesAllemands trouveront ces mines, les localisations seront chiffrees et envoyees au quartier general.Ces messages chiffres ont ete utilises par les cryptanalystes de Bletchley Park pour casser lesschemas de chiffrement allemands. Un autre exemple est decrit par l’histoire de la bataille deMidway. En 1942, les cryptanalystes americains de la Navy ont interceptes des messages chiffres

18

des Japonais qu’ils ont ete capable de dechiffrer partiellement. Les resultats indiquaient que lesJaponais planifiaient une attaque sur AF, ou AF etait un morceau du chiffre que les Americainsne pouvaient pas dechiffrer. Pour certaines raisons, les Americains pensaient que les ıles Midwayetait la cible. Malheureusement, leurs tentatives pour convaincre Washington que c’etait le cas,n’ont pas reussies ; le general pensait que Midway ne pourrait pas etre la cible. Les cryptanalystesamearicains ont alors concu le plan suivant : Ils ont demande aux forces americaines a Midwayd’envoyer un faux message que les ressources en eau fraıche etaient basses. Les Japonais ontintercepte le message et immediatement rapportes a leurs superieurs que ”AF avait des ressourcesen eau basse”. Les cryptanalystes americains avaient leur preuve de la localisation. Le resultat aete que Midway a ete sauve, et les Japonais ont eu des pertes importantes. Cette bataille a etele tournant de la guerre du Pacifique entre Americains et Japonais.

On modelise la definition formelle d’attaque a clairs choisis en donnant acces a l’adversaireA aun oracle de chiffrement, accede en boite noire, qui chiffre des messages pour A en choisissant unecle k qui est inconnue deA. C’est-a-dire qu’on image queA a acces a un ”oracle”Enck(·) ; quandAenvoie un message m en entree, l’oracle retourne un chiffre c ← Enck(m). (Enc est probabiliste,et l’oracle choisit un nouvel alea a chaque fois qu’il repond a une question.) L’adversaire estautorise d’acceder de facon adaptative a l’oracle de chiffrement (les prochaines questions peuventdependre des reponses de l’oracle) aussi souvent qu’il le veut (polynomiallement)

Experience d’indistibgualite CPA PrivKcpaA,Π(n) :

1. Une cle k est generee en executant Gen(1n).

2. L’adversaire A prend en entree 1n et a acces a l’oracle Enck(·), et retourne une paire demessages m0 et m1 de meme longueur.

3. Un bit b ∈ {0, 1} est choisi uniformement, et un chiffre c ← Enck(mb) est calcule etretourne a A.

4. L’adversaire A continue d’interagir avec l’oracle de chiffrement et retourne un bit b′.

5. La sortie de l’experience est definie a 1 si b = b′ ; 0 sinon. Dans le premier cas, on dit queA gagne le jeu de securite.

Definition 8. Un schema de chiffrement a cle secrete Π = (Gen,Enc,Dec) garantit l’indistinguabilitedes chiffres contre des attaques a clairs choisis, ou CPA-sur, si pour tout adversaire probabiliste entemps polynomial PPT A, il existe une fonction negligeable negl telle que :

Pr[PrivKcpaA,Π(n) = 1] ≤ 1

2+ negl(n),

ou la probabilite est prise sur les aleas de A ainsi que les aleas de l’experience.

2.2.5 Fonctions pseudo-aleatoires et chiffrement par bloc

Les fonctions pseudo-aleatoires (PRF : Pseudo-Random Functions) generalisent la notion degenerateurs pseudo-aleatoires. Maintenant, au lieu de considerer des chaınes de bits ”ressemblanta des chaınes uniformes”, on considere des fonctions ressemblant a des fonctions aleatoires. Celan’a pas de sens pour une fonction fixe f : {0, 1}∗ → {0, 1}∗ d’etre pseudo-aleatoire, donc on serefere ici a des distributions comme precedemment sur l’ensemble de toutes les fonctions. Unetelle distribution est induite en considerant des fonctions a cle.

Une fonction a cle F : {0, 1}∗ × {0, 1}∗ → {0, 1}∗ est une fonction a deux entrees ou lepremier argument est appele la cle et represente par k. On dit que F est efficace s’il existeun algorithme en temps polynomial qui calcule F (k, x) etant donnee k et x (polynomial en lataille des entrees, c’est-a-dire polynomial en |k|+ |x| la taille en bits de la cle et de l’entree). En

19

pratique, k est choisie uniformement et on s’interesse a la fonction Fk : {0, 1}∗ → {0, 1}∗ definiepar Fk(x) = F (k, x). Le parametre de securite n definit la longueur de la cle ℓkey, de l’entree ℓinet de la sortie ℓout pour k ∈ {0, 1}ℓkey(n), x ∈ {0, 1}ℓin(n) et F (k, x) ∈ {0, 1}ℓout(n). On dit que Fpreserve la longueur si ℓkey(n) = ℓin(n) = ℓout(n) = n. C’est-a-dire pour une cle k ∈ {0, 1}n, onobtient une fonction Fk qui envoie les chaınes de n bits vers les chaınes de n bits.

Une fonction a cle F induit une distribution naturelle sur les fonctions donnees en choisissantuniformement k ∈ {0, 1}n et en considerant la fonction resultante a une entree Fk. On dit que Fest pseudo-aleatoire si la fonction Fk (pour une cle uniforme k) est indistinguable d’une fonctionchoisie uniformement au hasard dans l’ensemble de toutes les fonctions ayant le meme ensemblede depart et d’arrivee. ; c’est-a-dire qu’il n’existe pas d’adversaire PPT capable de distinguer,dans un sens que nous donnerons plus tard, s’il est en train d’interagir avec Fk (pour une cle kuniforme) ou f (ou f est choisie uniformement dans l’ensemble des fonctions de n bits vers nbits.)

Comme choisir une fonction au hasard est moins intuitif qu’une chaıne de bits au hasard,nous allons decrire cela ici. Considerons l’ensemble Funcn, toutes les fonctions de n bits vers nbits. Cet ensemble est fini et choisir uniformement une fonction signifie choisir une fonction danscet ensemble. Quelle est la taille de Funcn ? Une fonction f est decrite par sa valeur sur chaquepoint du domaine d’entree. On peut donc voir une telle fonction comme une grande table quistocke la valeur f(x) a la case x. Donc, cette fonction a 2n entrees et chacune fait n bits. Donc,il existe une bijection entre une fonction et les tables et |Funcn| = 2n·2

n

.On pourrait donner acces au distingueur a la table de Fk et lui demander de distinguer cette

chaıne d’une chaıne aleatoire. Mais, comme le temps de calcul deD est borne (polynomiallement),ca ne fonctionne pas. On va donc donner acces a l’adversaire a certaines valeurs de la fonctionFk via un oracle. On mettra les acces a l’oracle en exposant de D.

Definition 9. Soit F : {0, 1}∗ × {0, 1}∗ → {0, 1}∗ une fonction efficace a cle preservant la lon-gueur. F est une fonction pseudo-aleatoire si pour tout distingueur PPT D, il existe une fonctionnegligeable negl telle que :∣∣∣∣Pr[DFk(·)(1n) = 1]− Pr[Df (1n) = 1]

∣∣∣∣ ≤ negl(n),

ou la premiere probabilite porte sur le choix uniforme de k ∈ {0, 1}n et les aleas de D, alorsque la seconde sur le choix de f ∈ Funcn et les aleas de D.

2.2.6 Permutation pseudo-aleatoire et Block Ciphers

On remplace l’ensemble des fonctions Funcn par l’ensemble des permutations Permn qui estde plus petite taille (2n)! (seulement !). On donne aussi acces a un oracle de dechiffrement quisait inverser la fonction :

Definition 10. Soit F : {0, 1}∗ × {0, 1}∗ → {0, 1}∗ une permutation efficace a cle preservant lalongueur. F est une permutation pseudo-aleatoire (fortement si on donne acces a l’oracle d’inversion)si pour tout distingueur PPT D, il existe une fonction negligeable negl telle que :∣∣∣∣Pr[DFk(·),F−1

k (·)(1n) = 1]− Pr[Df,f−1

(1n) = 1]

∣∣∣∣ ≤ negl(n),

ou la premiere probabilite porte sur le choix uniforme de k ∈ {0, 1}n et les aleas de D, alorsque la seconde sur le choix de f ∈ Funcn et les aleas de D.

20

2.2.7 Securite d’un schema

Soit la construction PRF-Enc suivante : Soit une famille de fonction pseudo-aleatoire F . Ondefinit un chiffrement a cle publique pour des messages de longueur n de la facon suivante :

— Gen : sur l’entree 1n, choisir uniformement une cle k ∈ {0, 1}n et la retourner.— Enc : cet algorithme prend en entree une cle k ∈ {0, 1}n, un message m ∈ {0, 1}n, choisit

uniformement un random f ∈ {0, 1}n et calcule le chiffre :

c := (r, Fk(r)⊕m).

— Dec : sur l’entree la cle k et le chiffre c = (r, s), retourne le message clair

m := Fk(r)⊕ s.

Theoreme 5. Si F est une fonction pseudo-aleatoire, alors la construction PRF-Enc est unschema de chiffrement a cle secrete CPA-sur pour des messages de longueur n.

Demonstration. Soit Π = (Gen, Enc, Dec) un schema de chiffrement qui est exactement le memeque Π = (Gen,Enc,Dec), sauf que l’on remplace Fk par une fonction aleatoire f . C’est-a-dire

que Gen(1n) choisit une fonction aleatoire dans f ∈ Funcn, Enc chiffre comme Enc sauf que lafonction f est utilisee a la place de Fk.

Soit un adversaire probabiliste en temps polynomial A et soit q(n) une borne superieure sur lenombre de requetes que A(1n) fait a l’oracle de chiffrement. (Remarquer que q doit etre majoreepar un polynome.) Dans une premiere etape de la preuve, nous allons montrer qu’il existe unefonction negligeable negl telle que :∣∣∣∣Pr[PrivKcpa

A,Π(n) = 1]− Pr[PrivKcpa

A,Π(n) = 1]

∣∣∣∣ ≤ negl(n).

On prouve ceci par reduction. On utilise A pour construire un distingueurD contre la fonctionpseudo-aleatoire F . Le distingueur D a un acces a un oracle calculant une fonction O, et sonbut est de determiner si cette fonction est ”pseudo-aleatoire” (i.e. egale a Fk pour k ∈ {0, 1}n)ou ”aleatoire” (i.e. egale a f pour f ∈ Funcn uniforme). Pour ce faire, D va emuler l’experiencePrivKcpa pour A de la facon suivante, et observe si A reussit ou non. Si A reussit, alors D devineque son oracle est une fonction pseudo-aleatoire, alors que si A ne reussit pas, alors D devineque son oracle doit etre une fonction aleatoire.

Distingueur D :D recoit en entree 1n et a acces a un oracle O : {0, 1}n → {0, 1}n.

1. Executer A(1n). Chaque fois que A pose une question a l’oracle pour chiffrer un messagem ∈ {0, 1}n, repondre a cette question de la facon suivante :

(a) Choisir uniformement r ∈ {0, 1}n

(b) Poser la question O(r) et obtenir la reponse y.

(c) Retourner le chiffre ⟨r, y ⊕m⟩ a A.2. Quand A retourne deux messages m0,m1 ∈ {0, 1}n, choisir un bit b ∈ {0, 1} uniformement

et :

(a) Choisir uniformement r ∈ {0, 1}n

(b) Poser la question O(r) et obtenir la reponse y.

(c) Retourner le chiffre ⟨r, y ⊕mb⟩ a A.

21

3. Continuer de repondre aux questions de A jusqu’a ce qu’il retourne un bit b′. Retourner1 si b′ = b et 0 sinon.

D s’execute en temps polynomial comme A. Les points importants sont les suivants :

1. Si l’oracle D est une fonction pseudo-aleatoire, alors la vue de A quand il s’execute commeune sous-routine par D est distribuee identiquement a la vue de A dans l’experiencePrivKcpa

A,Π(n). En effet, dans ce cas, une cle k est choisie uniformement au hasard et en-suite, tout chiffrement est effectue en choisissant un random uniforme r, et en calculanty := Fk(r), enfin le chiffre est (r, y ⊕ m), exactement comme dans la construction. Parconsequent :

Prk←{0,1}n

[DFk(·)(1n) = 1] = Pr[PrivKcpaA,Π(n) = 1],

ou la cle k est choisie uniformement a gauche.

2. Si l’oracle D est une fonction aleatoire, alors la vue de A quand il est execute comme sous-routine par D est distribuee identiquement a la vue de A dans l’experience PrivKcpa

A,Π(n).

On peut le voir comme precedemment, avec la seule difference que f ∈ Funcn au lieu deFk. Ainsi,

Prf←Funcn

[Df(·)(1n) = 1] = Pr[PrivKcpa

A,Π(n) = 1],

ou f est choisie uniformement dans Funcn.

Par hypothese que F est une fonction pseudo-aleatoire (et comme D est efficace), il existeune fonction negligeable negl pour laquelle :∣∣∣∣ Pr

k←{0,1}n[DFk(·)(1n) = 1]− Pr

f←Funcn[Df(·)(1n) = 1]

∣∣∣∣ ≤ negl(n).

En combinant les equations precedentes, on obtient :∣∣∣∣Pr[PrivKcpaA,Π(n) = 1]− Pr[PrivKcpa

A,Π(n) = 1]

∣∣∣∣ ≤ negl(n).

Dans la seconde partie de la preuve, nous allons montre que :

Pr[PrivKcpa

A,Π(n) = 1] ≤ 1

2+

q(n)

2n.

(On rappelle que q(n) est une borne sur le nombre de requetes de chiffrement fait par A. Laprobabilite precedente est vraie meme si on ne place aucune restriction sur l’adversaire A.) Pourvoir que cette inegalite est vraie, il suffit d’observer que chaque fois qu’un message est chiffre dansl’experience Pr[PrivKcpa

A,Π(n) = 1] (soit par l’oracle de chiffrement ou quand le chiffre challenge

est calcule), un random r ∈ {0, 1}n est choisi uniformement et le chiffre est (r, f(r)⊕m). Soit r∗

represente la chaıne de bits aleatoire utilisee quand on genere le chiffre challenge (r∗, f(r∗)⊕mb).Il y a alors deux options :

1. Soit la valeur r∗ n’a jamais ete utilisee pour repondre aux requetes de A par l’oracle dechiffrement : Dans ce cas, A n’apprend rien sur f(r∗) des interactions avec l’oracle de chif-frement (car f est une vraie fonction aleatoire). Ceci signifie que, tant que A est concerne,la valeur f(r∗) qui est XORee avec mb est distribuee uniformement et independammentdu reste de l’experience, et donc la probabilite que A retourne b′ = b est dans ce casexactement 1/2 (comme dans le cas du one-time pad).

22

2. Soit la valeur r∗ est utilisee quand on a repondu a au moins une requete par l’oracle :Dans ce cas, A peut aisement determiner quand m0 ou m1 est chiffre. Ceci parce quel’oracle de chiffrement retourne le chiffre (r∗, s) en reponse au chiffrement du message met l’adversaire sait que f(r∗) = s⊕m.

Cependant, comme A fait au plus q(n) requetes a son oracle de chiffrement (et donc auplus q(n) valeurs r sont utilisees pour repondre aux requetes de A), et comme r∗ est choisiuniformement au hasard dans {0, 1}n, la probabilite de cet evenement est au plus q(n)/2n.

Soit Repeat, l’evenement que r∗ est utilise par l’oracle de chiffrement quand il repond a aumoins une requetes de A. Comme on l’a vue precedemment, la probabilite de Repeat est au plusq(n)/2n, la probabilite que A reussisse dans PrivKcpa

A,Πsi Repeat n’a pas eu lieu est exactement

1/2. Donc,

Pr[PrivKcpa

A,Π(n) = 1]

= Pr[PrivKcpa

A,Π(n) = 1 ∧ Repeat] + Pr[Pr[PrivKcpa

A,Π(n) = 1 ∧ Repeat] ∧ Repeat]

≤ Pr[Repeat] + Pr[PrivKcpa

A,Π(n) = 1 ∧ Repeat] ≤ q(n)

2n + 12 .

En combinant cela avec la premiere inegalite, on obtient :

Pr[PrivKcpaA,Π(n) = 1] ≤ 1

2+

q(n)

2n+ negl(n),

ou q(n)/2n est negligeable et comme la somme de deux fonctions negligeables est negligeable, ona bien le resultat attendu.

Theoreme 6. Si F est une fonction pseudo-aleatoire, alors le mode CTR est CPA-sur.

Demonstration. On suit le meme exemple que dans la preuve precedente : on remplace F avecue fonction aleatoire et ensuite on analyse le schema resultant. Soit Π = (Gen,Enc,Dec) unschema (sans etat) de chiffrement en mode compteur (c’est-a-dire qu’on genere un alea differentpour chaque nouveau message que l’on veut chiffrer et qu’on n’incremente pas simplement un

compteur entre les different message), et soit Π = (Gen, Enc, Dec) un schema de chiffrement qui

est identique a Π sauf qu’il utilise une fonction aleatoire a la place de Fk. C’est-a-dire que Gen(1n)

choisit uniformement une fonction f ∈ Funcn, et Enc chiffre comme Enc sauf qu’il utilise f a la

place de Fk. (Encore une fois, ni Gen, ni Enc n’est efficace (car la table pour stocker la fonctionf est enorme) mais cela ne compte pas dans la definition de l’experience mettant en jeu Π.)

Fixons un adversaire PPT A, et soit q(n) un polynome bornant superieurement le nombre derequetes a l’oracle de chiffrement fait par A(1n) ainsi que le nombre maximal de blocs dans m0

et m1. Dans la premiere etape de la preuve, on affirme qu’il existe une fonction negligeable negltelle que : ∣∣∣∣Pr[PrivKcpa

A,Π(n) = 1]− Pr[PrivKcpa

A,Π(n) = 1]

∣∣∣∣ ≤ negl(n).

Ceci est prouve par reduction de facon similaire a ce qui est fait dans la preuve precedente etlaisser au lecteur.

On affirme ensuite que

Pr[PrivKcpa

A,Π(n) = 1] <

1

2+

2q(n)2

2n.

23

En combinant avec l’equation precedente, on obtient :

Pr[PrivKcpaA,Π(n) = 1] <

1

2+

2q(n)2

2n+ negl(n).

Comme q est un polynome, 2q(n)22n est negligeable et ceci termine la preuve.

On va prouver la seconde inegalite. Fixons une valeur n pour le parametre de securite. Soitℓ∗ ≤ q(n) representant la longueur (en blocs) des messages m0 et m1 retournee par A dansl’experience PrivKcpa

A,Π(n), et soit ctr∗ la valeur initiale utilisee pendant la generation du chiffre

challenge. De facon similaire, soit ℓi ≤ q(n) la longueur (en blocs) de la iieme requete a l’oraclede chiffrement faite par A et soit ctri la valeur initiale pour repondre a cette requete. Quand onrepond a la iieme requete, f est appliquee aux valeurs ctri + 1, . . . , ctri + ℓi. Quand on reponda la requete de challenge, f est appliquee aux valeurs ctr∗i + 1, . . . , ctr∗i + ℓ∗, et le iieme bloc estcalcule en XORant f(ctr∗ + i) avec le iieme bloc de message. Il y a deux cas :

1. Il n’existe pas i, j, j∗ ≥ 1 (avec j ≤ ℓi et j∗ ≤ ℓ∗) tels que ctri+j = ctr∗+j∗ : Dans ce cas,

les valeurs f(ctr∗+1), . . . , f(ctr∗+ℓ∗) utilisees pour chiffrer le challenge sont uniformementdistribuees et independante du reste de l’experience car f n’a pas ete appliquee a desentrees quand on chiffre par l’oracle de chiffrement. Ceci signifie que le chiffre challengeest calcule en XORant un flot de bits uniformes avec le message mb, et donc la probabiliteque A retourne b′ = b est exactement 1/2 (comme dans le cas du one-time pad).

2. Il existe i, j, j∗ ≥ 1 (avec j ≤ ℓi et j∗ ≤ ℓ∗) tels que ctri + j = ctr∗ + j∗ : On represente

cet evenement par Overlap. Dans ce cas, A peut potentiellement determiner lequel desdeux messages a ete chiffre, car A peut deduire la valeur de f(ctri + j) = f(ctr∗ + j∗) desrequete de l’oracle a sa iieme requete.

Analysons maintenant la probabilite que Overlap ait lieu. La probabilite est maximisee si ℓ∗ etchaque ℓi sont grands et donc supposons que ℓ

∗ = ℓi = q(n) pour tout i. Soit Overlapi l’evenementque la suite ctri+1, . . . , ctri+ q(n) recouvre la suite ctr∗+1, . . . , ctr∗+ q(n) : c’est-a-dire Overlapest l’evenement que Overlapi apparaıt pour un i. Comme il y a au plus q(n) requetes a l’oracle,la borne de l’union donne :

Pr[Overlap] ≤q(n)∑i=1

Pr[Overlapi].

Fixons ctr∗, l’evenement Overlapi a lieu exactement quand ctri satisfait :

ctr∗ − q(n) + 1 ≤ ctri ≤ ctr∗ + q(n)− 1.

Comme il y a 2q(n) − 1 valeurs de ctri pour lesquelles Overlapi a lieu, et ctri est choisiuniformement dans {0, 1}n, on voit que :

Pr[Overlapi] =2q(n)− 1

2n<

q(n)

2n.

En combinant avec l’equation (de la borne de l’union), on obtient : Pr[Overlap] < 2q(n)/2n.On peut maintenant facilement borner la probabilite de succes de A :

Pr[PrivKcpa

A,Π(n) = 1] = Pr[PrivKcpa

A,Π(n) = 1 ∧ Overlap] + Pr[PrivKcpa

A,Π(n) = 1 ∧ Overlap]

≤ Pr[PrivKcpa

A,Π(n) = 1 ∧ Overlap] + Pr[Overlap]

< 12 + 2q(n)2

2n .

Ceci conclut la preuve.

24

2.3 Code d’authentification de messages

Definition 11. Un code d’authentification de messages (ou MAC) consiste en 3 algorithmesprobabilistes en temps polynomial (Gen,Mac,Vrfy) tels que :

1. L’algorithme de generation de cle, Gen prend en entree le parametre de securite 1n estretourne une cle k telle que |k| ≥ n.

2. L’algorithme de generation du tag Mac prend en entree la cle k et un message m ∈ {0, 1}∗et retourne un tag t. Comme cet algorithme peut etre probabiliste, on ecrit t← Mack(m).

3. L’algorithme de verification deterministe Vrfy qui prend en entree la cle k, un messagem ∈ {0, 1}∗ et un tag t. Il retourne un bit b avec b = 1, i.e. valide et b = 0, non valide. Onecrit b := Vrfyk(m, t).

On exige que pour tout n, chaque cle retournee par Gen(1n), et tout message m ∈ {0, 1}∗, onait Vrfyk(m,Mack(m)) = 1.

S’il existe une fonction ℓ telle que pour tout k retournee par Gen(1n), l’algorithme Mack estseulement defini pour des messages m ∈ {0, 1}ℓ(n), alors on dit que le schema est un MAC pourdes messages de longueur fixe de longueur ℓ(n).

La definition de securite d’un MAC utilise l’experience suivante pour un code d’authentifica-tion de message Π = (Gen,Mac,Vrfy), un adversaire A et un parametre de securite :

Experience forger Mac− forgeA,Π(n) :

1. Une cle k est generee en executant Gen(1n).

2. L’adversaire A recoit la cle k et a acces a l’oracle Mack(·). L’adversaire retourne a la fin(m, t). Soit Q l’ensemble de toutes les requetes faites par A.

3. A reussit si et seulement si (1) Vrfyk(m, t) = 1 et m ∈ Q. Dans ce cas, on definit la sortiede l’experience a 1.

Un MAC est sur s’il n’existe pas d’adversaire efficace pour reussir l’experience precedenteavec une probabilite non-negligeable.

Definition 12. Un code d’authentification de messages Π = (Gen,Mac,Vrfy) est existentiellementunforgeable contre des attaques a messages choisis ou sur si pour tout adversaire probabiliste entemps polynomial A, il existe une fonction negligeable negl telle que

Pr[Mac− forgeA,Π(n) = 1] ≤ negl(n).

Considerons la construction PRF-MAC : soit F une fonction pseudo-aleatoire. Definissons unMAC pour des messages de longueur fixe n :

— Mac : algorithme qui prend en entree une cle k ∈ {0, 1}n et un message m ∈ {0, 1}n etretourne un tag t := Fk(m). (Si |m| = |k|, ne rien retourner.)

— Vrfy : algorithme qui prend en entree une cle k ∈ {0, 1}n, un message m ∈ {0, 1}n et un

tag t ∈ {0, 1}n et retourne 1 si et seulement si t?= Mack(m). (Si |m| = |k|, retourner 0.)

Theoreme 7. Si F est une fonction pseudo-aleatoire, la construction PRF-MAC est un MACsur pour des messages de taille fixe n.

Demonstration. Comme dans les utilisations precedentes de fonctions pseudo-aleatoires, la preuvesuit le modele d’analyser dans un premier temps la securite du schema en utilisant une fonctionvraiment aleatoire, et ensuite en considerant le resultat en remplacant la fonction vraimentaleatoire par une fonction pseudo-aleatoire.

25

Soit A un adversaire probabiliste en temps polynomial. Considerons le code d’authentification

de message Π = (Gen, Mac, Vrfy) qui est le meme que Π = (Mac,Vrfy) utilise dans la constructionPRF-MAC, sauf que l’on remplace Fk par une fonction aleatoire f choisie uniformement au

hasard dans l’ensemble de toutes les fonctions. C’est-a-dire que Gen(1n) commence par choisir

une fonction aleatoire f ∈ Funcn uniformement et Mac calcule un tag exactement comme Macsauf que l’on utilise f a la place de Fk. Il s’ensuit que :

Pr[Mac− forgeA,Π(n) = 1] ≤ 2−n

parce que pour tout message m ∈ Q, la valeur t = f(m) est uniformement distribuee dans {0, 1}ndu point de vue de l’adversaire A.

On va montrer ensuite qu’il existe une fonction negligeable negl telle que :∣∣∣∣Pr[Mac− forgeA,Π(n) = 1]− Pr[Mac− forgeA,Π(n) = 1]

∣∣∣∣ ≤ negl(n);

et en combinant avec l’inegalite precedente, on montre que

Pr[Mac− forgeA,Π(n) = 1] ≤ 2−n + negl(n),

ce qui prouvera le theoreme.Pour montrer la derniere inegalite, on va construire un distingueur D en temps polynomial

qui a acces a un oracle pour une fonction et dont le but est de determiner si la fonction estpseudo-aleatoire (i.e. egale a Fk pour une cle k ∈ {0, 1}n choisie uniformement) ou aleatoire(i.e. egale a f pour f ∈ Funcn uniformement). Pour ce faire, D va simuler l’experience du coded’authentification de messages pour A et observer si A reussit en retournant un tag valide surun ”nouveau” message. Si oui, D va deviner qu’il a en face de lui une fonction pseudo-aleatoireFk ; sinon, D va deviner que son oracle est une fonction aleatoire f . En detail :Distingueur D :

D recoit en entree 1n et a acces a l’oracle O : {0, 1}n → {0, 1}n et fonctionne de la facon suivante :

1. Executer A(1n). Quand A fait une requete a son oracle de MAC pour un message m (i.e.quand A demande un tag pour le message m), repondre a cette requete de la manieresuivante :

Demander a O avec m et obtenir la reponse t ; retourner t a A

2. Quand A retourne (m, t) a la fin de son execution, faire :

(a) Demander a O avec m et obtenir la reponse t.

(b) Si (1) t = t et (2) A n’a jamais fait la requete a son oracle de MAC pour m, retourner1 ; sinon, retourner 0.

Il est clair que D s’execute en temps polynomial.Remarquer que si l’oracle de D est une fonction pseudo-aleatoire, alors la vue de A quand il

est execute comme une sous-routine de par D est distribue identiquement de la vue de A pendantl’experience Mac− forgeA,Π(n). De plus, D retourne 1 exactement quand Mac− forgeA,Π(n) = 1.Par consequent,

Pr

[DFk(·)(1n) = 1

]= Pr

[Mac− forgeA,Π(n) = 1

],

ou k ∈ {0, 1}n est choisie uniformement au hasard. Si l’oracle de D est une fonction aleatoire,alors la vue de A quand il est execute comme une sous-routine par D est distribuee identiquement

26

a la vue de A pendant l’experience Mac− forgeA,Π(n), et donc, il retourne 1 exactement quandMac− forgeA,Π(n) = 1. Par consequent,

Pr

[Df(·)(1n) = 1

]= Pr

[Mac− forgeA,Π(n) = 1

],

ou f ∈ Funcn est choisie uniformement.Comme F est une fonction pseudo-aleatoire et D tourne en temps polynomial, il existe une

fonction negligeable negl telle que :∣∣∣∣Pr [DFk(·)(1n) = 1

]− Pr

[Df(·)(1n) = 1

]∣∣∣∣ ≤ negl(n).

Ceci conclut la preuve du theoreme.

Considerons la construction suivante appelee Ext-MAC qui construit un MAC sur pour desmessages de taille arbitraire a partir d’un MAC sur pour des messages de taille fixe n. SoitΠ′ = (Mac′,Vrfy′) un MAC pour des messages de taille fixe n. Definissons le MAC suivant :

— Mac : sur l’entree la cle k{0, 1}n et un message m{0, 1}∗ de longueur (non nulle) ℓ < 2n/4,parser m en d blocs m1, . . . ,md, chacun de longueur n/4. (Le bloc final est padde avecdes 0 si necessaire.) Choisir un identifiant uniformement r ∈ {0, 1}n/4.Pour i = 1, . . . , d, calculer ti ← Mac′k(r∥ℓ∥i∥mi), ou i, ℓ sont encodes comme des chaınesde longueur n/4 1. Retourner le tag t := (r, t1, . . . , td).

— Vrfy : sur l’entree la cle k ∈ {0, 1}n, un message m ∈ {0, 1}∗ de longueur ℓ < 2n/4, et untag t = (r, t1, . . . , td′), parser m en d blocs m1, . . . ,md, chacun de longueur n/4. (Le blocfinal est padde avec autant de 0 que necessaires.) Retourner 1 si et seulement si d′ = d etVrfy′k(mi∥ℓ∥i∥mi, ti) = 1 pour tout 1 ≤ i ≤ d.

Theoreme 8. Si Π′ est un MAC sur pour des messages de taille fixe n, la construction Ext-MACest un MAC sur pour des messages de taille fixe arbitraire.

Theoreme 9. Si F est une fonction pseudo-aleatoire, la construction CBC-MAC est un MACsur pour des messages de taille fixe n.

2.4 Fonctions de Hachage

Les fonctions de hachage sont des fonctions de

H : {0, 1}∗ → {0, 1}n.

Les proprietes de securite attendues des fonctions de hachage :

1. Resistance aux collisions : il est difficile calculatoirement de trouver deux messages M =M ′ tels que H(M) = H(M ′) (Resistance en O(2n/2))

2. Resistance aux secondes preimages : etant donne M , il est calculatoirement difficile detrouver un autre message M ′ = M tel que H(M) = H(M ′) (Resistance en O(2n))

3. Resistance en preimage : etant donne h ∈ {0, 1}n, trouver un messageM tel queH(M) = h(Resistance en O(2n))

1. Noter que i et ℓ sont encodes en utilisant n/4 bits car i, ℓ < 2n/4.

27

Formellement, on doit considerer des fonctions de hachage a cles. C’est-a-dire, H est unefonction a deux entrees, qui prend une cle s et une chaıne x et retourne une chaıne Hs(x) :=H(s, x). L’exigence est qu’il doit etre difficile de trouver une collision pour Hs pour une cle sgeneree aleatoirement. Il y a au moins 2 differences entre les cles utilisees dans ce contexte etjusqu’a present. D’abord, toutes les chaınes ne correspondent pas forcement a des cles valides(Hs peut ne pas etre definie pour certains s), et par consequent la cle s sera generee par unalgorithme Gen plutot que de facon uniforme. Ensuite, la cle s n’est generalement pas gardeesecrete, et la resistance aux collisions doit etre garantie meme si s est revelee a l’adversaire.

D’un point de vue formel, on est oblige d’utiliser des fonctions de hachage a cle, car si lafonction H est donnee, il exsite toujours un algorithme tres compact qui trouve une collision. Eneffet, si on hardcode la collision dans le programme, alors il est facile de voir qu’il retourne unecollision. Mais si on veut que l’adversaire soit capable de le faire pour n’importe quelle cle s, iln’est pas facile de trouver un algorithme qui realise cette tache.

Definition 13. Une fonction de hachage (avec une taille de sortie ℓ) est une paire d’algorithmesprobabilistes en temps polynomial (Gen,H) satisfaisant :

— Gen est un algorithme probabiliste qui prend en entree un parametre de securite 1n etretourne une cle s. On suppose que 1n est implicite dans s.— H prend en entree une cle s et une chaıne x ∈ {0, 1}∗ et retourne une chaıne de bitsHs(x) ∈ {0, 1}ℓ(n) (ou n est la valeur du parametre de securite implicite dans s).

Si Hs est definie seulement pour les entrees x ∈ {0, 1}ℓ′(n) avec ℓ′(n) > ℓ(n), alors on ditque la fonction (Gen,H) est une fonction de hachage pour des messages en entree de taille fixeℓ′. Dans ce cas, on dit aussi que H est une fonction de compression.

Definissons maintenant la securite d’une fonction de hachage. Comme d’habitude, on definitune experience pour une fonction de hachage Π = (Gen,H), un adversaire A et un parametre desecurite n :

Experience trouver-collision Hash− collA,Π(n) :

1. Une cle s est generee en executant Gen(1n).

2. L’adversaire A recoit la cle s et retourne x = x′. (Si Π est une fonction de hachage delongueur fixe pour des entrees de longueur ℓ′(n), alors on a x, x′ ∈ {0, 1}ℓ′(n).)

3. La sortie de l’experience est definie a 1 si et seulement si x = x′ et Hs(x) = Hs(x′). Dansce cas, on dit que A a trouve une collision.

Definition 14. Une fonction de hachage Π = (Gen,H) est resistante aux collision si pour toutadversaire probabiliste en temps polynomial A, il existe une fonction negligeable negl telle que

Pr[Hash− collA,Π(n) = 1] ≤ negl(n).

2.4.1 Extension de domaine : Merkle-Damgard

Le but des extension de domaine est de transformer une fonction de compression en fonctionde hachage de maniere sure.

Theoreme 10. Si (Gen, h) est resistante aux collisions, alors (Gen,H) aussi.

Demonstration. On montre que pour tout s, une collision sur Hs donne une collision sur hs.Soit x et x′ deux chaınes de bits differentes de longueur L et L′ respectivement, telles queHs(x) = Hs(x′). Soit x1, . . . , xB les B blocs du message x padde, x′1, . . . , x

′B′ les B′ blocs du

message x′ padde. On rappelle que xB+1 = L et x′B′+1 = L′. Considerons deux cas :

28

1. L = L′. Dans ce cas, la derniere etape du calcul de Hs(x) est zB+1 := hs(zB∥L), et laderniere etape de Hs(x′) est z′B′+1 := hs(z′B′∥L′). Comme Hs(x) = Hs(x′), il s’ensuit quehs(zB∥L) = hs(z′B′∥L′). Cependant, L = L′, et donc zB∥L et z′B′∥L′ sont deux chaınesde bits differentes qui collisionnent par hs.

2. L = L′. Ceci signifie que B = B′. Soit z0, . . . , zB+1 les valeurs definies pendant le calculde Hs(x), soit Ii := zi−1∥xi la i-eme entree de hs et IB+2 = zB+1. Soit I ′1, . . . I

′B+2 de

facon analogue pour x′. Soit N l’indice le plus grand tel que IN = I ′N . Comme |x| = |x′|et x = x′, il existe un indice i avec xi = x′i et donc un tel N existe. Comme

IB+2 = zB+1 = Hs(x) = Hs(x′) = z′B+1 = I ′B+2,

on a N ≤ B+1. Par maximalite de N , on a IN+1 = I ′N+1 et en particulier zN = z′N . Cecisignifie que IN , I ′N sont une collision pour hs.

2.4.2 Hash-and-MAC

L’idee de l’approche Hash-and-MAC est simple. D’abord, un message de taille arbitraire mest hache en une chaıne de bits de longueur fixe Hs(m) en utilisant une fonction de hachageresistante aux collisions. Puis, un MAC (sur pour des messages de taille fixe) est applique sur leresultat.

Considerons la definition formelle de la construction Hash-and-MAC. Soit Π = (Mac,Vrfy)un MAC pour des messages de longueur ℓ(n) et ΠH = (GenH ,H) une fonction de hachage avecune taille de sortie ℓ(n). On construit un MAC Π′ = (Gen′,Mac′,Vrfy′) pour des messages delongueurs variables :

— Gen′ : sur l’entree 1n, choisir uniformement k ∈ {0, 1}n et executer GenH(1n) pour obtenir

une cle s ; la cle est k′ := (k, s).— Mac′ : sur l’entree (k, s) et un message m ∈ {0, 1}∗, retourner t := Mack(H

s(m)).— Vrfy′ : sur l’entree (k, s), un message m ∈ {0, 1}∗ et un MAC tag t, retourner 1 si et

seulement si Vrfyk(Hs(m), t)

?= 1.

Cette construction est sure si Π est un MAC sur pour des messages de longueur fixe et siGen,H est resistante aux collisions. Intuitivement, comme la fonction de hachage est resistanteaux collisions, authentifier Hs(m) est aussi bon qu’authentifier m lui-meme : si l’emetteur peutgarantir que le receveur obtient la valeur correcte de Hs(m), la resistance aux collisions garantiraque l’attaquant ne peut pas trouver un message different m′ qui se hache a la meme valeur. Unpeu plus formellement, supposons qu’un emetteur utilise la construction Hash-and-MAC pourauthentifier un ensemble des messages Q et un attaquant A soit capable de forger un tag validepour un nouveau message m∗ ∈ Q. Il y a deux cas possibles :

— il existe un message m ∈ Q tel que Hs(m∗) = Hs(m). Alors A a trouve une collision surHs, ce qui contredit la resistance aux collisions de (Gen,H).

— pour tout message m ∈ Q, il vient que Hs(m∗) = Hs(m). Soit Hs(Q) := {Hs(m)|m ∈ Q}.Alors Hs(m∗) ∈ Hs(Q). Dans ce cas, A a forge un tag valide pour ”un nouveau message”Hs(m∗) par rapport au MAC de longueur fixe. Ceci contredit l’hypothese sur le fait queΠ est un MAC sur pour des messages de longueur fixe.

Voici une preuve formelle.

Theoreme 11. Si Π est un MAC sur pour des messages de longueur ℓ et ΠH est resistante auxcollisions, alors la construction Hash-and-MAC Π ◦ ΠH est un MAC sur pour des messages detaille arbitraire.

29

Demonstration. Soit Π′ represente la construction Hash-and-MAC et soit un adversaire A′ PPTattaquant Π′. Dans une execution de l’exeprience Mac− forgeA′,Π′(n), soit k′ = (k, s) la cle deMAC, soit Q l’ensemble de tous les messages dont le tag a ete demande par A′ et soit (m∗, t) lareponse finale de A′. On suppose sans perte de generalite que m∗ ∈ Q. On definit coll l’evenementque dans l’experience Mac− forgeA′,Π′(n), il existe un m ∈ Q tel que Hs(m) = Hs(m∗). On a :

Pr[Mac− forgeA′,Π′(n) = 1] = Pr[Mac− forgeA′,Π′(n) ∧ coll] + Pr[Mac− forgeA′,Π′(n) ∧ coll]

≤ Pr[coll] + Pr[Mac− forgeA′,Π′(n) ∧ coll].

On montre que les deux termes dans l’equation precedente sont negligeables, ce qui completerala preuve. Intuitivement, le premier terme est negligeable a cause de la resitance aux collisions deΠH , et le second par securite de Π. Considerons l’algorithme suivant C pour trouver une collisionsur ΠH :

Algorithme C : L’algorithme recoit s en entree (avec n implicitement)— Choisir uniformement k ∈ {0, 1}n.— Executer A′(1n). Quand A′ retourne un tag pour le ieme message mi ∈ {0, 1}∗, calculerti := Mack(H

s(mi)) et donner ti a A′.— Quand A′ retourne (m∗, t), alors s’il existe un i tel que Hs(m∗) = Hs(mi), retourner(m∗,mi).

Il est clair que l’algorithme C s’execute en temps polynomial. Analysons son comportement.Quand l’entree son entree est generee en executant GenH(1n) pour obtenir une cle s, la vue deA′ quand on l’execute comme une sous-routine par C est distribuee identiquement que la vue deA′ dans l’experience Mac− forgeA′,Π′(n). En particulier, les tags donnes a A′ par C ont la memedistribution que les tags que A′ recoit dans l’experience Mac− forgeA′,Π′(n). Comme C retourneune collision exactement quand coll apparaıt, on a :

Pr[Hash− collC,ΠH(n) = 1] = Pr[coll].

Comme ΠH est resistante aux collisions, on en deduit que Pr[coll] est negligeable.Maintenant, on va prouver que le second terme de l’equation est negligeable. Considerons

l’adversaire suivant A attaquant Π dans Mac− forgeA,Π(n).

Algorithme A : L’adversaire a acces a un oracle MAC Mack(·) :— Executer GenH(1n) pour obtenir s.— Executer A′. Quand A′ fait une requete de tag pour le iieme message mi ∈ {0, 1}∗,alors : (1) calculer mi := Hs(mi) ; (2) obtenir un tag ti pour mi de l’oracle de MAC ; et(3) donner ti a A′.— Quand A′ retourne (m∗, t), alors retourner (Hs(m∗), t).

Clairement A s’execute en temps polynomial. Considerons l’experience Mac− forgeA,Π(n).Dans cette experience, la vue de A′ quand on l’execute comme sous-routine de A est distribueede facon identique a sa vue dans l’experience Mac− forgeA′,Π′(n). De plus, a chaque fois queles evenements Mac− forgeA′,Π′(n) et coll ne se produisent pas, A retourne une forgerie valide.(Dans ce cas, t est un tag valide sur Hs(m) dans le schema Π par rapport a k. Le fait que colln’a pas eu lieu signifie que Hs(m∗) n’a jamais ete demande par A a son oracle MAC et donc,c’est une forgerie valide.) Par consequent, on a :

Pr[Mac− forgeA,Π(n) = 1] = Pr[Mac− forgeA′,Π′(n) = 1 ∧ coll],

et la securite de Π implique que la probabilite precedente soit negligeable. Ceci conclut la preuvedu theoreme.

30

3 Cryptographie Asymetrique

3.1 Rappel d’algebre et Theorie des Nombres

3.2 Echange de cle et Diffie-Hellman

3.3 Chiffrement Hybride

3.4 El Gamal et RSA

3.5 Signatures

31

4 Annexes

4.1 Probabilite

Lire un livre de base sur les probabilites par exemple [].Soit E un evenement, alors E represente l’evenement complementaire ; c’est-a-dire que E est

l’evenement que E n’a pas eu lieu. Par definition, Pr[E] = 1 − Pr[E]. Si E1 et E2 sont deuxevenements, alors E1 ∧ E2 presente leur conjonction ; c’est-a-dire que E1 ∧ E2 est l’evenementque les deux evenements aient lieu en meme temps. Par definition, Pr[E1 ∧ E2] ≤ Pr[E1]. Lesevenements E1 et E2 sont dits independants si Pr[E1 ∧ E2] = Pr[E1] · Pr[E2].

Si E1 et E2 sont deux evenements, alors E1 ∨ E2 represente la disjonction de E1 et E2 ;c’est-a-dire que, E1∨E2 est l’evenement que l’un des deux evenements E1 ou E2 ait lieu (ou nonexclusif). Il s’ensuit de la definition que Pr[E1 ∨ E2] ≥ Pr[E1]. La borne de l’union est souventune borne superieure de cette quantite.

Proposition 1. (Union Bound)

Pr[E1 ∨ E2] ≤ Pr[E1] + Pr[E2].

Une application repetee de la borne de l’union pour les evenements E1, . . . , Ek donne

Pr[

k∨i=1

Ei] ≤k∑

i=1

Pr[Ei].

La probabilite conditionnelle de E1 etant donne E2, notee Pr[E1|E2], est definie comme

Pr[E1|E2]∆=

Pr[E1 ∨ E2]

Pr[E2]

tant que Pr[E2] = 0. (Si Pr[E2] = 0, alors Pr[E1|E2] n’est pas definie.) Ceci represente laprobabilite que E1 arrive, etant donne que E2 est arrive. Il s’ensuit que :

Pr[E1 ∧ E2] = Pr[E1|E2] · Pr[E2];

egalite a lieu si Pr[E2] = 0. On peut en deduire le theoreme de Bayes :

Theoreme 12. Si Pr[E2] = 0, alors

Pr[E1|E2] =Pr[E2|E1] · Pr[E1]

Pr[E2].

Demonstration. Ceci provient de :

Pr[E1|E2] =Pr[E1 ∧ E2]

Pr[E2]=

Pr[E2 ∧ E1]

Pr[E2]=

Pr[E2|E1] · Pr[E1]

Pr[E2].

Soit E1, . . . , En des evenements tels que Pr[E1 ∨ . . . ∨ En] = 1 et Pr[Ei ∧ Ej ] = 0 pour touti = j. C’est-a-dire que {Ei} forment une partition de l’espace de tous les evenements possibles,donc avec probabilite 1 exactement un de ces evenements se produit. Donc, pour tout F ,

Pr[F ] =n∑

i=1

Pr[F ∧ Ei].

32

Un cas special quand n = 2 et E2 = E1, donne,

rclPr[F ] = Pr[F ∧ E1] + Pr[F ∧ E1] (1)

= Pr[F |E1] · Pr[E1] + Pr[F |E1] · Pr[E1]. (2)

En prenant F = E1 ∨ E2, on obtient une version plus fine de la borne de l’union :

rclPr[E1 ∨ E2] = Pr[E1 ∨ E2|E1] · Pr[E1] + Pr[E1 ∨ E2|E1] · Pr[E1] (3)

≤ Pr[E1] + Pr[E2|E1]. (4)

En generalisant cette formule aux evenements E1, . . . , En, on obtient :

Pr[

k∨i=1

Ei] ≤ Pr[E1] +

k∑i=2

Pr[Ei|E1 ∧ . . . ∧ Ei−1].

4.1.1 Bornes de probabilite utiles

Le lecteur est invite a consulter un livre de probabilite comme le Feller s’il ne connaıt passes resultats classiques qui peuvent aussi se trouver dans le Cormen, Leicerson, Rivest and Steind’Algorithmique.

Une variable aleatoire X est a valeurs (discretes, reelles) est une variable dont la valeur estassignee de facon probabiliste a partir d’un ensemble fini S des nombres reels. X est non-negativesi elle ne prend pas des valeurs negatives ; elle est une variable aleatoire 0/1 si S = {0, 1}. Lesvariables aleatoires 0/1 X1, . . . , Xk sont independantes si pour tout b1, . . . , bk, on a Pr[X1 =

b1 ∧ . . . ∧Xk = bk] =∏k

i=1 Pr[Xi = bi].On represente par Exp[X] la moyenne de la variable aleatoire X ; si X prend ces valeurs dans

S, alors Exp[X]∆=

∑s∈S s · Pr[X = s]. Une propriete des plus importantes est que la moyenne

est lineaire ; pour des variables aleatoires X1, . . . , Xk (avec des dependances arbitraires), on a :Exp[

∑i Xi] =

∑i Exp[Xi]. Si X1, X2 sont independantes, alors Exp[X1 ·X2] = Exp[X1] · Exp[X2].

L’inegalite de Markov est utile quand on connaıt peu de choses sur X :

Theoreme 13. (Inegalite de Markov) Soit X une variable aleatoire non-negative et v > 0. AlorsPr[X ≥ v] ≤ Exp[X]/v.

La variance de X, notee Var[X], mesure de combien X devie de sa moyenne. On a : Var[X]∆=

Esp[(X −Esp[X])2] = Esp[X2]−Est[X]2, et on peut facilement voir que Var[aX + b] = a2Var[X].Pour une variable aleatoire 0/1 Xi, on a Var[Xi] ≤ 1/4 car dans ce cas Esp[X2

i ] = Esp[Xi] etdonc Var[Xi] = Esp[Xi](1− Esp[Xi]), qui est maximisee quand Esp[Xi] = 1/2.

Theoreme 14. (Inegalite de Chebyshev) Soit X une variable aleatoire et δ > 0. Alors :

Pr[|X − Esp[X]| ≥ δ] ≤ Var[X]

δ2.

Les variables aleatoires 0/1 X1, . . . , Xm sont deux a deux independantes si pour tout i = j ettout bi, bj ∈ {0, 1}, on a :

Pr[Xi = bi ∧Xj = bj ] = Pr[Xi = bi] · Pr[Xj = bj ].

Si X1, . . . , Xm sont deux a deux independantes, alors Var[∑m

i=1 Xi] =∑m

i=1 Var[Xi]. (Ceci pro-vient du fait que Esp[Xi ·Xj ] = Esp[Xi] · Esp[Xj ] quand i¬j en utilisant l’independance deux adeux.) Un corollaire important est l’inegalite de Chernoff :

33

Theoreme 15. Soit X1, . . . , Xm des variables aleatoies deux a deux independantes de mememoyenne µ et de variance σ2. Alors pour tout δ > 0, on a :

Pr[|∑m

i=1 Xi

m− µ| ≥ δ] ≤ σ2

δ2m.

Si X1, . . . , Xm sont des variables 0/1, fournissant chacune une estimation d’un bit fixe binconnu : c’est-a-dire Pr[Xi = b] ≥ 1/2 + ε pour tout i, avec ε > 0. On peut estimer b enregardant la valeur de X1 ; cette estimation sera correcte avec probabilite Pr[X1 = b]. Unemeilleure estimation peut etre obtenue en regardant la valeur de X1, . . . , Xm et en prenant lavaleur qui arrive la majorite des temps. On peut estimer si ceci est une bonne estimation dansle cas ou les tirages sont deux a deux independants.

Theoreme 16. Soit ε > 0 et b ∈ {0, 1}, et soit {Xi} des variables aleatoires 0/1 deux a deuxindependantes telles que Pr[Xi = b] ≥ 1/2+ε pour tout i. Considerons le processus qui enregistrem valeurs X1, . . . , Xm et X est la valeur qui arrive la majorite du temps. Alors :

Pr[X = b] ≤ 1

4 · ε2 ·m.

On peut obtenir une meilleure borne dans le cas ou {Xi} sont independants.

Theoreme 17. Soit ε > 0 et b ∈ {0, 1}, et soit {Xi} des variables aleatoires 0/1 independantesavec Pr[Xi = b] ≥ 1/2 + ε pour tout i. La probabilite que la valeur majoritaire ne soit pas b est

au plus eε2m/2.

4.1.2 Paradoxe des anniversaires

Si on choisit q elements y1, . . . , yq uniformement dans un ensemble de taille N , quelle est laprobabilite qu’il existe des indices distincts i, j tels que yi = yj ? On appelle ce dernier evenementune collision et on represente la probabilite de cet evenement par coll(q,N). Ce probleme est relieau probleme des anniversaires, qui demande quelle est la taille d’un groupe de personnes tellequ’avec probabilite 1/2 un couple de personnes dans le groupe a le meme jour d’anniversaire.Pour voir la relation, soit yi represente le jour anniversaire de la personne i dans le groupe. S’il ya q personnes dans le groupe, on a q valeurs y1, . . . , yq choisies uniformement dans {1, . . . , 365}en faisant la simplification que les anniversaires sont uniformes et distribues independamment.De plus, les anniversaires qui coincident correspondent a des collisions, i.e. i = j tels que yi = yj .En consequence, la solution recherchee au probleme des anniversaires est donnee par le minimum(entier) des valeurs de q pour lesquelles coll(q, 365) ≥ 1/2. (La reponse peut vous surprendre,q=23 personnes sont suffisantes !)

On va donner une borne superieure et inferieure sur coll(q,N).

Lemme 4. Soit un entier positif N et q elements y1, . . . , yq choisis uniformement et indepen-damment au hasard dans un ensemble de taille N . Alors la probabilite qu’il existe deux indices

distincts i = j avec yi = yj est au plus q2

2N . C’est-a-dire :

coll(q,N) ≤ q2

2N.

Demonstration. La preuve est une simple application de la borne de l’union. On rappelle qu’unecollision signifie qu’il existe deux entiers distincts i, j tels que yi = yj . Soit Coll represente

34

l’evenement d’une collision et Colli,j l’evenement que yi = yj . De plus, Coll =∨

i =j Colli =j et enrepetant la borne de l’union :

Pr[Coll] = Pr[∨

i =j Colli,j ]

≤∑

i =j Pr[Colli,j ] =(q2

)· 1N ≤

q2

2N .

Lemme 5. Soit un entier positif N et q ≤√2N elements y1, . . . , yq choisis uniformement et

independamment au hasard dans un ensemble de taille N . Alors la probabilite qu’il existe deux

indices distincts i = j avec yi = yj est au moins q(q−1)4N . En fait,

coll(q,N) ≥ 1− e−q(q−1)/2N ≥ q(q − 1)

4N.

Demonstration. On rappelle qu’une collision signifie qu’il existe deux entiers distincts i, j tels queyi = yj . Soit Coll represente l’evenement d’une collision. Soit NoColli l’evenement qu’il n’y a pasde collision parmi y1, . . . , yi ; c’est-a-dire que yi = yk pour tout j < k ≤ i. Alors NoCollq = Collest l’evenement qu’il n’y a pas du tout de collision.

Si NoCollq a lieu, alors NoColli a lieu pour tout i ≤ q. Ainsi,

Pr[NoCollq] = Pr[NoColl1] · Pr[NoColl2|NoColl1] . . .Pr[NoCollq|NoCollq−1].

Maintenant Pr[NoColl1] = 1 car y1 ne peut pas etre en collision avec lui-meme. De plus,l’evenement NoCollia lieu quand {y1, . . . , yi} contient i valeurs distinctes ; donc la probabiliteque yi+1 collisionne avec ces valeurs est i/N et donc la probabilite que yi+1 ne collisionne pasest 1− i/N . Par consequent,

Pr[NoColli+1|NoColli] = 1− i

N,

et donc,

Pr[NoColli] =

q−1∏i=1

(1− i

N

).

Comme i/N < 1 pour tout i, on A− i/N ≤ e−i/N et donc

Pr[NoCollq] ≤q−1∏i=1

e−i/N = e−∑q−1

i=1 i/N = e−q(q−1)/2N .

On en conclut que

Pr[Coll] = 1− Pr[NoCollq] ≥ 1− e−q(q−1)/2N ≤ q(q − 1)

4N,

car pour tout 0 ≤ x ≤ 1, e−x ≤ 1− (1− 1/e) · x ≤ 1− x/2.

35