Maintenant que nous avons vu quelques
exemples de chiffres historiques,
tous gravement défectueux, nous allons
passer à des chiffres bien mieux faits.
Avant je veux définir plus précisément
ce qu'est un chiffre. D'abord, rappelez-
vous qu'un chiffre est fait de
deux algorithmes: un algorithme de
cryptage et un algorithme de décryptage.
Mais un chiffre est défini sur un triplet:
l'ensemble de toutes les clefs possibles,
que je vais noter K, que j'appellerai
aussi l'espace des clefs;
l'ensemble de tous les messages
possibles, et
l'ensemble de tous les textes chiffrés possibles.
Donc ce triplet est
l'espace de definition du chiffre. Le chiffre lui-meme est une paire d'algorithmes "efficaces", E et D.
E est l'algorithme de chiffrage; D est
l'algorithme de déchiffrage.
E prend des clefs et des messages,
et produit des textes chiffrés. /////
D prend des clefs et des textes en chiffre,
et produit des messages.
Et tout ce qu'il faut, c'est que ces algorithmes soient consistents (/constants): qu'ils satisfassent
ce qu'on appelle la propriete de correction. Pour tout message dans l'espace des messages,
et toute clef dans l'espace des clefs,
il faut que si je chiffre le
message avec la clef K et je dechiffre ensuite avec K,
je retrouve le message d'origine.
Cette equation la est ce qu'on appelle
l'equation de consistance (/constance)
et tout chiffre doit la satisfaire pour etre un chiffre,
sinon le dechiffrage est impossible.
Une chose a souligner est que j'ai place
le mot "efficace" entre guillemets.
La raison en est qu'"efficace"
a des senses differents selon ta perspective.
Si tu aimes la
theorie, l'efficacite veut dire que ca s'execute en un temps d'ordre polynomial. Les algorithmes E et D prennent un
temps d'ordre polynomial a operer sur leurs donnees.
Si tu es plus pratique,
l'efficacite veut dire que ca dure un temps assez court. Par exemple,
un algorithme E prendrait moins d'une minute
pour chiffrer 1 gigabyte d'information.
D'une facon ou d'une autre, le mot "efficace" capture la notion de duree et tu peux
l'interpreter dans ta tete comme tu le veux.
Je vais continuer a
parler d'efficacite et a mettre le mot entre guillemets,
et comme je l'ai dit si tu es plus theorique
penses "duree polynomiale", sinon penses
contraintes temporelles concretes. Un autre commentaire que je veut faire est que l'algorithme E
est souvent un algorithme aleatoire.
Ca veut dire que pendant que tu cryptes
un message, l'algorithme E va generer des bits au hasard,
et va utiliser ces bits pour chiffrer le message.
Par contre, l'agorithme de dechiffrement est toujours deterministe. C'est a dire
que la clef et le texte chiffre sont toujours les memes.
Ils ne dependent pas
du hasard d'un algorithme.
Bon, maintenant que nous comprenons
mieux ce qu'est un chiffre, je veux te montrer un premier exemple de chiffre sur ("secure").
Ca s'appelle le "one time pad" (la feuille a 1 utilisation). Vernam l'a cree au debut du
vingtieme siecle. Avant d'expliquer de qu'est ce chiffre, decrivons le avec
la terminologie que nous venons d'apprendre. L'espace des messages du
chiffre de Vernam est le meme que l'espace des textes chiffres, et c'est tout simplement
l'ensemble des strings (/sequences) binaires longues de n-bits. C'est a dire toutes les sequences de
bits, de 0 et de 1. L'espace des clefs est le meme que l'espace
des messages, qui est encore l'ensemble de toutes les sequences binaires. Une clef dans le "onetime pad"
est une longue sequence binaire aleatoire, aussi longue
que le message a chiffrer. Bon, maintenant que nous
avons precise l'univers de definition du chiffre,
decrivons comment
le chiffre fonctionne. C'est tres simple.
Essentiellement, le texte chiffre
qui resulte du cryptage du message
est simplement k XOR m. Voyons en un exemple.
Souviens-toi que XOR, ce signe d'addition entoure d'un cercle, veut dire une addition modulo 2.
Donc je prends un message, disons 0110111. Et je prends
une clef, disons 1011001. Quand je chiffre le message
avec la clef, je compute le XOR des deux sequences de bits.
Autrement dit, j'additionne les deux, modulo 2, bit par bit. La, le resultat
c'est 101110. C'est le texte chiffre. Comment le decrypter?
Faisons un chose semblable. Pour decrypter un texte chiffre en utilisant
une clef, je XOR la clef et le texte chiffre. Et tout ce qu'il
faut verifier c'est que ca satisfasse la regle de consistance. Je vais le refaire doucement
une fois encore et ensuite je vais le prendre pour aquis.
Donc je doit m'assurer que si je decrypte un texte chiffre,
qui avait ete encrypte avec une certaine clef, j'ai bien interrest a ce que le resultat soit
le message d'origine, m. Voyons ce qui se passe. Je prends le
message chiffre, qui resultait de k XOR m par definition. Quelle en est le dechiffrage?
C'est k XOR (k XOR m). Et comme l'addition modulo 2 est associative,
c'est equivallent a (k XOR k) XOR m,
qui peut etre simplifie. (k XOR k) = 0,
et zero XOR m
est simplement m. Bon, ceci demontre que le ontime pad est bien un chiffre,
mais ca ne nous dit rien de sa surete. Nous allons parler de
la surete (/securite) de ce chiffre dans un instant.
D'abord, je vais te poser une question,
juste pour s'assurer que tu suis bien.
Suppose un message m
et le chiffrage de m via une clef "ontime pad" k.
Tout ce que tu as est le message et son texte chiffre. Ma questions est celle-ci:
peux-tu deduire la clef qui a servit a
la creation de c a partir de m?
J'espere que tu t'ai rendu compte que, etant donne le message
et le texte chiffre, il est tres facile de recouvrire la clef. Plus precisement,
la clef est m XOR c. Si ceci n'est pas
immediatement evident,
nous verrons plus tard pourquoi ceci est le cas.
Le onetime pad est assez genial du point de vue de sa performance. Tout ce que tu fait
c'est une XOR de la clef sur le message,
et donc c'est super rapide. Mais chiffrer et dechiffrer
des messages tres longs devient difficile en pratique.
La raison que c'est difficile est que la clef
est essentiellement aussi longue que le message. Donc si Alice et Bob veulent se parler
en toute securite, avant qu'Alice ne puisse envoyer un message a Bob, elle doit d'abord
transmettre a Bob une clef qui est aussi longue
que le message lui-meme. Et bien sur, si elle a un moyen sur d'envoyer cette clef a Bob,
pourquoi ne pas s'en servire pour transmettre le
message lui-meme. Donc le fait que la clef est aussi longue que le message est
problematique et rend le one-time pad
tres difficile a utiliser en pratique.
Bien sur, nous verrons plus tard que l'idee qui soutent le onetime pad est tres utile,
Pour l'instant, regardons de plus pres
sa securite. La question qui saute aux yeux est, pourquoi
le chiffre "onetime pad" est-il sur?
Pourquoi est-ce un bon chiffre? Afin de repondre a cette question, la premiere question a poser
est, qu'est que ca veut dire qu'un chiffre est sur?
Qu'est ce qui le rend sur? Bien, alors pour etudier la securite des chiffres, parlons d'abord
de la theorie de l'information. La premiere personne a etudier la securite des chiffres de
facon rigoureuse est le fameux Claude Shannon, pere de la theorie de l'information.
Il publia un fameux papier en 1949 ou il analysa la
securite du onetime pad. L'idee derriere la definition de securite que nous donna Shannon
est que si tout ce que tu vois est le texte chiffre,
tu ne devrais rien savoir du message d'origine. Autrement dit, le texte chiffre
ne devrait rien reveler du message d'origine. Et tu vois maintenant pourquoi il a fallut attendre
l'invention de la theorie de l'information pour avoir cette notion,
parce que Shannon a du qui explique formellement ce qu'une information sur le message d'origine veut dire.
C'est la la contribution de Shanon. Laisses-moi te montrer la definition de Shanon.
Je vais l'ecrire lentement. Ce qu'a dit Shanon, c'est, suppose
que nous avons un chiffre E, D qui est definit dans l'espace K, M, C. Donc K, M, C
definissent les espaces de la clef, du message et du texte chiffre.
On dit que le chiffre est parfaitement sur
si la condition suivante est verifiee.
Pour toute paire de messages m0 et m1 dans l'espace des messages...
pour toute paire de messages -- la seule exigence est que
ces messages aient la meme longueur, nous verrons pourquoi dans une minute --
et pour tout texte chiffre dans l'espace des textes chiffres,
(okay?)
donc pour toute paire de messages et tout texte chiffre,
il faut que, si je demance quelle est la probabilite que
le resultat du chiffrage de m0 par k soit c?
Quelle chance y a-t'il que, si je choisi une clef au hasard,
et que je chiffre m0, j'obtienne c?
Cette probabilite doit etre la meme que si j'avais chiffre m1. Okay, bon,
la probabilite de chiffrer m1 et d'obtenir c est exactement la meme que la
probabilite de chiffrer m0 et d'obtenir c.
Et comme je l'ai dit auparavant,
la clef est choisie au hasard dans un espace (de clefs)
a distribution uniforme.
Donc k est uniforme (a une probabilite uniforme d'etre choisie) dans K. J'utiliserais souvent la notation
K, fleche avec un petit r au dessus pour indiquer le fait que k est une variable aleatoire qui est
echantillonnee de facon uniforme dans l'espace K. Bon, voici le coeur de la definition de Shannon.
Reflechissons a ce que cette definition dit essentiellement.
Que ce que ca veut dire que ces deux probabilites sont les memes? Et bien, ce que ca
nous dit, c'est que si je suis un attaquant et que j'intercepte un texte chiffre c,
la probabilite que de c soit le cryptage de m0 est
exactement la meme que la probabilite que c'est le cryptage de m1. Parceque
ces probabilites sont egales. Donc si j'ai seulement le texte chiffre c, et rien de plus,
je n'ai aucune idee de si le texte chiffre vient de m0
ou de m1, parceque, encore, la probabilite d'obtenir c est
egale que ce soit m0 ou m1 qui ait ete encrypte.
Alors la, la definition est donnee a nouveau. Et je veux juste ecrire ces proprietes une fois encore
plus precisement. Alors refaisons le.
Ce que cette definition veux dire, c'est que
si je recoit un certain texte chiffre, je ne peux pas dire d'ou il vient.
Je ne peux pas dire si le message qui en est l'original etait m0 ou m1.
Et en fait cette propriete est vraie de tous les messages, pour tout m0,
pour tout m1. Non seulement je ne peux pas dire
si c vient de m0 ou de m1,
je ne peux pas dire s'il vient de m2, m3, m4 ou m5 parceque
tous ont la meme probabilite de produire c.
Donc ce que je veux dire vraiment
c'est que si tu encryptes des messages sur un onetime pad alors meme l'adversaire le plus
formidable, quelque soit son intelligence, l'adversaire le plus puissant
ne poura rien apprendre du message d'origine
a partir du texte chiffre. Dit d'une autre maniere,
ce que ca prouve c'est qu'aucune attaque fondee seulement sur le texte chiffre ne pourra venir a bout
d'un chiffre qui est parfaitement secret. Maintenant, une attaque sur le chiffre n'est pas la seule attaque possible.
Et en fait, d'autres attaques sont plausibles.
Bon. Maintenant que nous comprenons le secret parfait,
la prochaine question est celle-ci:
pouvons-nous construire des chiffres qui sont parfaitement secrets? Et il ne faut pas chercher loin,
parceque la ontime pad est parfaitement secrete.
Alors je veux prouver cela, est c'est le premier resultat qu'a obtenu Shannon,
c'est une preuve tres simple alors allons-y et voyons comment ca se fait.
Nous avons besoin d'interpreter ce que veut dire cette probabilite Pr[E(k,m0)=c?
est zero. Alors ce n;est pas vraiment difficile a voir que pour tout message et
pour tout texte chiffre la probabilite que le cryptage de m via la clef k
la probabilite que cela soit egal a c, la probabilite d'un choix au hasard de clef, est, par definition,
le nombre de clefs ( le nb de k appartenant a K)
tel que, si je chiffre m avec k, j'obtient c. Donc je compte literalement le nombre de clefs comme ca
et je divise par le nombre total de clefs dans l'espace K.
C'est bon? C'est ce que ca veut dire
que si je choisi une clef au hasard, elle projette m sur c.
Bien. Donc a la base, ce nombre de clefs
qui projettent m sur c, divise par le nombre total de clefs.
C'est sa probabilite.
Maintenant suppose que nous avons un chiffre tel que
pour tout message et
tout texte chiffre, il se trouve que si je regarde ce nombre,
le nombre de k dans K tels que E(m,k)=c, ou le nombre de clefs
qui projettent m sur c, suppose que ce nombre soit constant.
Je postule qu'il se trouve etre 2, 3, ou 10 ou 15.
Il se trouve simplement etre
une constante. Si c'est le cas, alors par definition, pour tout m0 et m1
et pour tout c, cette probabilite doit etre la meme parce que le denominateur est le meme,
le numerateur est le meme, c'est juste une constante,
et donc la probabilite est
toujours la meme pour tout m et tout c.
Alors si cette propriete est vraie, le chiffre doit avoir
une surete parfaite (/un secret parfait).
Bon, alors voyons ce qu'on peut dire au suject
de cette quantite pour le onetime pad. Alors une question pour toi:
Si j'ai un message chiffre, combien de onetime pads y a t-il qui projettent m sur c? Autrement dit, combien de clefs
y a-t-il telles que m XOR k produise c?
Alors j'espere que tu a repondu "1". Voyons pourquoi c'est le cas.
Pour le onetime pad, si on a que E(k,m)=c,
ca implique par definition que k XOR m = c.
Cela implique que k = m XOR c.
Je "XOR" les deux cotes par "m" et j'obtiens
que k doit etre egal a
m XOR C. Bien? Alors ce que ce veut dire, c'est que pour le onetime pad, en fait,
le nombre de clefs dans K tels que E(k,m)=c
tout simplement 1. Et cela est vrai
pour tout message et tout texte chiffre.
Alors, encore, comme on l'a dit avant,
cela signifie que le onetime pad est parfaitement secret.
Et cela complete la preuve de ce lemme trivial, tres, tres simple.
Maintenant la chose marrante est que meme si ce lemme est simple a prouver
il demontre quelque chose de tres puissant.
Il nous dit au fond que
pour un onetime pad, il n'est pas possible d;attaquer seulement le texte chiffre. Alors au contraire
du chiffre de substitution, ou du chiffre de Vigenere, ou des machines a cran, qui pouvaient toutes
etre cassees par une analyse du texte chiffre, nous venons
de prouver que pour le onetime pad
cela serait impossible. Etant donne le texte chiffre,
tu n'apprends rien
du message d'origine. Cependant, comme on l'a vu,
cela n'est pas la fin de l'histoire.
Je veux dire, est-ce qu'on a fini?
On pourrait avoir deja fini la classe, parcequ'on
a une methode pour chiffrer de facon a ce qu'un attaquant
ne peut rien recouvrir du message.
On peut tout aussi bien finir le cour maintenent.
Mais en fait, comme nous allons voir, il y a
d'autres attaques qui sont possibles. Et, en fait, ce ontime pad n'est pas
un chiffre tellement sur. Il y aa d'autres attaques et nous allons
les etudier bientot. Okay? Je souligne encore: le fait qu'il a un
secret parfait ne veut pas dire
que le onetime pad est un chiffre sur.
Bien. Mais comme on l'a dit
le probleme avec le onetime pad est que la clef secrete
est vraiment longue. Si tu as
une maniere de communiquer cette clef secrete a ta contrepartie, tu peux tout aussi bien
te servir de cette meme methode pour communiquer le message a ta contrepartie
et tu n'aurras alors pas besoin d'un chiffre pour commencer.
C'est bon? Donc le probleme encore une fois
est que le onetime pad a des clefs tres longues.
La question evidente est y a-t-il
d'autres chiffres qui ont un secret parfait et ont peut-etre des clefs bien plus courtes?
Et bien, le mauvaise nouvelle est que Shannon, apres avoir prouve que le onetime pad
est parfaitement secret, prouva un autre theoreme qui dit
que si un chiffre
est parfaitement secret, le nombre de clefs dans le chiffre doit etre exactement le nombre de
messages que le chiffre peut supporter. Bon, alors
en particulier, ce que ca veut dire c'est que
si j'ai un secret parfait, alors necessairement
le nombre de clef, ou plutot la longueur de ma clef,
doit etre plus grande que la longueur du message.
Alors en fait, puisque le onetime pad
nous satisfait avec l'egalite (de longueur), le onetime pad est optimal. Il est parfaitement secret.
Alors a la base, ce que ca demontre, c'est que c'est
une notion interessante. Le onetime pad est un chiffre interessant. Mais en fait,
en realite, c'est tres difficile a utiliser. Il est difficile de s'en servire en pratique,
a cause de ses longues clefs.
Et cette notion de secret parfait,
meme si elle est interessante, nous dit que des chiffres
pratiques ne seront pas vraiment surs.
Et nous verrons cela, mais comme je l'ai dit,
l'idea deriere le onetime pad est tres bonne. Et nous allons voir, en cours,
comment en faire un systeme pratique.