1978 Le cryptosystème résiste à l'attaque quantique

Personne n'a construit un ordinateur quantique beaucoup plus puissant qu'une calculatrice de poche, mais cela n'a pas empêché les gens de s'inquiéter des implications du monde de l'informatique post-quantique. Les plus inquiets sont les personnes qui s'appuient sur des codes cryptographiques pour protéger les informations sensibles. Lorsque le premier ordinateur quantique de taille décente est allumé, des codes auparavant sécurisés tels que l'algorithme RSA couramment utilisé deviendront instantanément cassables.

C'est pourquoi les cryptographes se précipitent pour rechercher des codes qui seront sécurisés dans le monde post-quantique. Aujourd'hui, Hang Dinh de l'Université du Connecticut et quelques amis montrent que les cryptographes en ont observé un depuis le début. Ils disent qu'un code peu utilisé développé par le mathématicien de CalTech Robert McEliece en 1978 peut résister à toutes les attaques connues des ordinateurs quantiques.

Tout d'abord, faisons une distinction entre les codes symétriques et asymétriques. Les codes symétriques utilisent des clés identiques pour crypter et décrypter un message. Les ordinateurs quantiques peuvent considérablement accélérer une attaque contre ce type de codes. Cependant, les codes symétriques ont une certaine protection. Doubler la taille de la clé contrecarre cette accélération. Il est donc possible pour les créateurs de code de garder une longueur d'avance sur les casseurs, du moins en théorie. (Bien qu'en pratique, l'argent sûr serait sur le prédateur dans ce jeu du chat et de la souris.)

Les codes asymétriques utilisent des clés différentes pour crypter et décrypter les messages. Dans les systèmes de cryptage dits à clé publique tels que l'algorithme RSA populaire, une clé publique est disponible pour quiconque peut l'utiliser pour crypter un message. Mais seuls ceux qui ont une clé privée peuvent déchiffrer les messages et cela, bien sûr, est gardé secret.

La sécurité de ces systèmes repose sur des fonctions dites de trappe : des étapes mathématiques faciles à faire dans un sens mais difficiles à faire dans l'autre. L'exemple le plus connu est la multiplication. Il est facile de multiplier deux nombres pour en obtenir un troisième, mais difficile de commencer par le troisième nombre et de déterminer lesquels l'ont généré, un processus appelé factorisation.

Mais en 1994, le mathématicien Peter Shor a imaginé un algorithme quantique qui pourrait factoriser beaucoup plus rapidement que n'importe quel homologue classique. Un tel algorithme fonctionnant sur un ordinateur quantique décent pourrait casser tous les systèmes de cryptage à clé publique connus, comme un enfant de 4 ans fou de Legoland.

Voici une idée de la façon dont cela fonctionne. Le problème de la factorisation est de trouver un nombre qui se divise exactement en un autre. Les mathématiciens font cela en utilisant l'idée de périodicité : un objet mathématique avec exactement la bonne périodicité devrait diviser le nombre exactement, aucun autre ne le fera.

Une façon d'étudier la périodicité dans le monde classique consiste à utiliser l'analyse de Fourier, qui peut décomposer un signal en ses ondes composantes. L'analogue quantique à cela est l'échantillonnage de Fourier quantique et le triomphe de Shor était de trouver un moyen d'utiliser cette idée pour trouver la périodicité de l'objet mathématique qui révèle les facteurs.

Grâce à Shor, tout code qui repose sur ce type d'asymétrie (c'est-à-dire presque tous les systèmes de cryptage à clé publique populaires) peut être craqué à l'aide d'une attaque quantique de Fourier.

Le cryptosystème McEliese est différent. Il est également asymétrique mais sa sécurité n'est pas basée sur la factorisation mais sur une version d'une énigme que les mathématiciens appellent le problème du supgroupe caché. Ce que Dinh et ses amis ont montré, c'est que ce problème ne peut pas être résolu en utilisant l'analyse de Fourier quantique. En d'autres termes, il est immunisé contre les attaques de l'algorithme de Shor. En fait, il est immunisé contre toute attaque basée sur l'échantillonnage de Fourier quantique.

C'est un gros problème. Cela signifie que tout ce qui est codé de cette manière sera en sécurité lorsque la prochaine génération d'ordinateurs quantiques commencera à ronger les cryptosystèmes à clé publique plus conventionnels. L'un de ces systèmes est Entropy, un réseau de communication peer-to-peer conçu pour résister à la censure basé sur le cryptosystème McEliese.

Mais Entropy est peu utilisé et il y a de bonnes raisons pour lesquelles d'autres ont résisté au système de cryptage McEliese. Le problème principal est que les clés publiques et privées sont quelque peu lourdes : une clé publique standard est une grande matrice décrite par pas moins de 2^19 bits.

Cela peut sembler moins un problème maintenant. Il est possible que le système McEleise devienne soudainement au centre de beaucoup plus d'attention plus de 30 ans après son invention.

Cependant, il convient de souligner que si le nouveau travail garantit la sécurité contre toutes les attaques quantiques connues, il ne fait rien de la sorte pour les futures attaques quantiques. Il est parfaitement possible que quelqu'un développe un algorithme quantique qui le déchire aussi facilement que Shor le peut avec l'algorithme RSA. Nos résultats n'excluent pas d'autres attaques quantiques (ou classiques), déclare Dinh and co.

Le scénario le plus probable pour les recherches futures est donc que les cryptographes renouvellent leurs efforts dans l'une des nombreuses autres directions qui semblent fructueuses, telles que les algorithmes basés sur les réseaux et la cryptographie multivariée.

Quoi qu'il en soit, attendez-vous à en savoir beaucoup plus sur la cryptographie post-quantique, à condition que les pouvoirs soient autorisés.

Réf : arxiv.org/abs/1008.2390 : Le cryptosystème McEliece résiste aux attaques d'échantillonnage de Fourier quantique

cacher