Le Logarithme Discret

tbowan

7 Juillet 2017

Le logarithme discret est une opération algébrique donc la difficulté est à la base de nombreux algorithmes de cryptographie moderne.

Cet article vous présente les concepts nécessaires à la définition de cette opération ainsi que ses faiblesses dans certains cas particuliers.

Après s'être fait la main rapidement dans un article précédent sur le chiffre de césar, nous allons poursuivre notre voyage cryptographique vers le problème du logarithme discret.

Pour ce trajet, nous allons aborder quelques notions-étapes d'Algèbre Générale qui permettront ensuite de définir et mieux comprendre cette opération si importante en cryptograhpie.

Les Groupes

Qui dit opération (algébrique) dit forcément structure (algébrique). C'est à dire un ensemble muni d'opérations pour manipuler les éléments, le tout obéissant à certaines règles.

Pour les développeurs, vous pouvez voir l'algèbre comme étant de la programmation orientée objets (POO). Les ensembles sont des classes, dont les objets sont les élements. Les axiomes sont comme des interfaces que vos classes doivent respecter.

Pour le cas qui nous occupe, nous allons utiliser des groupes finis. C'est à dire des ensembles contenant un nombre fini d'éléments et munis d'une opération binaire respectant les 4 propriétés suivants :

Il est d'usage de noter un groupe comme un couple contenant l'ensemble puis l'opération : (E, ⊕).

Le groupe fini le plus simple et facile à démontrer est l'ensemble des booléens1 muni du ou exclusif. L'opération est trivialement interne, et associative. L'élément neutre est faux et chaque élément est son propre inverse.

Plus proche des développeurs et de la cryptographie, les ensemble de nombres entiers modulo n, où on ne garde que les reste des divisions par n, sont des groupes avec l'addition (Z/nZ, +) et avec la multiplication (Z/nZ, .).

Voici un exemple en C++ pour les groupes (Z/nZ, +) pour n un nombre entier de base. Pour obtenir un groupe multiplicatif, il suffit d'implémenter operator*. Pour des groupes plus grands, il faudrait changer l'implémentation.

template<unsigned int N>
class Field
{
public:
    unsigned int value ;

public:
    Field()               : value(0) {}
    Field(unsigned int i) : value(i % N) { }

};

template <const unsigned int N>
Field<N> operator+(Field<N> const & lhs, Field<N> const & rhs)
{
    return Field<N>(lhs.value + rhs.value) ;
}

J'ai choisi d'implémenter les opérateurs en dehors de la classe pour me permettre d'en introduire de nouveaux dans la suite de cet article sans devoir réécrire tout le code. Voici deux autres opérateurs pratiques pour manipuler les éléments du groupe :

#include <iostream>

/**
 * Allow writing elements on a stream
 */
template <typename Stream, const unsigned int N>
Stream & operator<<(Stream & stream, Field<N> const & elem)
{
    stream << "{" << elem.value << "}" ;
    return stream ;
}

/**
 * Allow equality check between elements
 */
template <const unsigned int N>
bool operator==(const Field<N> & lhs, Field<N> const & rhs)
{
    return lhs.value == rhs.value ;
}

Générateur et Groupe engendré

Pour chaque élément d'un groupe (E, ⊕), on peut construire une suite en appliquant l'élément (a) itérativement, quel que soit l'ensemble et l'opération :

u0 = 0, u1 = a, u2 = a ⊕ a, u3 = a ⊕ a ⊕ a, …

Pour simplifier les écritures, on note cette suite comme un = n.a dans le cas de groupes additifs ou un = an pour les groupes multiplicatifs.

On dit alors que a engendre le sous groupe formé des valeurs successives de la suite. Dans le cas de groupes finis, cette suite revient sur l'élément neutre et se répète infiniment et fournis une correspondance très pratique avec (Z/nZ, ⊕)n est le nombre d'éléments de la suite (on dit que c'est un isomorphisme).

Le calcul d'un élément de la suite est un calcul facile, sa complexité est proportionnelle à la taille du nombre. Pour continuer sur l'exemple en C++, le code suivant est l'implémentation du générateur, en notation additive.

/**
 * Additive notation of generation
 */
template <const unsigned int N>
Field<N> operator*(unsigned int coef, Field<N> const & base)
{
    if (coef == 0) {
        return Field<N>() ;
    } else if (coef == 1) {
        return base ;
    } else {
        Field<N> big    = (coef / 2) * base  ;
        Field<N> little = (coef % 2) * base  ;
        return big + big + little ;
    }
}

On peut noter au passage que l'implémentation de cet opérateur en tant que composition interne au groupe lui donne une structure d'anneau. L'ensemble est alors muni de deux opérateurs respectant quelques propriétés pratiques (mais que nous n'aborderons pas pour rester dans le sujet).

template <const unsigned int N>
Field<N> operator*(Field<N> const & base, Field<N> const & exp)
{
    return base.value * exp ;
}

Le Logarithme Discret

On en arrive alors à la définition du logarithme discret qui consiste tout simplement à inverser cette correspondance.

