Philosophie d'ingénierie : Adi Shamir

L’essentiel à retenir

• Il est le « S » de RSA, le premier cryptosystème à clé publique réellement utilisable. Avec Ron Rivest et Leonard Adleman, Adi Shamir a co-inventé RSA au MIT en 1977 — décrit publiquement cette année-là, puis publié dans Communications of the ACM en février 1978. Le schéma a rendu possible de chiffrer un message à destination de quelqu’un, et de vérifier ses signatures, sans jamais avoir partagé de secret au préalable ; sa sécurité repose sur la difficulté de factoriser de grands nombres. Ce travail leur a valu, à tous les trois, le prix Turing de l’ACM 2002.¹²
• Il a transformé un polynôme en un secret parfait. En 1979, Shamir publie « How to Share a Secret », un schéma à seuil qui répartit un secret entre n personnes de sorte que k d’entre elles, quelles qu’elles soient, puissent le reconstituer, tandis que k-1 n’apprennent absolument rien — pas un indice, pas le moindre rétrécissement de l’éventail des possibles. L’ensemble n’est bâti qu’à partir de points sur un polynôme.³
• C’est un maître de la cryptanalyse — il attaque pour défendre. Avec Eli Biham, à la fin des années 1980, Shamir a découvert publiquement la cryptanalyse différentielle, une méthode générale pour casser les chiffrements par blocs ; il avait auparavant cassé le cryptosystème à sac à dos de Merkle-Hellman. L’esprit même qui a conçu RSA a passé des décennies à apprendre à casser les choses, parce qu’en cryptographie c’est la seule façon honnête de savoir qu’un système est solide.⁴⁵
• Il ne cesse de convertir des mathématiques limpides en mécanismes concrets. Au-delà de RSA et du partage de secret, Shamir a co-inventé l’heuristique de Fiat-Shamir — une manière de transformer une preuve interactive en une signature non interactive à l’aide d’une fonction de hachage — ainsi que des schémas de cryptographie basée sur l’identité et de cryptographie visuelle. Professeur à l’Institut Weizmann depuis 1980, sa carrière est une longue démonstration que la théorie des nombres la plus profonde est une boîte à outils, et non une pièce de musée.¹⁶

Le principe

« On découvrit par la suite que la cryptanalyse différentielle était déjà connue — et tenue secrète — à la fois par IBM et par la National Security Agency. » — à propos de la technique que Biham et Shamir ont redécouverte au grand jour, en paraphrasant le récit historique⁴⁵

L’essentiel de l’ingénierie tend vers une démonstration. Vous écrivez la chose, vous l’exécutez, elle fonctionne, et ce fonctionnement fait office de preuve. La cryptographie refuse ce confort. Un chiffrement qui chiffre et déchiffre correctement n’a rien démontré quant à sa sécurité — un chiffrement cassé et un chiffrement incassable se comportent de façon identique jusqu’à ce que quelqu’un les attaque. La discipline a donc dû inventer un autre critère de vérité : un système est digne de confiance non pas quand il tourne, mais quand des gens sérieux ont tout tenté pour le casser et ont échoué. Toute la carrière de Shamir incarne ce critère. On sécurise un système en apprenant à casser des systèmes — attaquer pour défendre.⁴

L’expression la plus claire en est qu’il accomplit lui-même les deux moitiés. Il a bâti RSA, la pierre angulaire de la cryptographie à clé publique, et il a bâti le partage de secret de Shamir, un schéma à la sécurité prouvable, d’ordre théorique-informationnel.¹³ Mais il a aussi cassé le cryptosystème à sac à dos de Merkle-Hellman — un schéma à clé publique rival qui semblait sûr et ne l’était pas — et il a co-découvert la cryptanalyse différentielle, une méthode assez générale pour menacer le Data Encryption Standard lui-même.⁴⁵ Ce ne sont pas deux carrières. C’est une seule discipline. Le travail de construction vous dit ce qui est possible ; le travail de destruction vous dit ce qui est réel. Un cryptographe qui se contente de construire ne fait que deviner, et la preuve la plus glaçante en est apparue plus tard, lorsqu’on a découvert qu’IBM et la NSA connaissaient la cryptanalyse différentielle depuis le milieu des années 1970 et l’avaient classée secrète — ce qui signifie que la communauté publique concevait des chiffrements en restant aveugle à une attaque que ses adversaires détenaient déjà.⁴⁵

