On a lu avec beaucoup d'attention un article de sur le chiffrement probabiliste. Cet article fait suite au précédent, et on va parler de chiffrement probabiliste.

Prédicats à sens unique

Chiffrer est facile, mais déchiffrer est en pratique impossible sans bénéficier d'une information particulière, en l’occurrence la clef privée. C'est ce qu'on appelle une fonction à sens unique, ou à trappe. Si vous connaissez la trappe, vous savez inverser la fonction. Sinon, c'est très difficile. Un prédicat à sens unique suit exactement la même idée. Si on identifie 0 au faux et 1 au vrai, c'est fondamentalement une fonction dans {0,1}. Donc, un prédicat P à sens unique est une "fonction" où étant donné un x, il est facile de trouver P(x), mais trouver à l'inverse l'ensemble des x tels que P(x) est beaucoup plus compliqué en temps polynomial (on peut toujours énumérer tous les cas possibles sur un ensemble fini, mais...) Donnons en un exemple, celui de l'article : le problème du résidu quadratique. La subtilité est celle ci: vous prenez un anneau, et un entier X sur cet anneau. Vous dites que X est un carré s'il existe un nombre dont le carré vaut X. Jusque là, tout va bien. Sur un corps fini, c'est simple. Mais si on se donne N le produit de deux nombres premiers, ou plus généralement pour un nombre composé, on ne connait pas d'algorithme qui soit efficace, donc exécutable en temps polynomial.

Le problème du résidu quadratique induit donc un prédicat à trappe, ou à sens unique: si vous connaissez la décomposition d'un nombre composé, c'est facile de déterminer si un nombre est un carré. Si vous ne disposez pas de la décomposition du nombre composé, c'est quasiment impossible. La trappe est donc la décomposition du nombre composé. Au passage, vous aurez remarqué une cohérence dans ce magnifique domaine puisque la décomposition d'un nombre en ses facteurs est lui même un problème difficile.

Le chiffrement probabiliste

Et nous voilà armés pour donner un exemple de chiffrement probabiliste. Avec RSA, vous prenez un message long, vous le coupez en blocs que vous transformez en entiers. Pour chaque entier, vous calculez son image (ce qu'on appelle chiffrer). Vous mettez les résultats bout à bout (quitte à rajouter des 0) et bim bam boum, vous avez chiffré vos données. Vous comprenez bien du coup que les mêmes entiers vont donner les mêmes données chiffrées. Avec le chiffrement probabiliste, vous partez d'un prédicat P à trappe, comme par exemple celui dont on parlait plus haut. Pour chaque bit b du message en clair, vous allez prendre un entier X tel que P(X) = b. Avantage immédiat : vous avez un choix de X immense, bien plus grand qu'avec une fonction à trappe. Inconvénient: le message chiffré est vraiment immense par rapport au message en clair. Dans le cas du problème de la résiduosité quadratique, l'algorithme est le suivant :

Et pourquoi on ferait tout ça?

Pour une raison simple: votre clef publique étant ... publique, on peut partir du principe que tous les cryptanalystes motivés du monde vont vouloir mettre à mal votre sécurité. En l'exposant, n'importe quel adversaire pourra tester des messages conçus spécifiquement pour révéler des informations sur la clef privée. Si le même message lui donne une entrée différente d'apparence aléatoire, cela rend encore plus complexe la mise en place d'une attaque pour avoir de l'information sur la clef. 

Conclusion

Ce protocole est sémantiquement sûr. (Pour celles et ceux qui auraient fait l'impasse sur l'article précédent, ça veut dire que vous ne pouvez pas deviner le message en clair à partir du chiffré mieux que par pur hasard). Le cryptosystème d'El Gamal en est un autre exemple. L'idée d'utiliser un prédicat et plus une fonction à trappe est quand même une idée magnifique!

 

Comments are closed.

Set your Twitter account name in your settings to use the TwitterBar Section.