Introduction

L’attaque Franklin-Reiter sur le chiffrement RSA requiert d’avoir deux messages chiffrés avec une relation linéaire connu entre les deux messages.

Contextualisation

Exemple :

• $m_1 = 100000000000$
• $m_2 = 100000000999$

Ici , si la relation entre les deux messages est linéaire puisque $m_1 + 999 == m_2$. Il est alors possible de retrouver le message à partir de :

• $c_1 = m_1^e \pmod n$
• $c_2 = m_2^e \pmod n$

A l’origine, cet attaque était faisable pour $e=3$ puis elle a était généralisé pour n’importe quel $e$ .
(Plus e est grand, plus l’attaque est longue)

Première approche :

• $e = 3$

  • $\begin{cases} m_2 = \alpha*m_1+\beta \newline c_1 = m_1^3 \pmod n \newline c_2 = m_2^3 \pmod n \end{cases}$

  $\implies \dfrac{\beta(c_2+2\alpha^3c_1+\beta^3)}{\alpha(c_2-\alpha^3c_1+2\beta^3)} = \dfrac{3\alpha^3\beta{m_1}^3+3\alpha^2\beta^2{m_1^2}+3\alpha\beta^3m_1}{3\alpha^3\beta{m_1}^2+3\alpha^2\beta^2m1+3\alpha\beta^3} = m_1 \pmod n$

• $e = 5$

  • $\begin{cases} m_2 = \alpha*m_1+\beta~(avec~\alpha=\beta=1) \newline c_1 = m_1^5 \pmod n \newline c_2 = m_2^5 \pmod n \end{cases}$

  $\implies\begin{cases} P(m)=c_2^3-3c_1c_2^2+3c_1^2c_2-c_1^3+37c_2^2+176c_1c_2+37c_1^2+73c_1^2+73c_2-73c_1+14 \newline mP(m)=2c_2^3-c_1c_2^2-4c_1^2c_2+3c_1^3+14c_2^2-88c_1c_2-51c_2-9c_2+64c_1-7 \newline m = \dfrac{mP(m)}{P(m)} \end{cases}$

Cette méthode est longue mais fonctionnelle, elle permet pour tous $e$ de déterminer un polynôme $P$ pour retrouver les $m_i$

Seconde approche :

Théorème de Franklin-Reiter :

Soit (n,e) une clé RSA publique , et $m_1 \neq m_2$ tel que :

• $\mathbf{m_1 = f(m_2) \pmod n}$

Si $f$ est une fonction affine $f:x \rightarrow a*x+b$
Alors avec $(n,e,c_1,c_2,f)$ il est possible de retrouver $m_1~et~m_2$

Démonstration :

On a :

$\begin{cases} c_1 = m_1^e \pmod n \newline c_2 = m_2^e \pmod n \end{cases}$

$\implies\begin{cases} z^e - c_1 \equiv 0 \pmod n \newline (\alpha*z+\beta)^e - c_2 \equiv 0 \pmod n \end{cases}$

$\implies \begin{cases} m_2~est~racine~de~: g_1(x) = f(x)^e - c_1\newline m_2~est~racine~de~: g_2(x) = x^e - c_2 \end{cases}$

et
$x-m_2$ divise les deux polynômes.
Ainsi , on peut utiliser le PGCD entre $g_1$ et $g_2$ pour retrouver $m_2$ dans l’anneau $Z/N$

$\implies z-m_1 = gcd(z^e - c_1,(\alpha*z+\beta)^e - c_2) \in Z/N[m_1]$

Le temps d’exécution de cette méthode dépend de la puissance de calcul du PGCD , elle reste efficace jusqu’a des $e$ de 32 bits environ . Elle est donc possible contre des $e=65537$ par exemple.

>>> e = 65537
>>> e.bit_length()
17

Implémentation en Python

• $m2 = a*m1 + b$

Avec Sympy

def franklin_reiter(c1,c2,e,n,a,b):
	from sympy import poly,gcdex
	from sympy.abc import x

	g1 = poly((a*x + b)**e - c1)
	g2 = poly(x**e - c2)
	for res in gcdex(g1,g2):
		z = -res.coeffs()[-1]
		if z.is_integer and \
			len(res.coeffs()) == 2 :
			return z

Avec SageMath

def franklin_reiter(c1,c2,e,n,a,b):
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a.monic()
    P.<X> = PolynomialRing(Zmod(N))
    g1 = (a*X + b)^e - C1
    g2 = X^e - C2
    result = -gcd(g1, g2).coefficients()[0]
    return result

Reference : Low-Exponent RSA with Related Message