Fonctions à sens unique en Crypto... - ibni

Dans le chiffrement à clef publique la clef de chiffrement est accessible librement, mais pas la clef de déchiffrement.

Ce type de chiffrement repose directement sur l'existence de fonctions à trappes à sens unique :

• Une fonction est dite à sens unique quand il est facile de calculer f(x) en connaissant x, mais très difficile (voire impossible) de calculer x en connaissant f(x).

• Une fonction à sens unique est dite à trappes quand il est très difficile (voire impossible) de calculer x en connaissant f(x) SAUF si on connaît une information supplémentaire.

Par exemple la fonction qui à deux nombres premiers n et p associe leur produit n×p est une fonction unique : il est très facile de calculer n×p en connaissant n et p, mais très difficile de calculer n et p en ne connaissant que n×p (ceux qui n'en serait pas convaincu peuvent relire avec profit la section intitulée « Problèmes difficiles »). Il est par contre extrêmement facile de retrouver n si on connaît aussi p (ou le contraire) : une simple division suffit.

---

Définition 7.7 (Fonction à Sens Unique)   Une fonction à sens unique est une fonction qui est facile à calculer mais difficile à inverser (par calcul).

Comment une fonction à sens unique peut-elle être utile en cryptographie ?

L'idée-clé est que le codage et le décodage sont faciles à calculer, mais que leur inversion est difficile (même si ).

Toutefois, l'application la plus évidente de fonctions à sens unique concerne certainement les systèmes basés sur des mots de passe.

Pour chaque utilisateur autorisé du système, un mot de passe est stocké sous forme cryptée , où est une fonction à sens unique. Lorsque quelqu'un veut utiliser le système (« log in »), il fournit un mot de passe et le système calcule (sens facile) et vérifie si il correspond à l'information enregistrée . Si c'est le cas, l'accès est autorisé à l'utilisateur ; si non, il lui est refusé. L'avantage de ce système est que les mots de passe cryptés enregistrés n'ont pas besoin d'être gardés secrets^7.7. Si est vraiment une fonction à sens unique, un attaquant qui arrive d'une façon quelconque à accéder à ces mots de passe cryptés ne peut rien en faire puisqu'il lui est calculatoirement impossible de trouver un mot (de passe) tel que .

Notez, chose intéressante, que ce premier exemple d'application de fonctions à sens unique, effectivement utilisé en pratique, fournit une authentification plutôt qu'une sécurité, dans le sens développé plus tôt dans ce chapitre.

Un exemple de fonction à sens unique est donné dans la prochaine section.

Cryptographie asymétrique

Les concepts de signature numérique sont principalement basés sur la cryptographie asymétrique. Cette technique permet de chiffrer avec un mot de passe et de déchiffrer avec un autre, les deux étant indépendants.

Par exemlpe, imaginons que Bob souhaite envoyer des messages secret à Alice. Ils vont pour cela utiliser la cryptographie symétrique.

Alice génère tout d'abord un couple de clés. Une clé privée (en rouge) et une clé publique (en vert). Ces clés ont des propriétés particulière vis à vis des algorithmes utilisés. En effet, un message chiffré avec une clé ne peut être déchiffré qu'avec l'autre clé. Il s'agit de fonctions à sens unique.
 

Alice transmet ensuite la clé publique (en vert) à Bob.

Grâce à cette clé, Bob peut chiffrer un texte et l'envoyer à Alice.