Cryptographie à clé publique : Diffie-Hellman et RSA

Curiosité

1. Comment deux inconnus peuvent-ils convenir d’une clé secrète alors que tout le monde écoute ?
2. Pourquoi est-il trivial de multiplier deux grands nombres premiers, mais presque impossible de retrouver ces nombres premiers à partir de leur produit ?
3. Que signifie posséder quelque chose si la possession est définie par la capacité de signer ?

Explorer

1. Avant 1976, une communication sécurisée nécessitait un secret partagé échangé par un canal de confiance. Si un intercepteur capturait cette clé, tout le trafic ultérieur était compromis. Whitfield Diffie et Martin Hellman ont proposé une solution dans « New Directions in Cryptography » (IEEE Transactions on Information Theory, novembre 1976). Deux parties pouvaient dériver un secret partagé sur un canal ouvert grâce à l’exponentiation modulaire. Le calcul est à sens unique : facile à effectuer dans un sens, impossible en pratique à inverser sans l’entrée privée.
2. Ralph Merkle a conçu des énigmes similaires entre 1974 et 1975, et les a publiées en 1978. L’une des parties publiait de nombreuses petites énigmes chiffrées ; l’autre en résolvait une au hasard et utilisait son contenu comme clé. L’avantage n’était que quadratique : avec n énigmes, les deux parties effectuaient environ n unités de travail, et une oreille indiscrète environ n². Avec Diffie-Hellman, l’écart croît avec la taille de la clé, et lorsque de nouvelles paires de clés sont utilisées à chaque session, une fuite ultérieure des clés à long terme n’expose pas les communications passées.
3. Ron Rivest, Adi Shamir et Leonard Adleman, au MIT, ont développé RSA en 1977. Martin Gardner a décrit le système dans sa chronique d’août 1977 de Scientific American, avant la parution de l’article formel dans Communications of the ACM (février 1978). RSA repose sur la difficulté de décomposer le produit de deux grands nombres premiers en ses facteurs. Il a rendu possibles les signatures numériques : une clé privée signe les données, et la clé publique correspondante vérifie la signature sans révéler le secret du signataire.
4. James Ellis, au GCHQ, a conçu le « chiffrement non secret » vers 1969 et l’a formalisé par écrit en 1970 ; Clifford Cocks a mis au point un système équivalent à RSA en 1973 ; Malcolm Williamson, un équivalent de Diffie-Hellman en 1974. Ces découvertes sont restées classifiées jusqu’en 1997. Ce développement parallèle montre que les fondements mathématiques étaient mûrs dès le début des années 1970, mais que l’adoption n’a suivi qu’après la publication ouverte des travaux de chercheurs universitaires. Le travail secret ne bâtit pas d’infrastructure publique.
5. Rivest, Shamir et Adleman ont reçu le prix Turing en 2002 ; Diffie et Hellman l’ont reçu en 2015. Ces travaux sont essentiels pour bitcoin : la propriété n’est plus liée à la détention physique ni aux registres bancaires, mais à la capacité de produire une signature valide avec une clé privée. Bitcoin utilise la cryptographie sur courbe elliptique secp256k1 plutôt que RSA, mais la structure fondamentale demeure. Un utilisateur prouve qu’il contrôle des fonds en signant des transactions ; le réseau vérifie ces signatures au moyen des clés publiques, sans jamais voir les clés privées.
6. Déroulez Diffie-Hellman avec de petits nombres. Convenez publiquement d’un nombre premier p = 23 et d’une base g = 5. Alice choisit un secret a = 6 et envoie 5^6 mod 23 = 8. Bob choisit b = 15 et envoie 5^15 mod 23 = 19. Alice calcule 19^6 mod 23 = 2 ; Bob calcule 8^15 mod 23 = 2. Tous deux détiennent désormais le secret 2, alors que seuls 23, 5, 8 et 19 ont transité par le canal ouvert. Les systèmes réels utilisent des nombres de plusieurs centaines de chiffres, pour lesquels retrouver a ou b à partir des valeurs publiques est impossible en pratique.

Faits clés

Exercice neuf, six, trois, un

Vérification des faits

Les dates, les chiffres et les affirmations ont été vérifiés à l’aide des sources publiées listées ci-dessous.

• W. Diffie & M. Hellman, 'New Directions in Cryptography', IEEE Transactions on Information Theory (Nov 1976)
• R. Rivest, A. Shamir & L. Adleman, 'A Method for Obtaining Digital Signatures and Public-Key Cryptosystems', Communications of the ACM (Feb 1978)
• S. Singh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography (1999)
• S. Levy, Crypto: How the Code Rebels Beat the Government—Saving Privacy in the Digital Age (2001)