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 cryptographie.

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. Les ensembles sont des classes, dont les objets sont les éléments. Les axiomes sont comme des interfaces que vos classes doivent respecter.

Définition

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 suivantes :

• Composition interne : le résultat de l’opération est un élément de l’ensemble,
• Associativité : le résultat ne change pas en fonction de la façon de regrouper les termes,
• Élément neutre : il existe un élément (noté $e$ ou $0$) qui n’a aucun effet,
• Symétrique : quel que soit l’élément, il existe un élément qui l’annule.

Il est d’usage de noter un groupe comme un couple contenant l’ensemble puis l’opération : $(E, \oplus)$.

Exemple avec les booléens

Le groupe fini le plus simple et facile à démontrer est l’ensemble des booléens (vrai et faux, notés ⊤ et ⟂) muni du ou exclusif (noté ⊕).

• Interne : le résultat est toujours booléen.
• Associative : $a \oplus (b \oplus c) = (a \oplus b) \oplus c$, je vous laisse vérifier.
• Neutre : faux est l’élement neutre, le résultat prendra la valeur de l’autre opérande.
• Symétrique : chaque élément est son propre inverse, $a \oplus a = \perp$.

Si vous voulez allez au fond des choses, l’ensemble contenant un seul élément forme également un groupe avec n’importe quelle opération interne mais n’a pas franchement une utilité trépidante.

Exemple avec les nombres entiers

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, +)$ mais aussi 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 et vous permettre d’ajouter les exemples à votre fichier au fur et à mesure. 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, \oplus)$, on peut construire une suite en appliquant l’élément ($a$) itérativement

$$\begin{align} u_0 & = 0\\ u_1 & = a\\ u_2 & = a \oplus a\\ u_3 & = a \oplus a \oplus a \\ u_n & = a \oplus \dots \oplus a \end{align}$$

Pour simplifier les écritures, on rencontre deux notations pour cette suite :

1. $u_n = n.a$ dans le cas de groupes additifs,
2. $u_n = a^n$ pour les groupes multiplicatifs.

Dans le doute, si l’opération n’est pas clairement déterminée, on préfère la seconde, qui rend mieux le côté exponentiel de la chose.

On dit alors que $a$ engendre le sous groupe formé des valeurs successives de la suite. Dans le cas de groupes finis, cette suite est cyclique (elle revient un jour sur l’élément neutre pour se répéter ensuite) et fournis une correspondance très pratique avec $(Z/nZ, \oplus)$ où $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$, qu’on note $log_g(a)$, est l’entier $n$ tel que $a = g^n$.

Contrairement à l’exponentiation qui est facile, le calcul du logarithme discret est difficile. C’est sur cette disparité de complexité entre ces deux opérations qu’est basée la sécurité de certains algorithmes (e.g. l’échange de clé Diffie-Hellmann et le cryptosystème El Gamal).

Mais 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 également 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 avant, 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.

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 inverse au sens multiplicatif, le calcul du logarithme discret est immédiat puisque les effets de cet inverse annulent ceux du générateur :

$$n . a . a^{-1} = n . 1 = n$$

Dont voici l’implémentation :

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.

La réduction de Pohlig-Hellman. Lorsque l’ordre du groupe est le multiple de deux nombres, on peut répartir le calcul du logarithme dans les deux sous-groupes correspondants puis combiner les résultats. Une sorte de raccourci qui fait gagner beaucoup de temps.

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.

Et après ?

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. C’est cette difficulté qui est utilisée dans d’autres algorithmes comme l’échange de clé Diffie-Hellmann et le cryptosystème El Gamal.