Chapitre 5 FAQ de sci.crypt Chapitre 7 Retour à la case départ

Cryptographie à clé publique

Ceci est le sixième des dix chapitres de la FAQ de sci.crypt. Nous n'avons pas le temps d'envoyer ce qui manque par courrier électronique, donc ne demandez rien.
Des notes comme "[KAH67]" renvoient à la liste de références au dernier chapitre.

Les chapitres de cette FAQ sont disponibles par FTP anonyme sur ftp://rtfm.mit.edu/pub/usenet/news.answers/cryptography-faq/part[xx]
La FAQ de cryptographie est postée sur les groupes de discussions sci.crypt, talk.politics.crypto, sci.answers, et news.answer tous les 21 jours.

Table des matières

6.1. Qu'est-ce que la cryptographie à clé publique?

Dans un cryptosystème classique, nous avons des fonctions de chiffrement EK et de déchiffrement DK telles que DK(EK(P))=P pour tout texte clair P. Dans un cryptosystème à clé publique, EK peut facilement être calculée à partir d'une "clé publique" X qui à son tour est calculée à partir de K. X est publiée, si bien que n'importe qui peut chiffrer des messages. Si le déchiffrement DK ne peut pas être facilement calculé à partir de X sans connaître la clé privée K, mais facilement en connaissant K, seule la personne qui a généré K pourra déchiffrer les messages. C'est le principe de la cryptographie à clé publique, introduite par Diffie et Hellman en 1976.

Ce document décrit les rudiments de cryptographie à clé publique. Il y a une littérature importante sur les modèles de sécurité de la cryptographie à clé publique, sur d'autres applications de la technologie mathématique qui est derrière la cryptographie à clé publique, etc.; consultez les références à la fin pour une présentation plus complète et plus détaillée.

6.2. Comment la cryptographie à clé publique résout-elle à tous les coups on perd?

Dans un cryptosystème classique, si vous voulez que vos amis soient capables de vous envoyer des messages, vous devez être sûr que personne d'autre ne voit la clé K. Dans un cryptosystème à clé publique, vous pouvez publier X, et vous n'aurez pas à vous soucier des espions. La cryptographie à clé publique résout donc un des problèmes les plus agaçants: la nécessité d'établir un canal sûr pour échanger la clé. Pour établir un canal sûr on utilise la cryptographie, mais la cryptographie à clé privée nécessite un canal sûr!
En résolvant ce dilemme, la cryptographie à clé publique a été considérée par beaucoup comme une révolution technologique, une avancée qui a rendu le chiffrement des communications pratique et omniprésent.

6.3. Quel est le rôle de la fonction à sens unique dans un schéma à clé publique ?

La cryptographie à clé publique est basée sur une fonction à sens unique DK qui a comme caractéristique que le calcul est facile dans une direction (le chiffrement EK) et quasiment impossibe dans l'autre (l'attaque qui consiste à déterminer P à partir de EK(P) et de la clé publique X). De plus, elle a comme propriété que la fonction inverse (le déchiffrement DK) devient calculable si la clé privée K est connue.

6.4. Quel est le rôle de la "clé de session" dans les schémas à clé publique ?

Dans quasiment tous les systèmes à clé publique, les temps de chiffrement et de déchiffrement sont très longs comparés aux autres algorithmes par blocs comme le DES pour des tailles de données comparables. Ainsi dans la plupart des mises en oeuvre des systèmes à clé publique, on génère une clé de session aléatoire beaucoup plus petite que le(s) message(s); seule cette clé temporaire est chiffrée avec l'algorithme à clé publique. Le message est ensuite chiffré avec un algorithme à clé privée plus rapide à l'aide de la clé de session. Du côté du récepteur, la clé de session est déchiffrée avec l'algorithme à clé publique et le "texte clair" récupéré (la clé) est utilisé pour déchiffrer le message.

Cette approche brouille la distinction entre les clés et les messages -- dans ce schéma, le message comprend la clé, et la clé elle-même est traitée comme un "message" chiffrable. Selon cette approche de double chiffrement, la force cryptographique de l'ensemble dépend soit de l'algorithme à clé publique soit de l'algorithme à clé privée.

6.5. Qu'est-ce que le RSA?

RSA est un cryptosystème à clé publique défini par Rivest, Shamir, et Adleman. Voici un petit exemple. Voir aussi [FTPDQ].

Les textes clairs sont les entiers positifs jusqu'à 2^512. Les clés sont des quadruplets (p,q,e,d) avec p entier premier de 256 bits, q entier premier de 258 bits, et d et e deux grands nombres tels que (d.e - 1) soit divisible par (p-1)(q-1)
On définit EK(P) = P^e mod pq, DK(C) = C^d mod pq. Tous ces nombres sont calculés facilement avec des algorithmes classiques ou modernes de théorie des nombres -- d'anciens algorithmes comme Euclide pour calculer le plus grand diviseur commun ou des méthodes récemment explorées comme le test de Fermat découlent des méthodes pour trouver de grands nombres "probablement" premiers, EK est facilement calculé à partir de la paire (pq,e) -- mais, d'après ce que l'on sait, il n'existe aucune façon simple de calculer DK à partir de (pq,e). Ainsi quiconque connaît K peut publier (pq,e). N'importe qui pourra lui envoyer un message secret; lui seul pourra lire les messages.

6.6. Le RSA est-il sûr?

Personne ne sait. Une attaque évidente contre le RSA est de factoriser pq. Voir ci-dessous les commentaires sur la rapidité des meilleurs lagorithmes de factorisation. Malheureusement personne n'a la moindre idée sur comment prouver que la factorisation (ou tout autre problème "réaliste") est fondamentalement lente. Il est facile de formaliser ce que nous entendons par "RSA est/n'est pas robuste"; mais, comme Hendrik W. Lenstra Jr. le dit
les définitions exactes semblent n'être nécessaires que lorsque l'on souhaite prouver que des algorithmes ayant certaines propriétés n'existent pas, et il est notoire que de tels résultats manquent en informatique théorique.

Notez qu'il pourrait exister un "raccourci" qui permettrait de casser le RSA sans factoriser. Donc, la sécurité du système dépend de deux hypothèses critiques: (1) il faut factoriser pour casser le système, et (2) la factorisation est "difficile", ou bien "la factorisation est difficile" et "toute méthode qui peut casser le système est aussi coûteuse que la factorisation".

Dans l'histoire même des cryptographes professionnels ont fait des erreurs en estimant la difficulté de divers problèmes de calcul et en comptant dessus pour des applications cryptographiques sûres. Par exemple, un système connu sous le nom de Knapsack cipher [NdT: sac à dos; en fait, il est basé sur le problème de la sous-somme] a été à la mode dans la littérature pendant des années jusqu'à ce qu'on démontre qu'il pouvait être facilement cassé, et tout ce domaine est passé de mode.

6.7. Quelle est la différence entre le RSA et les schémas de Diffie-Hellman?

