Il aura fallu quatre ans de calcul à 10.000 PC pour venir à bout d'un message chiffré par l'algorithme à courbes elliptiques de Certicom. La clé était de 109 bits, ce qui est tout de même largement inférieur aux versions commercialisées.

au sommaire

    k=281183840311601949668207954530684. Jusqu'à aujourd'hui, ce nombre valait 10.000 euros.

    Il ne s'agit pourtant pas du résultat d'un tirage de loterie, mais de la clé de chiffrement à 109 bits d'un message crypté grâce à un algorithme asymétriqueasymétrique à courbes elliptiques. Afin d'éprouver la solidité de sa solution, la société Certicom avait ainsi offert en 1997 dix mille euros à qui parviendrait à déchiffrer le message.
    Il a été découvert cette semaine, après 549 jours de calculs ininterrompus, menés par une armée de dix mille ordinateurs de bureaux réquisitionnés pour l'occasion à travers le monde. L'ensemble était coordonné par un mathématicienmathématicien de l'université de Notre-Dame aux Etats-Unis, et à mis à profit un aréopage hétéroclite de passionnés volontaires.

    Sur les dix mille euros gagnés, huit mille ont étés offerts à la Free Software FoundationFree Software Foundation, afin d'aider au développement des logiciels libres, et les deux mille euros restants reviennent aux utilisateurs dont les PC ont découvert la clé.

    L'algorithme n'est pas cassé

    Le chiffrement par courbes elliptiques se pose en alternative efficace à l'incontournable RSA. L'algorithme exploite un problème mathématique différent, qui est réputé pour sa solidité égale à RSA pour des clés de longueur bien inférieures (une clé ECC de 109 bits est considérée équivalente à une clé RSA de 600 bits). Cela le rend parfaitement adapté aux utilisations embarquées, où la mémoire et la puissance des processeurs ne sont pas suffisants pour réaliser en un temps convenable les calculs exigés par RSA.

    L'exploit de l'équipe de Notre Dame ne remet toutefois pas en cause la fiabilité de l'algorithme, puisque la clé a été découverte grâce à une attaque "frontale", qui consiste à essayer toutes les clés possibles, les unes après les autres.

    Les produits commerciaux de Certicom proposent par défaut une clé longue de 163 bits qui serait, selon l'éditeur "cent million de fois plus difficile à casser". Le chiffrement ECC n'est donc pas près d'être obsolète, sauf une découverte mathématique majeure. Et c'est précisément le but de ce type de défi, généralement lancés à la communauté cryptographique par les éditeurs eux-même : éprouver leurs solutions en situation réelle, face à une attaque difficile à mettre en oeuvre dans un laboratoire.

    En 2000, l'INRIA avait relevé le précédent défi de Certicom (109 bits aussi) en quatre mois et avec dix mille ordinateurs, et avait également empoché 10.000 euros. La clé était cependant choisie pour être plus simple à trouver. Ainsi, à longueur de clélongueur de clé égale, un sésame bien choisi résiste quatre ans, contre quatre mois pour une clé mal choisie. Voilà qui devrait faire réfléchir bien des utilisateurs de mot de passemot de passe !

    En savoir plus: