Rolinh

Rolinh' release

Test De Primalité De AKS: Un Danger Pour Les Algorithmes De Chiffrement Actuels?

Au menu d’aujourd’hui, un article qui inaugure une nouvelle catégorie: sécurité.

On entend vraiment tout et surtout n’importe quoi à propos de la sécurité quand celle-ci touche à l’informatique. Néanmoins, c’est un sujet important si l’on ne veut pas que des choses comme celle-ci se produisent.

Et, en tant que développeur web (à côté de mes études), j’ai déjà vu des trucs atroces fait par des “professionnels” (ex: une boucle qui récupère tout ce qui passe par GET ou POST et envoie, sans aucune vérification, tout cela dans la base de donnée (non, je ne citerais pas le site en question!)… je vous laisse imaginer ce que cela peut donner…).

Enfin bref, aujourd’hui je vais vous parler d’une question que je me suis posée suite à un cours de complexité que je suis à l’université.

En 2002, trois chercheurs indiens ont mis au point un algorithme qui permet de tester la primalité d’un nombre dans une complexité polynomiale. Il en existait déjà plusieurs  mais la plupart étaient des algorithmes probabilistes ou pouvant vérifier la primalité d’un certain type de nombre.

De plus, la complexité de cet algorithme, dénommé AKS (nom formé des trois initiales des chercheurs indiens), était initialement de O(log12(n)) mais a été assez vite réduite à O(log6(n)) donc polynomial de degré 6.

Vous ne voyez pas le rapport avec la sécurité? Et bien le voilà: de nombreux algorithmes de chiffrement se basent sur les nombres premiers, dont le très répandu RSA que j’utilise par exemple pour m’authentifier sur des machines via ssh.

Vivement que la cryptographie quantique se développe! Même si, dixit un de mes profs, “la sécurité quand tu y mets un doigt, ça te prend tout le corps”.