Le logarithme discret de a en base g, noté logg(a), est l'entier n tel que a = gn.

Contrairement à l'exponentiation qui est facile, le calcul du logarithme discret peut être bien plus difficile. C'est sur cette disparité de complexité entre ces deux opérations qu'est basée la sécurité de certains algorithmes2.

Cette difficulté de résolution dépend du groupe et du générateur choisi. Nous allons donc aborder les faiblesses du groupe (Z/nZ,   + ) et (Z/nZ,  .). D'autres groupes sont égalements utilisés, comme les courbes elliptiques, mais ne seront pas abordés.

Faiblesse de (Z/nZ, +)

Les groupes pour lesquels le calcul du logarithme discret est facile sont donc déconseillés. C'est le cas du groupe additif (Z/nZ, +) qui nous sert d'exemple d'implémentation depuis le début.

En effet, ce groupe possède quelques propriétés qui facilitent la tâche d'un attaquant. Comme on l'a vu précédement, il est possible de construire un anneau à partir du groupe en lui ajoutant la multiplication (équivalente, ici au calcul d'exponentiation).

Résoudre le logarithme est ici équivalent à calculer une division dans l'anneau (Z/nZ, +, .).

Si le générateur est premier avec n, il a un inverse pour la multiplication qu'on peut calculer grâce à l'algorithme d'Euclide étendu qui a une complexité également polynomiale dans la taille de N. Le code C++ suivant montre une implémentation de cet algorithme :

template <const unsigned int N>
Field<N> inverse(Field<N> const & elem)
{
    int r1 = elem.value ; int u1 = 1 ; int v1 = 0 ;
    int r2 = N          ; int u2 = 0 ; int v2 = 1 ;

    while (r2 != 0) {
        int q = r1 / r2 ;

        int r3 = r1 - q * r2 ;
        int u3 = u1 - q * u2 ;
        int v3 = v1 - q * v2 ;

        r1 = r2 ; u1 = u2 ; v1 = v2 ;
        r2 = r3 ; u2 = u3 ; v2 = v3 ;
    }

    return Field<N>(u1) ;
}

Avec cet invere, le calcul du logarithme discret est immédiat puisque les effets de cet inverse annulent ceux du générateur : x.g.g−1 = x.1 = x

template <const unsigned int N>
Field<N> log(Field<N> const & elem, Field<N> const & base)
{
    Field<N> i = inverse(base) ;
    return elem * i ;
}

Si le générateur n'est pas premier avec n, le groupe engendré ne couvre pas toutes les valeurs de Z/nZ mais seulement une partie : les multiples du pgcd de n et g. En divisant les nombres et le générateur par ce pgcd, on obtiens un nouveau groupe sur lequel la résolution du logarithme discret donne la même valeur et le tour est joué.

Faiblesses de (Z/nZ, .)

Le choix du générateur est également important pour les groupes multiplicatifs comme (Z/nZ, .). Ceux-ci ont deux risques :

  1. Ne générer qu'un sous-groupe d'une taille ridiculement faible, rendant une attaque par force brute (ou par dictionnaire) faisable,
  2. Être vulnérable à la réduction de Pohlig-Hellman qui permet de simplifier les calculs lorsque l'ordre du groupe est multiple de deux nombres. Sans rentrer dans les détails, ce cas permet de calculer le logarithme discret dans deux bases plus faciles et de combiner les résultats.

On impose donc les contraintes suivantes lorsqu'on construit un groupe pour l'utiliser en cryptographie :

  1. n doit être grand, pour que sa résolution soit longue, typiquement, 2048 bits d'après les recommandations de l'ANSSI,
  2. n doit être un nombre premier, pour garantir d'avoir des générateurs qui engendrent tout le groupe,
  3. (n − 1)/2 est aussi un nombre premier, pour éviter d'affaiblir le système via un calcul par la réduction de Pohlig-Hellman,
  4. g doit être d'ordre n − 1, donc engendrer tout le groupe et éviter une attaque par force brute.

Ces précautions étant prises, les meilleurs algorithmes pour résoudre le logarithme discret restent exponentielles dans la taille de n. Ce qui est justement le but recherché et permet son utilisation dans un cadre cryptographique.

Conclusion

Le logarithme discret est une opération algébrique plutôt classique dans sa définition et dont la difficulté de calcul dépend à la fois du groupe utilisé et du générateur choisi.

Pour aller plus loin dans la définition mathématique du logarithme discret, je vous conseille la lecture de cet article : Le problème du logarithme discret en cryptographie


  1. Si on voulait être exact, l'ensemble contenant un seul élément forme un groupe avec n'importe quelle opération interne mais n'a pas franchement une utilité trépidente.

    L'ensemble vide n'est pas un groupe parce qu'il n'a pas la place pour un élément neutre. Par contre, l'ensemble contenant l'ensemble vide, peut être un groupe ...

  2. Comme l'échange de clé Diffie-Hellmann, le cryptosystème asymétrique El Gamal ou encore les algorithmes à base de courbes elliptiques.