Le principe comporte une seconde moitié, plus discrète et tout aussi porteuse : la force consistant à transformer une idée mathématique limpide en un mécanisme concret. Le partage de secret n’est que de l’interpolation polynomiale — un fait que tout élève rencontre en algèbre, à savoir que deux points fixent une droite et trois fixent une parabole. Shamir a vu que ce même fait, lu à l’envers, est une primitive de sécurité : distribuez des points, et la courbe reste cachée jusqu’à ce qu’un nombre suffisant d’entre eux soit réuni.³ RSA n’est que de l’exponentiation modulaire et la difficulté de la factorisation.² L’heuristique de Fiat-Shamir n’est que le remplacement du tirage à pile ou face d’un vérificateur par un hachage.⁶ Trouvez la structure mathématique limpide, puis lisez-la comme un mécanisme. Le génie réside rarement dans des mathématiques nouvelles — il consiste à voir que de vieilles mathématiques, observées sous le bon angle, sont déjà la chose que vous avez besoin de construire.

Le contexte

Adi Shamir est né le 6 juillet 1952 à Tel-Aviv, en Israël.¹ Il obtient sa licence de mathématiques à l’université de Tel-Aviv en 1973, puis rejoint l’Institut Weizmann des sciences pour ses études supérieures, où il décroche un master en informatique en 1975 et un doctorat en 1977.¹ Son calendrier, comme celui du domaine, était sur le point de basculer : 1977 fut l’année où la cryptographie à clé publique passa de l’idée alléchante au système opérationnel.

Après le doctorat, il passe un an comme chercheur postdoctoral à l’université de Warwick en Angleterre, puis rejoint le Massachusetts Institute of Technology, où il est membre du personnel de recherche de 1977 à 1980.¹ C’est au MIT que RSA voit le jour. Ron Rivest, le cryptographe, poursuivait un schéma à clé publique inspiré de l’idée de Diffie-Hellman selon laquelle deux parties pouvaient établir un secret sans secret partagé ; Shamir et Adleman étaient ses collaborateurs et, surtout, ses adversaires — Rivest proposait un schéma, et Shamir et Adleman le cassaient, encore et encore, jusqu’à ce que l’un survive. Celui qui survécut fut RSA, nommé d’après leurs trois noms, publié en 1977 puis dans Communications of the ACM en 1978.² (À leur insu, le mathématicien britannique Clifford Cocks, au GCHQ, avait décrit un système équivalent dans un document classifié de 1973 resté secret jusqu’en 1997 — autre exemple d’un domaine qui construisait dans l’obscurité pendant que les services de renseignement observaient.)²

En 1980, Shamir revient à l’Institut Weizmann, où il est depuis lors professeur au département d’informatique et de mathématiques appliquées, occupant plus tard également une chaire d’invité à l’École normale supérieure de Paris.¹ Presque tout ce qui le définit — le partage de secret, l’assaut contre les chiffrements à sac à dos, la cryptanalyse différentielle avec son étudiant Eli Biham, l’heuristique de Fiat-Shamir, la cryptographie visuelle avec Moni Naor, les attaques par cube, les dispositifs de factorisation TWIRL et TWINKLE — est sorti de Weizmann. En 2002, l’Association for Computing Machinery a décerné à Rivest, Shamir et Adleman le prix Turing, la plus haute distinction de l’informatique, pour leurs contributions à la cryptographie à clé publique.¹²

Le travail

Le partage de secret de Shamir : une parabole qui garde un secret

Commençons par là, car c’est le principe sous sa forme la plus pure et la plus belle. Supposons que vous déteniez un secret — une clé maîtresse, le code de lancement, le mot de passe d’un trésor — et que vous vouliez le répartir entre cinq dépositaires de sorte que trois d’entre eux, quels qu’ils soient, puissent ensemble le retrouver, mais que deux d’entre eux ne puissent rien apprendre. Vous pourriez tenter de découper physiquement la clé en morceaux, mais cela fuit : chaque morceau rétrécit l’éventail des possibles. L’intuition de Shamir en 1979, dans « How to Share a Secret », fut que les polynômes résolvent déjà exactement ce problème.³

