Cryptographie : le logarithme discret devenu trop faible ?

Dans le domaine de la cryptographie, il existe de nombreux moyens différents pour chiffrer des messages, des moyens plus ou moins efficaces selon la méthode utilisée mais aussi et surtout selon la puissance de l’attaquant. En effet, il est bien important de noter qu’en théorie, parmi tous les différents systèmes utilisés de nos jours, il n’en existe aucun qui soit incassable. En théorie seulement, car en pratique, il faudrait plusieurs années, voire plusieurs dizaines d’années et même parfois plus, pour en casser certains, ce qui les rend presque inviolables à l’heure actuelle.

Mais peut-être plus pour longtemps, car une équipe de chercheurs du CNRS a semble-t-il réussi à trouver un algorithme capable de résoudre le problème du logarithme discret plus rapidement que tous les algorithmes étudiés auparavant. L’équipe souhaite continuer à affiner l’algorithme en question pour le moment, mais la nouvelle reste importante : le logarithme discret est la clé de voûte de nombreux cryptosystèmes actuels.

La cryptographie mise à mal

En cryptographie, on utilise ce qu’on appelle des clés, qui permettent de chiffrer et déchiffrer un message. Le problème, c’est que l’expéditeur comme le destinataire ont besoin de ladite clé, et il faut bien un moment où les deux compères doivent se l’échanger.

Si cet échange est fait de façon privée, il n’y a pas de soucis, mais des protocoles existent pour échanger de façon publique des clés, un échange qui peut alors être intercepté sans risques. Ou presque.

Ces protocoles sont basés sur les puissances de nombres : l’idée, c’est que vous décidez d’un nombre avec votre destinataire, de façon publique, et vous vous envoyez mutuellement des puissances de ce nombre. Si vous avez choisi 2, par exemple, vous pourrez envoyer 1024. Le tout est qu’un éventuel adversaire ne puisse pas deviner que la puissance choisie est 10.

Sur cet exemple, ça paraît un peu débile, mais il faut prendre en compte un autre détail : on utilise ici de l’arithmétique modulaire, un bien grand mot pour dire tout simplement qu’on tourne en rond. Par exemple, si on choisit d’avoir 26 lettres dans notre alphabet, une fois arrivés à 26, on repart à 0 : 27 devient 1, 28 devient 2, etc..

Dans notre exemple, 1024 devient alors 10 et l’adversaire ne peut pas forcément deviner la puissance correspondante, ou tout du moins assez difficilement : si bien sûr cela reste facile dans notre exemple, il faut penser à des nombres beaucoup plus importants, tellement énormes que tester toutes les puissances avec un simple bruteforce prendrait des années.

Le problème du logarithme discret, c’est ça : retrouver une puissance à partir de son résultat modulaire. Beaucoup de systèmes reposent sur le seul fait que ce problème ne peut être résolu facilement, et c’est pourquoi le nouvel algorithme dont nous parlons ici est si important : il va falloir soit augmenter encore et toujours la longueur des nombres utilisés, soit trouver de nouveaux systèmes, ce qui n’est pas si simple qu’il n’y paraît…

Via | Image : Harishpichukala