Information theoretic security and the one time pad (19 min)

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.