Attaques sur RSA, part 1 : L’algo \(p-1\) de Pollard

A.k.a. “Non, dans la vraie vie on n’utilise pas RSA comme tu l’as vu en Terminale, jeune padawan.” Même si on ne connaît pas d’attaque sur RSA qui marche à tous les coups, on sait l’attaquer dans certains cas, et il faut donc faire attention, quand on choisit ses paramètres, à ne pas tomber dans l’un d’eux.

RSA

D’abord, petits rappels sur RSA (Rivest-Shamir-Adleman, 1977), à toutes fins utiles : on choisit deux entiers premiers \(p\) et \(q\) distincts, et on calcule le produit \(n = pq\). \(p\) et \(q\) sont secrets, \(n\) est public. On calcule également le produit \(\varphi(n) = (p-1)(q-1)\). Le résultat fondamental pour RSA est un théorème dû à Euler et qui généralise le petit théorème de Fermat en affirmant que pour tout entier \(k\) premier avec \(n\), on a
\[ k^{\varphi(n)} \equiv 1\ [n]. \]

On choisit un entier \(e\) premier avec \(\varphi(n)\), qui sera l’exposant de chiffrement (public), et on calcule l’exposant de déchiffrement (secret) \(d\) tel que \(de \equiv 1\ [\varphi(n)]\). Les messages sont représentés par des entiers de \([0,n-1]\) premiers avec \(n\). La fonction de chiffrement est
\[ e(m) = m^e \mod n \]
et la fonction de déchiffrement est
\[ d(m) = m^d \mod n. \]
Cela fonctionne car
\[ \begin{align*}
d(e(m)) &= d(m^e) \mod n \\
&= (m^e)^d \mod n \\
&= m^{ed} \mod n \\
&= m^{1+k\varphi(n)} \mod n & \text{(Car \(ed \equiv 1\ [\varphi(n)]\))} \\
&= m\cdot m^{k\varphi(n)} \mod n \\
&= m(m^{\varphi(n)})^k \mod n \\
&= m\cdot 1^k \mod n & \text{(Car \(m^{\varphi(n)} \equiv 1\ [n]\))} \\
&= m \mod n \\
&= m & \text{(Car \(m \in [0,n-1]\))}
\end{align*} \]

Le seul moyen connu actuellement pour déchiffrer le message est de calculer \(d\). Sachant que \(e\) et \(n = pq\) sont publics, une méthode possible est de retrouver \(p\) et \(q\) à partir de \(n\) (ainsi on peut calculer \(\varphi(n) = (p-1)(q-1)\), et retrouver \(d\)). On dit qu’on cherche à factoriser \(n\). Un algorithme simple de factorisation est l’algorithme \(p-1\) de Pollard (Pollard, 1974).

L’algorithme \(p-1\) de Pollard

Cet algorithme nécessite de se donner a priori une borne supérieure sur les facteurs de \(p-1\) de la forme \(\pi^k\) avec \(\pi\) premier, et donc il est utilisable dans les cas où \(p-1\) n’a que des petits facteurs puissances de nombres premiers.

Le phénomène qui implique le résultat est que si \(\pi^k \le B\) pour tout facteur \(\pi^k\) de \(p-1\) avec \(\pi\) premier, on a nécessairement que \(p-1\) divise \(B!\) car tous les facteurs \(\pi^k\) de \(p-1\) seront facteurs de \(B!\). On commence par calculer
\[ a = 2^{B!} \mod n \]
et puisque \(p\) divise \(n\) on a
\[ a \equiv 2^{B!}\ [p]. \]

Le petit théorème de Fermat assure que
\[ 2^{p-1} \equiv 1\ [p] \]
et puisque \(p-1\) divise \(B!\) il vient
\[ a \equiv 2^{B!} \equiv 2^{k(p-1)} \equiv (2^{p-1})^k \equiv 1^k \equiv 1\ [p] \]
et \(p\) divise \(a-1\). Comme \(p\) divise également \(n\), il divise le PGCD de \(a-1\) et \(n\), ce qui signifie que le PGCD de \(a-1\) et \(n\) est un diviseur non-trivial de \(n\).

En pratique

Cet algorithme s’implémente simplement, par exemple en Python (on suppose disponible une fonction pgcd()) :

def pollard(n, B):
    a = 2
    for i in range(2, B+1):
        a = (a**i) % n
    d = pgcd(a-1, n)
    if d > 1 and d < n:
        return d
    return None

Par exemple avec \(n = 15770708441\) et \(B = 200\) on obtient la factorisation de \(n\) :

>>> pollard(15770708441, 200)
135979
>>> 15770708441 / 135979
115979.0

En effet, la factorisation de \(p-1 = 135978\) en facteurs premiers est
\[ 135978 = 2 \cdot 3 \cdot 131 \cdot 173 \]
et on voit qu’il sont bien tous inférieurs à \(200\).

Pour voir que cet algorithme est bien plus rapide que l’algorithme “naïf” :

firas@aoba ~ % cat pollard.py 
import sys
import time

def pgcd(a, b):
    if b == 0:
        return a
    return pgcd(b, a%b)

def naivefactor(n):
    i = 2
    while i*i <= n:
        if n % i == 0:
            return i
        i += 1

def pollard(n, B):
    a = 2
    for i in range(2, B+1):
        a = (a**i) % n
    d = pgcd(a-1, n)
    if d > 1 and d < n:
        return d
    return None

n = 15770708441
B = 200
print("Factoring " + str(n))

starttime = time.time()
p = pollard(n, B)
endtime = time.time()
print("Pollard p-1 algorithm returned %s in %s seconds" %
        (p, endtime-starttime))

starttime = time.time()
p = naivefactor(n)
endtime = time.time()
print("Naive factoring returned %s in %s seconds" %
        (p, endtime-starttime))

firas@aoba ~ % python3 pollard.py
Factoring 15770708441
Pollard p-1 algorithm returned 135979 in 0.0032417774200439453 seconds
Naive factoring returned 115979 in 0.0407099723815918 seconds

Il est plus rapide d’un facteur 10, mais sur une petite valeur de \(n\). Sur une valeur plus réaliste, la différence est évidemment encore plus marquée.

Contre-mesures

Le moyen le plus simple pour se prémunir contre cette attaque est d’utiliser un nombre premier \(p\) tel que \(p_1 = (p-1)/2\) soit également premier (et faire bien entendu de même pour \(q\)). Ainsi on a \(p-1 = 2p_1\), et l’algorithme \(p-1\) nécessite alors une borne au moins égale à \(p_1\), ce qui le ralentit considérablement si \(p_1\) est assez grand.

Leave a Reply

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