Diffie et Hellman ont proposé un système qui exige un échange de clés dynamique pour chaque paire émetteur - recepteur (et en pratique, habituellement pour chaque session de communication, d'où le terme clé de session).
Cette négociation à double sens est utile pour compliquer un peu plus les attaques, mais introduit une charge supplémentaire dans la communication. Le système du RSA réduit cette charge car on peut avoir des clés statiques, immuables, pour chaque récepteur qui a été "publié" par une "autorité de confiance" ou distribué via une "toile d'araignée de confiance" informelle.

6.8. Qu'est-ce que l'"authentification" et "le problème d'échange de clés"?

Le problème d'échange de clés consiste (1) à s'assurer que les clés sont échangées de tellle sorte que l'émetteur et le récepteur puissent chiffrer et déchiffrer, et (2) à faire ça de telle façon qu'un espion ou une personne extérieure ne puisse pas casser le code. L'authentification ajoute le besoin (3) on assure au récepteur qu'un message a été chiffré par une entité donnée et non par quelqu'un d'autre.

La manière la plus simple mais la moins pratique pour respecter toutes ces contraintes (échange de clé réussi et authentification valide) est employée par la cryptographie à clé privée: échanger la clé en secret.
Selon ce schéma, le problème de l'authentification est implictement résolu. On suppose que seul l'émetteur aura la clé capable de chiffrer les messages sensibles envoyés au récepteur.

Bien que les méthodes cryptographiques à clé publique résolve un aspect critique de l'échange de clé, précisément leur résistance à l'analyse même si un espion passif écoute l'échange, elles ne résolvent pas tous les problèmes associés à l'échange de clés. En particulier, comme ces clés sont considérées comme étant connues de tout le monde (en particulier avec le RSA) d'autres mécanismes doivent être développés pour certifier l'authenticité, car la simple possession de la clé (suffisante pour chiffrer des messages intelligibles) ne garantit pas l'identité de l'émetteur.

Une solution (appelée parfois autorité de confiance) est de développer un mécanisme de distribution de clé qui assure que les clés listées sont vraiment celles des entités données. L'autorité ne génère pas les clés, mais assure par un quelconque mécanisme que les listes de clés et les identités associées gardées et publiées par les émetteurs et les récepteurs sont "correctes". Une autre méthode compte sur les utilisateurs pour distribuer et pister les clés des autres et leur faire confiance de façon informelle et distribuée. Ceci a été popularisé par le logiciel PGP qui appelle le modèle toile d'araignée de confiance.

Sous RSA, si on souhaite donner une preuve de son identité en plus du message chiffré, on chiffre simplement à l'aide de sa clé privée une information appelée signature. Ceci est inclus dans le message chiffré avec la clé publique du récepteur.
Le recepteur peut utiliser l'algorithme RSA "à l'envers" pour vérifier que l'information déchiffrée a un sens, donc que seule l'entité donnée a pu chiffrer le texte clair à l'aide de sa clé privée. Typiquement la signature chiffrée est un "résumé du message" [NdT: message digest en anglais] qui comprend un résumé mathématique du message secret (si la signature était statique sur plusieurs messages, les récepteurs pourraient l'utiliser frauduleusement une fois celle-ci connue). De cette façon, seul l'émetteur du message peut théoriquement générer une signature valide. Les signatures numériques ont beaucoup d'autres propriétés décrites dans le chapitre 7.

6.9. A quelle vitesse peut-on factoriser?

Ca dépend de la taille des nombres, et de leur forme. Des nombres tels que a^n - b avec b "petit" sont plus facilement factorisés avec des techniques spécialisées et ne sont pas significatifs du problème général. Donc une avancée sur une forme de nombres particulière peut n'avoir aucune valeur pratique pour d'autres nombres (ceux générés pour l'utilisation dans les cryptosystèmes sont "filtrés" spécialement pour résister à de telles attaques). L'observation la plus importante à propos de la factorisation est que tous les algorithmes nécessitent un temps exponentiel en fonction de la taille du nombre (mesurée en bits, log2(n) où n est le nombre). Les algorithmes cryptographiques construits sur la difficulté de la factorisation dépendent généralement de cette propriété. (la distinction entre les algorithmes à temps exponentiel ou à temps polynomial, ou NP et P, est un domaine majeur de la recherche informatique; certains résultats sont intimement liés à la sécurité cryptographique)

En Octobre 1992 Arjen Lenstra et Dan Bernstein ont factorisé 2^523 - 1 en nombres premiers, en utilisant environ trois semaines de temps de calcul d'une MasPar (La MasPar est une machine SIMD à 16384 processeurs; chaque processeur peut additionner environ 200000 entiers par seconde) L'algorithme est appelé crible du corps des nombres; il est nettement plus rapide pour des nombres spéciaux comme 2^523 - 1 que pour des nombres généraux n, mais il prend seulement exp(O(log^{1/3} n log^{2/3} log n)) dans tous les cas.

Une méthode plus vieille et plus populaire pour les petits nombres est le crible polynomial quadratique multiple, qui prend un temps exp(O(log^{1/2} n log^{1/2} log n)) --- plus rapide que l'autre pour les petits nombres mais plus lente pour les grands nombres. Le point d'équilibre est quelque part entre 100 et 150 chiffres, selon les réalisations.

La factorisation est un domaine qui bouge vite --- l'état de l'art il y a seulement quelques années était loin d'être aussi bon que maintenant. Si aucune nouvelle méthode n'est développée, les clés RSA sur 2048 bits seront toujours sûres contre la factorisation, mais personne ne peut prédire le futur (avant que le crible du corps des nombres soit découvert, certains ont conjecturé que le crible quadratique était asymptotiquement aussi rapide que possible).

6.10. Et les autres systèmes à clé publique?

Nous avons parlé du RSA parce qu'il est bien connu et facile à décrire. Mais il y a beaucoup d'autres systèmes à clé publique, beaucoup sont plus rapides que le RSA ou dépendent de problèmes que plus de gens croient difficiles. Ceci est juste une brève introduction; si vous voulez réellement apprendre les nombreuses facettes de la cryptographique à clé publique, consultez les livres et articles de journaux cités au chapitre 10 .

6.11. Qu'est-ce que le défi de factorisation RSA?

[Note: les adresses E-mail ci dessous seraient invalides]
En 1992 environ, RSA Data Securities Inc., propriétaire des multiples brevets sur le matériel RSA et les techniques cryptographiques en général, fabricant de divers logiciels et bibliothèques de chiffrement a annoncé sur sci.math et ailleurs le lancement d'un Défi de Factorisation pour juger de l'état de l'art en technologie de factorisation. Tous les mois une série de nombre est publiée et des récompenses sont offertes au premier qui les casse en facteurs. Des ressources matérielles significatives sont nécessaires pour arriver à battre les autres participants. On peut obtenir des renseignements par réponse automatique à
Chapitre 5 FAQ de sci.crypt Chapitre 7 Retour à la case départ
Michel Arboi
Last modified: Sun Mar 25 16:21:01 CEST 2007