L’astuce consiste à lire à l’envers un fait appris à l’école primaire. Deux points déterminent une droite unique ; trois points déterminent une parabole unique ; en général, k points déterminent un polynôme unique de degré k-1. Ainsi, pour partager un secret entre n personnes avec un seuil de k, vous dissimulez le secret dans le terme constant d’un polynôme aléatoire de degré (k-1) — la valeur de la courbe en x = 0 — et vous remettez à chaque personne un point sur cette courbe.³ k personnes quelconques peuvent interpoler la courbe unique passant par leurs points et y lire sa valeur en zéro. Mais la sécurité, c’est ce qu’il y a d’étonnant : avec seulement k-1 points, la courbe n’est pas simplement difficile à trouver — elle est véritablement indéterminée. Pour chaque valeur de secret possible, il existe exactement une courbe du bon degré qui passe par leurs points et atteint cette valeur en zéro. Comme le garantit le schéma de Shamir, « la connaissance de k-1 parts ou moins laisse S complètement indéterminé ».³ En deçà du seuil, rien n’est révélé ; au seuil, tout est révélé. Cette frontière nette du tout-ou-rien est ce qui en fait un schéma à la sécurité d’ordre théorique-informationnel — sûr non pas parce que le casser est coûteux en calcul, mais parce que l’information, tout simplement, n’est pas là.³

Pourquoi cela compte en tant qu’ingénierie : ce schéma est l’exemple canonique de Shamir lisant les mathématiques comme un mécanisme. Il n’a pas inventé l’interpolation polynomiale — elle est vieille de plusieurs siècles. Il a vu que son mode d’échec — le fait qu’on ne puisse pas reconstituer une courbe à partir de trop peu de points — est précisément une propriété de sécurité, et que son mode de succès — le fait qu’un nombre suffisant de points la fixe exactement — est précisément une propriété de reconstitution. Le même fait, utilisé dans les deux sens, devient une primitive cryptographique qui tourne aujourd’hui au cœur des modules matériels de sécurité, de la conservation de cryptomonnaies et des autorités de certification. Des mathématiques limpides, lues comme un outil.³

RSA : chiffrer à destination d’un inconnu

RSA a répondu à une question qui paraissait presque paradoxale : comment deux personnes qui ne se sont jamais rencontrées, et qui ne communiquent que sur un canal écouté par un adversaire, peuvent-elles échanger des secrets ? La cryptographie classique exigeait une clé partagée établie au préalable — mais on ne peut pas partager une clé sur le canal même que l’on cherche à protéger. La percée, que Rivest, Shamir et Adleman ont transformée en système opérationnel en 1977, fut la fonction à sens unique à trappe : une opération facile à calculer dans un sens et infaisable à inverser, sauf si l’on détient une information secrète.²

La trappe de RSA, c’est la factorisation. Vous choisissez deux grands nombres premiers et vous les multipliez pour obtenir un module n ; n et un exposant public deviennent votre clé publique, que vous pouvez diffuser au monde entier. N’importe qui peut s’en servir pour vous chiffrer un message, par exponentiation modulaire. Mais le déchiffrement requiert la clé privée, qui ne peut être dérivée que des deux nombres premiers d’origine — et retrouver ces nombres premiers à partir de leur produit revient à factoriser un très grand nombre, un problème sans solution efficace connue.² Comme le veut la formulation, s’il est faisable de construire les clés, « lorsqu’on ne dispose que de e et de n, il est infaisable de calculer les racines e-ièmes modulo n ».² Vous publiez le cadenas ; vous seul détenez la clé ; et l’écart entre les deux est la difficulté de la factorisation.

Le rôle précis de Shamir mérite d’être énoncé clairement, car c’est encore le principe : il était, aux côtés d’Adleman, le cryptanalyste du trio. L’histoire de l’invention de RSA est une histoire de cassage — Rivest proposait des schémas candidats et Shamir et Adleman les attaquaient jusqu’à ce qu’un seul résiste à l’assaut. Le schéma survivant était solide précisément parce qu’il avait survécu aux attaques de deux personnes déterminées à le casser. RSA n’est pas un système qui fut conçu pour être sûr et dont on a ensuite espéré qu’il le serait ; c’est un système qui a mérité cette affirmation en survivant à ses propres auteurs.²

