L’algo Rho de Pollard

(Pollard, 1975) On rappelle qu’on cherche à factoriser un entier \(n\), qui est le produit de deux nombres premiers distincts \(p\) et \(q\) (i.e., on cherche à retrouver un des deux facteurs \(p\), l’autre facteur se calculant ensuite simplement). Cet algorithme n’est pas une attaque sur RSA à proprement parler, car il ne fonctionne que si le nombre à factoriser n’a que de petits facteurs, ce qui n’est pas le cas pour RSA.

Idée

L’idée de l’algorithme Rho et que si on parvient à trouver deux entiers distincts \(x\) et \(x’\) inférieurs à \(n\) et tels que \(x \equiv x’\ [p]\), alors \(x-x’\) est multiple de \(p\). Comme \(n\) est également multiple de \(p\), le PGCD de \(x-x’\) et \(n\) sera multiple de \(p\), ce qui signifie qu’il sera égal à \(p\) ou \(n\). Ainsi, on teste successivement des paires \((x,x’)\) d’entiers de \([0,n-1]\) jusqu’à trouver une paire telle que le PGCD de \(x-x’\) et \(n\) est supérieur à \(1\) mais inférieur à \(n\). Cette méthode s’implémente facilement :

import random

def factor(n):
    while True:
        a = random.randint(0, n-1)
        b = random.randint(0, n-1)
        d = pgcd(a-b, n)
        if d != 1:
            break
    if d == n:
        return None
    else:
        return d

Et pour \(n = 15770708441\) on obtient bien :

>>> factor(15770708441)
115979

Le paradoxe des anniversaires nous dit qu’on obtient une solution après avoir testé environ \(1.25\sqrt{p}\) valeurs en moyenne. Le problème principal de cette méthode est qu’on doit calculer le PGCD de \(a-b\) et \(n\) à chaque itération, ce qui est coûteux en temps. L’algorithme Rho est basé sur cette idée mais permet de grandement réduire le nombre de calculs de PGCD.

L’algorithme Rho

On se donne une fonction \(f(x)\) qui soit suffisamment proche d’une fonction aléatoire (au sens statistique du terme, en pratique on prend souvent \(f(x) = x^2+1\)), ainsi qu’une “valeur initiale” \(x_1\), puis on pose \(x_{i+1} = f(x_i)\). On cherche \(x_i, x_j\) tels que le PGCD de \(x_i-x_j\) et \(n\) soit supérieur à \(1\). On pourrait tout simplement calculer le PGCD pour toutes les paires \((x_i,x_j)\), mais on peut faire plus simple.

Pour cela, on commence par remarquer que si \(x_i \equiv x_j\ [p]\), alors \(f(x_i) \equiv f(x_j)\ [p]\) (car \(f\) est un polynôme à coefficients entiers, et le calcul de \(f(x)\) ne fait donc intervenir que des opérations qui respectent les congruences). Comme \(x_{i+1} = f(x_i)\) et \(x_{j+1} = f(x_j)\), on obtient
\[ x_{i+1} \mod p = (f(x_i) \mod n) \mod p = f(x_i) \mod p \]
car \(p\) divise \(n\). De même
\[ x_{j+1} \mod p = f(x_j) \mod p \]
et donc \(x_{i+1} \equiv x_{j+1}\ [p]\). En répétant le raisonnement, on obtient que si \(x_i \equiv x_j\ [p]\), alors \(x_{i+k} \equiv x_{j+k}\ [p]\) pour tout entier positif \(k\). Pour visualiser ce qui se passe, il est intéressant de construire un graphe orienté dont les sommets sont les entiers de \(\mathbb{Z}_p\) et les arêtes relient \(x_i\) à \(x_{i+1}\). Par exemple pour \(n = 7171 = 71 \times 101\), \(f(x) = x^2+1\), et \(x_1 = 1\), on obtient les valeurs suivantes de \(x_i\) :
\[ \begin{array}{lllll}
1 & 2 & 5 & 26 & 677 & 6557 & 4105 \\
6347 & 4903 & 2218 & 219 & 4936 & 4210 & 4560 \\
4872 & 375 & 4377 & 4389 & 2016 & 5471 & 88
\end{array} \]
et en réduisant modulo \(71\) :
\[ \begin{array}{lllll}
1 & 2 & 5 & 26 & 38 & 25 & 58 \\
28 & 4 & 17 & 6 & 37 & 21 & 16 \\
44 & 20 & 46 & 58 & 28 & 4 & 17
\end{array} \]
et le cycle \((58, 28, \dots , 46, 58)\) se répète. En construisant un graphe comme décrit plus haut on obtient :


ce qui explique également pourquoi cet algorithme est appelé “algorithme Rho”.

On veut donc trouver \(i\) et \(j\) tels que \(x_i\) et \(x_j\) soient à la même position sur le cycle. On note \(\ell\) la longeur du cycle. Afin de ne pas tester toutes les valeurs, on se restreint au cas où \(j = 2i\). Pour voir qu’il est toujours possible de trouver une collision ainsi, on note \(i\) et \(j\) les plus petits entiers distincts tels que \(x_i \equiv x_j\ [p]\) (dans l’exemple précédent, \(i=7\) et \(j = 18\)). Comme \(x_i\) est sur le cycle, on a \(x_{i’} \equiv x_{2i’}\ [p]\) pour tout multiple \(i’\) de \(\ell\) supérieur à \(i\). Comme \(j = i+\ell\), il y a \(\ell\) entiers entre \(i\) et \(j-1\), et donc exactement un d’entre eux sera multiple de \(\ell\) et sera notre valeur de \(i’\). On doit donc tester au maximum \(j\) paires d’entiers avant de trouver une collision.

Cet algorithme s’implémente simplement :

def pollardrho(n, x1=1, f=lambda x: x**2+1):
    x = x1
    y = f(x) % n
    p = pgcd(y-x, n)
    while p == 1:
        x = f(x) % n
        y = f(f(y)) % n
        p = pgcd(y-x, n)
    if p == n:
        return None
    return p

Il est à peu près aussi rapide que l’algorithme \(p-1\) pour la valeur \(n = 15770708441\) :

>>> starttime = time.time(); pollardrho(15770708441); endtime = time.time()
135979
>>> endtime-starttime
0.0034170150756835938

Contre-mesures

L’algorithme Rho nécessite \(j\) calculs de PGCD au maximum. La valeur de \(j\) dépend non seulement de \(n\), mais aussi du choix de la fonction \(f\) et de la valeur initiale \(x_1\). En moyenne, on a \(j \approx \sqrt{p}\), et donc pour se prémunir contre cette méthode de factorisation, il suffit de prendre des facteurs de \(n\) suffisamment grands.

Leave a Reply

Your email address will not be published. Required fields are marked *