algorithme de Adleman et Huang

Imaginez un immense jeu de combinaisons : partir d'un élément G et répéter une même opération donne un élément Q. Calculer Q quand on connaît le nombre de répétitions est direct. Retrouver ce nombre à partir de G et Q est le problème du logarithme discret.

Pour certaines courbes hyperelliptiques de grand genre, l'algorithme d'Adleman et Huang remplace la recherche répétition par répétition par une collecte de relations entre petits éléments. Ces relations sont ensuite combinées pour retrouver le nombre caché.

L'algorithme d'Adleman et Huang est une méthode de calcul du logarithme discret dans un sous-groupe de la jacobienne d'une courbe hyperelliptique définie sur un corps fini. La jacobienne est constituée de classes de diviseurs de degré zéro et leur fournit une loi de groupe. Si une classe G engendre un sous-groupe d'ordre r et si Q appartient à ce sous-groupe, le problème consiste à trouver l'entier n tel que $Q=[n]GQ=[n]G$. La réponse est déterminée modulo r.

La méthode relève du calcul d'index. Elle choisit une base de facteurs formée de petits diviseurs premiers, cherche des classes qui se décomposent entièrement sur cette base, puis traduit ces décompositions en relations linéaires modulo r. Une résolution adaptée à l'anneau Z/rZ, ou menée séparément modulo les puissances premières composant r, attribue des logarithmes aux éléments de la base. Une relation supplémentaire contenant Q permet alors d'isoler n.

Le qualificatif « grand genre » est essentiel : l'intérêt de cette stratégie vient du nombre de décompositions exploitables dans ce régime. L'algorithme ne dit pas que tout logarithme discret sur toute courbe hyperelliptique est facile ; il fournit une attaque structurée pour la famille visée.

On se donne une courbe hyperelliptique de grand genre sur un corps fini, une classe G d'ordre r dans sa jacobienne et une classe Q appartenant au sous-groupe engendré par G. L'objectif est de déterminer n modulo r dans $Q=[n]GQ=[n]G$.
1. Choisir une base de petits diviseurs premiers.
2. Collecter assez de décompositions sur cette base.
3. Résoudre les relations linéaires modulo r.
4. Décomposer une classe faisant intervenir Q, puis en déduire n. Le calcul s'arrête lorsque n vérifie l'égalité de départ.

La méthode vise la jacobienne d'une courbe hyperelliptique de grand genre sur un corps fini. Il faut connaître la loi de groupe, l'ordre r du sous-groupe utilisé et deux classes G et Q, avec Q dans le sous-groupe engendré par G. Les relations collectées doivent être assez nombreuses pour déterminer les logarithmes utiles de la base de facteurs, avec les conditions d'inversibilité requises dans Z/rZ ou après traitement séparé des puissances premières composant r.

Un contre-cas apparaît si Q n'appartient pas au sous-groupe engendré par G : aucun entier n ne peut alors vérifier Q = [n]G. Autre blocage concret, si les classes testées ne se décomposent pas sur la base choisie, la matrice de relations reste insuffisante. Il faut élargir la base, poursuivre la collecte ou employer une autre méthode adaptée au groupe.

Voici un modèle réduit de la phase linéaire, et non une exécution sur une courbe réelle. Les données sont : un sous-groupe d'ordre 11 engendré par G ; une cible Q ; deux éléments A et B de la base de facteurs ; et trois relations collectées, $[3]G=A+B[3]G=A+B$, $[5]G=[2]A+B[5]G=[2]A+B$ et $Q+A=[9]GQ+A=[9]G$.

1. On note a et b les logarithmes de A et B en base G. Les deux premières relations donnent :
2. La soustraction de la première congruence à la seconde donne a ≡ 2 modulo 11.
3. Le remplacement de a par 2 dans la première donne b ≡ 1 modulo 11.
4. Si n est le logarithme de Q, la troisième relation donne n + a ≡ 9, donc n ≡ 7 modulo 11.

Le contrôle consiste à multiplier G par 7 dans le groupe et à vérifier que l'on obtient Q. L'exemple montre le mécanisme algébrique ; dans l'algorithme réel, le travail difficile est d'obtenir suffisamment de décompositions de diviseurs sur une base de facteurs.

Pour évaluer un système fondé sur une courbe hyperelliptique, on identifie d'abord le genre de la courbe, la taille du corps fini et le sous-groupe réellement employé. Un grand genre signale qu'une attaque par calcul d'index doit être examinée, au lieu de transposer automatiquement les estimations usuelles d'autres groupes.

Pendant une attaque, l'essentiel du travail consiste à produire des relations : on teste des classes et l'on conserve celles qui se décomposent entièrement sur la base de facteurs. Si trop peu de relations apparaissent, on modifie la base ou la stratégie de collecte.

Une fois la matrice assez riche, on résout correctement le système sur Z/rZ, en tenant compte des conditions d'inversibilité ou, si r est composite, en traitant séparément les puissances premières qui le composent, puis on traite la cible. Si l'ordre est très friable, l'algorithme de Silver-Pohlig-Hellman constitue une autre piste, car son critère décisif est la factorisation de l'ordre plutôt que le grand genre.

Le problème du logarithme discret. Il s'agit du problème à résoudre : retrouver n à partir de G et Q = [n]G. L'algorithme d'Adleman et Huang est une méthode particulière pour l'attaquer dans le cadre des courbes hyperelliptiques de grand genre.

L'algorithme de Silver-Pohlig-Hellman. Celui-ci exploite la factorisation de l'ordre du groupe. Le critère qui tranche est donc différent : ordre friable pour Silver-Pohlig-Hellman, structure hyperelliptique de grand genre et relations de petits diviseurs pour Adleman et Huang.

Une courbe elliptique. Une courbe elliptique est de genre 1. Le cadre annoncé ici est celui d'une courbe hyperelliptique de grand genre ; le simple fait que les deux objets soient des courbes algébriques ne rend pas l'attaque interchangeable.

Genre insuffisant. « Hyperelliptique » ne suffit pas : la contribution citée concerne le grand genre. Pour le genre 1, on est dans le cas elliptique ; pour un genre modéré, il faut comparer les coûts des attaques réellement applicables au lieu d'invoquer automatiquement cet algorithme.

Base trop étroite. Une petite base réduit le nombre d'inconnues, mais les décompositions complètes peuvent devenir trop rares. Le symptôme est une collecte qui ne fournit pas assez de lignes ; il faut ajuster la base ou poursuivre la recherche de relations.

Relations dépendantes. Avoir autant de relations que d'éléments de base ne garantit pas que le système détermine leurs logarithmes. Dans Z/rZ, il faut vérifier les conditions d'inversibilité nécessaires ; si r est composite, on peut résoudre séparément modulo les puissances premières qui le composent ou employer une méthode adaptée, comme la forme normale de Smith. À défaut, il faut collecter des relations supplémentaires.

Portée cryptanalytique. Une attaque contre une famille mathématique ne signifie pas que toute mise en œuvre utilisant le mot « hyperelliptique » est immédiatement cassée. La courbe, le corps, le genre, l'ordre du sous-groupe et les paramètres doivent être examinés ensemble.

La fiche fonction hyperelliptique éclaire le lien entre courbe, genre et jacobienne, qui fournit ici le groupe où vivent les diviseurs.

La fiche courbe elliptique présente le cas de genre 1 et aide à comprendre pourquoi le grand genre change le choix des attaques.

La fiche algorithme de Silver-Pohlig-Hellman expose une autre attaque du logarithme discret, guidée cette fois par la factorisation de l'ordre du groupe.