Attaquer pour défendre : casser les sacs à dos et la cryptanalyse différentielle

Si RSA montre Shamir en train de construire, le corpus de travail suivant le montre en train de faire ce dont le domaine a encore plus besoin : casser. À la fin des années 1970, le cryptosystème à sac à dos de Merkle-Hellman était un rival de premier plan de RSA, sa sécurité reposant sur le problème de la « somme de sous-ensemble », qui est NP-complet et paraissait donc redoutablement difficile. Shamir l’a cassé. Il a montré que les sacs à dos particuliers employés par Merkle-Hellman n’étaient pas le cas général difficile, mais un cas spécial et structuré que l’on pouvait résoudre efficacement — démolissant un schéma auquel beaucoup s’étaient fiés.¹ La leçon est de celles que la cryptographie réapprend sans cesse : qu’un problème soit difficile en général ne signifie pas que les instances que votre chiffrement utilise réellement sont difficiles. Seule l’attaque révèle la différence.

Son travail cryptanalytique le plus influent est venu avec son étudiant Eli Biham, à la fin des années 1980 : la cryptanalyse différentielle, publiée vers 1990.⁴⁵ C’est une technique générale qui étudie comment des différences entre des paires d’entrées d’un chiffrement se propagent en différences dans la sortie. Si certaines différences d’entrée conduisent à certaines différences de sortie avec une probabilité non aléatoire, ce biais statistique est une fissure — une fuite d’information sur la clé — et Biham et Shamir l’ont transformé en attaques contre toute une gamme de chiffrements par blocs, dont une faiblesse théorique du Data Encryption Standard, alors le chiffrement le plus important du monde.⁴⁵

Puis le domaine a appris quelque chose d’humiliant. En 1994, Don Coppersmith a révélé qu’IBM — qui avait conçu DES dans les années 1970 — connaissait la cryptanalyse différentielle « dès 1974 », que s’en défendre avait été un objectif de conception explicite de DES, et que la NSA avait insisté pour que la technique reste classifiée parce que « la divulgation des considérations de conception révélerait la technique de la cryptanalyse différentielle, une technique puissante utilisable contre de nombreux chiffrements ».⁴⁵ Les mystérieuses constantes internes de DES, longtemps soupçonnées de cacher une porte dérobée, se révélaient cacher une défense contre une attaque que le public ignorait. L’épisode est le plus solide argument possible en faveur du principe de Shamir. Pendant deux décennies, la communauté ouverte avait conçu des chiffrements et leur avait fait confiance tout en restant aveugle à une attaque fondamentale que les adversaires détenaient déjà. La redécouverte publique de Biham et Shamir n’a pas affaibli la cryptographie — elle l’a renforcée, en traînant l’attaque dans la lumière où chacun pouvait concevoir pour s’en prémunir. Attaquer pour défendre, à l’échelle d’un domaine entier.⁴⁵

Fiat-Shamir et l’ampleur de la boîte à outils

Le même instinct — trouver la structure limpide, la lire comme un mécanisme — parcourt les autres inventions de Shamir. L’heuristique de Fiat-Shamir, avec Amos Fiat au milieu des années 1980, a résolu un problème concret posé par les preuves interactives de connaissance : de telles preuves exigent un va-et-vient en direct, où un vérificateur envoie un défi aléatoire et un prouveur répond. Fiat et Shamir ont vu que le seul rôle du vérificateur était de fournir de l’aléa imprévisible, et qu’une fonction de hachage cryptographique appliquée au propre message du prouveur pouvait fournir cet aléa tout aussi bien — transformant une conversation en une preuve unique, autonome et non interactive, c’est-à-dire une signature numérique.⁶ Cette seule transformation sous-tend une large fraction des schémas de signature et des systèmes à divulgation nulle de connaissance modernes. Il a aussi proposé la cryptographie basée sur l’identité (utilisant l’identité d’une personne comme clé publique), co-inventé la cryptographie visuelle avec Moni Naor (découper une image en transparents qui ne révèlent un secret qu’une fois empilés — un partage de secret que l’on peut voir), et développé plus tard les attaques par cube ainsi que les dispositifs de factorisation TWIRL et TWINKLE.¹ Partout, le motif tient : un fragment connu de mathématiques, tourné dans le bon sens, devient un outil.

La méthode

Parcourez RSA, le partage de secret, les sacs à dos cassés, la cryptanalyse différentielle et Fiat-Shamir, et les mêmes engagements reviennent. La méthode de Shamir tient moins du slogan que d’un ensemble d’habitudes permanentes.

Construire et casser des mêmes mains. Le geste déterminant consiste à refuser la division du travail entre ceux qui construisent les systèmes et ceux qui les attaquent. Shamir a co-inventé RSA et cassé le sac à dos de Merkle-Hellman ; il a prouvé la sécurité du partage de secret et co-découvert la cryptanalyse différentielle. La leçon dépasse de loin la cryptographie : vous ne comprenez pas ce que vous avez construit tant que vous n’avez pas tenté, pour de bon, de le mettre en échec. C’est la barrière de la preuve érigée en mode de vie — « ça marche » n’est pas une preuve de sécurité ; « des gens sérieux ont tenté de le casser et n’y sont pas parvenus » en est une.²⁴

Ne faire confiance qu’à ce qui survit à l’attaque. Un chiffrement qui a simplement été conçu avec soin est un espoir ; un chiffrement qui a résisté à une cryptanalyse concentrée est un fait. La discipline consiste à traiter votre propre système comme coupable jusqu’à preuve d’attaque — à présumer l’existence d’une fissure et à partir à sa recherche, plutôt que d’attendre qu’un adversaire la trouve à votre place. C’est la forme cryptographique de « Reflections on Trusting Trust » de Thompson : l’intuition fondatrice que l’on ne peut faire confiance à ce que l’on n’a pas examiné de façon adverse, car la menace que vous ne voyez pas est celle qui vous prend — comme l’a prouvé l’histoire classifiée de la cryptanalyse différentielle.⁴⁵

Lire les mathématiques comme un mécanisme. Les primitives les plus puissantes sont rarement des mathématiques nouvelles ; ce sont de vieilles mathématiques vues sous un angle nouveau. L’interpolation polynomiale devient le partage de secret ; la difficulté de la factorisation devient une trappe ; une fonction de hachage devient le substitut d’un vérificateur interactif. L’habitude consiste à regarder une structure limpide et à demander non pas « qu’est-ce que c’est ? » mais « que pourrait faire ceci ? » — la même économie de moyens qui fait que les primitives les plus solides sont aussi les plus simples, dans l’esprit du produit minimum digne.³⁶

Préférer la sécurité prouvable là où on peut l’obtenir, et la sécurité méritée partout ailleurs. Le partage de secret est sûr d’ordre théorique-informationnel — aucun ordinateur, si puissant soit-il, ne peut extraire le secret de trop peu de parts, parce que l’information n’est pas présente.³ RSA est sûr d’un point de vue calculatoire — sûr seulement tant que la factorisation reste difficile. Shamir travaille aux deux niveaux et reste précis sur celui dont il dispose. La discipline consiste à savoir exactement sur quoi repose votre revendication de sécurité, et à ne jamais confondre « personne ne l’a encore cassé » avec « il ne peut pas être cassé ». C’est la qualité est la seule variable appliqué à la confiance : la seule chose qui compte est de savoir si la garantie est réelle.²³

Se méfier du cas particulier qui se cache dans le cas général. Casser Merkle-Hellman a appris au domaine qu’un problème NP-complet en général ne dit rien des instances spécifiques qu’un chiffrement utilise réellement.¹ L’habitude permanente consiste à soupçonner que la version commode et structurée d’un problème difficile — celle qui est assez facile pour bâtir un système autour d’elle — peut être exactement la version facile à casser. Le même scepticisme que Leslie Lamport a porté aux systèmes distribués : ne faites pas confiance à la propriété que vous avez supposée ; trouvez la condition précise sous laquelle elle tient réellement.

La chaîne d’influence

Ceux qui l’ont façonné

Diffie, Hellman et l’idée de la clé publique. RSA fut une réponse directe à la proposition de Whitfield Diffie et Martin Hellman, en 1976, selon laquelle un secret pouvait être établi sans clé pré-partagée. Diffie-Hellman a posé la question — un cryptosystème à clé publique devrait exister — et Rivest, Shamir et Adleman ont bâti la première réponse concrète.² (Influence directe)

Ron Rivest et Leonard Adleman. La collaboration RSA fut véritablement à trois mains : Rivest le proposeur acharné, Shamir et Adleman les casseurs acharnés. La structure adverse de ce partenariat — proposer, attaquer, recommencer — a façonné la conviction de toute une vie chez Shamir : construction et cryptanalyse sont une seule discipline.² (Influence formatrice)

La tradition de la théorie des nombres. Le geste signature de Shamir — lire les mathématiques classiques comme un mécanisme cryptographique — descend de la longue tradition qui relie la théorie des nombres, la difficulté de la factorisation et l’algèbre des corps finis au calcul. Son génie résidait dans l’application, non l’invention, de ces mathématiques. (Influence formatrice)

Ceux qu’il a façonnés

Eli Biham et la cryptanalyse moderne. La cryptanalyse différentielle, développée avec son étudiant Biham, est devenue un outil standard contre lequel tout concepteur sérieux de chiffrement par blocs doit désormais se défendre — elle a refaçonné la manière de bâtir les chiffrements, y compris les critères de conception de l’Advanced Encryption Standard.⁴⁵

Tout l’écosystème de la clé publique. RSA a sous-tendu des décennies de communication sécurisée, de signatures numériques et d’échange de clés. Chaque fois qu’un navigateur établit une connexion sécurisée ou vérifie un certificat, il s’appuie sur les fondations de la clé publique que Shamir a contribué à poser.²

Les schémas à divulgation nulle de connaissance et de signature. L’heuristique de Fiat-Shamir est un cheval de trait sous une vaste gamme de signatures numériques et de systèmes de preuve à divulgation nulle de connaissance modernes, y compris ceux désormais centraux dans la cryptographie de préservation de la vie privée et de la blockchain.⁶

Le fil conducteur

Shamir est la clé de voûte de la sécurité dans cette série — la figure qui rend le reste de la pile digne de confiance. Tim Berners-Lee a bâti un web destiné à tous, mais un web sur lequel vous pouvez acheter, gérer vos comptes et vous exprimer librement dépend entièrement de la cryptographie à clé publique pour ses connexions TLS et ses certificats signés — c’est-à-dire qu’il dépend de RSA et du domaine que Shamir a contribué à fonder. Thompson et Ritchie nous ont donné les systèmes sur lesquels nous tournons et, dans « Reflections on Trusting Trust », l’avertissement fondateur que l’on ne peut faire confiance à ce que l’on n’a pas examiné de façon adverse — l’instinct même sur lequel Shamir a bâti une carrière. Et Leslie Lamport a donné aux systèmes distribués la discipline de définir la correction avec précision et de la prouver, face à des adversaires byzantins au comportement arbitraire ; le partage de secret de Shamir est cette même impulsion sous forme cryptographique, une primitive dotée d’une preuve plutôt que d’un espoir. Là où Berners-Lee dit ceci est pour tous et Thompson dit ne faites confiance à rien que vous n’ayez bâti, Shamir dit : je vais vous construire quelque chose de sûr, puis je passerai ma vie à tenter de le casser — parce que c’est la seule façon, pour vous comme pour moi, de savoir que c’est réel. (Pont de la série)

Ce que j’en retiens

La leçon que je retiens de Shamir, c’est ne faire confiance qu’à ce qui survit à l’attaque. Mon instinct, comme celui de la plupart des bâtisseurs, est de traiter le code qui fonctionne comme une preuve — les tests passent, la démonstration tourne, on livre. La cryptographie interdit ce confort, parce qu’un système cassé et un système sain semblent identiques jusqu’à ce que quelqu’un les attaque, et la réponse de Shamir est d’être ce quelqu’un en premier. Il a cassé les chiffrements à sac à dos ; lui et Adleman ont cassé les schémas candidats de Rivest jusqu’à ce que RSA survive ; lui et Biham ont cassé DES assez gravement pour exposer ce que les services de renseignement avaient caché pendant vingt ans. Alors, quand je construis quelque chose aujourd’hui — un flux d’authentification, une frontière de permissions, un pipeline de données — j’essaie de coiffer le chapeau de l’attaquant avant qu’un attaquant ne le fasse, de présumer l’existence d’une fissure et de partir en chasse plutôt que d’attendre qu’on me la signale. La confiance qui compte n’est pas « je ne vois pas comment ça casse » ; c’est « j’ai tenté de toutes mes forces de le casser et je n’y suis pas parvenu ».

La seconde leçon, c’est que les mécanismes les plus puissants sont des mathématiques limpides lues dans le bon sens. Le partage de secret m’a un peu désarçonné quand je l’ai compris pour la première fois — ce n’est que le fait scolaire que des points déterminent un polynôme, et pourtant il produit un secret qui est, de façon prouvable, théorique-informationnelle, à l’abri. Shamir n’a pas inventé des mathématiques plus ardues ; il a vu que des mathématiques qu’il possédait déjà étaient, sous un certain angle, exactement une primitive de sécurité. Cela a changé ma façon de regarder les structures déjà devant moi. Le hachage que j’utilise pour des recherches peut être un engagement ; la redondance que j’ai ajoutée pour la fiabilité peut être un schéma à seuil ; la contrainte que je traitais comme une gêne peut être le cadenas. Le talent ne consiste pas toujours à inventer quelque chose de nouveau — il consiste à reconnaître que la chose limpide que vous comprenez déjà est, tournée dans le bon sens, le mécanisme dont vous aviez besoin.

FAQ

Pour quoi Adi Shamir est-il connu ?

Adi Shamir est un cryptographe israélien et professeur à l’Institut Weizmann des sciences, surtout connu comme le « S » de RSA — le premier cryptosystème à clé publique réellement utilisable, qu’il a co-inventé avec Ron Rivest et Leonard Adleman au MIT en 1977. Les trois ont partagé le prix Turing de l’ACM 2002 pour ce travail. Il a aussi inventé le partage de secret de Shamir (1979), co-découvert la cryptanalyse différentielle avec Eli Biham, et co-créé l’heuristique de Fiat-Shamir, parmi de nombreuses autres contributions à la cryptographie.¹²

Qu’est-ce que le partage de secret de Shamir ?

C’est une méthode, publiée par Shamir en 1979 dans « How to Share a Secret », pour répartir un secret entre n personnes de sorte que k d’entre elles, quelles qu’elles soient, puissent le reconstituer, mais que k-1 n’apprennent rien. Le secret est dissimulé dans le terme constant d’un polynôme aléatoire de degré k-1, et chaque personne reçoit un point sur cette courbe. Parce que k points déterminent de façon unique un polynôme de degré (k-1), k parts quelconques reconstituent le secret — tandis que moins de k le laissent « complètement indéterminé », ce qui confère au schéma une sécurité d’ordre théorique-informationnel.³

Qu’est-ce que le « S » de RSA, et comment fonctionne RSA ?

Le « S », c’est Shamir ; RSA signifie Rivest, Shamir et Adleman. RSA est un cryptosystème à clé publique : chaque utilisateur dispose d’une clé publique que tout le monde peut utiliser pour lui chiffrer des messages ou vérifier ses signatures, et d’une clé privée que lui seul détient. Sa sécurité repose sur une trappe — la clé publique est construite à partir du produit de deux grands nombres premiers, et retrouver la clé privée requiert de factoriser ce produit pour revenir à ses nombres premiers, ce qui est infaisable d’un point de vue calculatoire pour des nombres assez grands. RSA a été publié dans Communications of the ACM en 1978.²

Qu’est-ce que la cryptanalyse différentielle ?

La cryptanalyse différentielle est une technique générale, découverte publiquement par Eli Biham et Adi Shamir à la fin des années 1980, pour attaquer les chiffrements par blocs en étudiant comment des différences entre des paires d’entrées se propagent en différences dans la sortie. Des biais statistiques dans cette propagation peuvent laisser fuir de l’information sur la clé secrète ; Biham et Shamir s’en sont servis pour trouver une faiblesse théorique de DES. On a découvert par la suite qu’IBM et la NSA connaissaient la technique depuis le milieu des années 1970 et l’avaient tenue classifiée, ayant secrètement conçu DES pour y résister.⁴⁵

Sources