Carrés, racines et factorisation

Sécurité de RSA

On définit \(n=pq\), avec

\[p = \frac{15^{73}-1}{14}, \; q = \frac{11^{73}-1}{10}\]

On suppose que \(n=pq\) est un module RSA.

1. Calculer les racines carrées de \(1\) dans \(\Z/n\Z\). Combien y en a-t-il ?
2. Montrer que si \(a\neq\pm1\) vérifie \(a^2=1\bmod n\), alors \(n\) n’est pas premier, et \(\pgcd(a-1,n)\) est un facteur non trivial de \(n\).
3. 410041 est un nombre de Carmichael. Le factoriser en déterminant une telle valeur de \(a\).
4. Supposons que l’on connaisse les exposants de chiffrement et de déchiffrement \(ed\) du système RSA. On pose \(ed-1=2^rm\). Montrer qu’au plus la moitié des \(a\in(\Z/n\Z)^\ast\) vérifie \(a^m=1\) ou \(a^{2^jm}=-1\) pour \(0\leq j<m\).
5. En déduire un algorithme pour factoriser \(n\).
6. Faire le test avec votre voisin : construire et échanger des clefs RSA, et les casser quand on connaît \(e\) et \(d\).

Carrés et racines

7. On note \(S\) le sous-groupe des carrés de \((\Z/n\Z)^\ast\). Quel est son indice ?
8. Montrer que si \(a\in S\), déterminer les racines carrées de \(a\) est équivalent à connaître la factorisation de \(n=pq\).
9. On pose \(p = \frac{6^{127}-1}{5}\). Déterminer un carré (non trivial) \(a\bmod p\).
10. Vérifier que \(a^{\frac{p+1}4}\) est une racine carrée de \(a\).
11. Quelles sont les racines carrées de \(6\) modulo \(n=pq\), où

\[p = \frac{6^{127}-1}{5}, \; q = \frac{6^{271}-1}{5}\]

Racines carrées

On considère un cas plus compliqué

\[p = \frac{15^{73}-1}{14}, \; q = \frac{11^{73}-1}{10}\]

La méthode précédente permet-elle de calculer les racines carrées de \(6\) modulo \(n=pq\) ?

Algorithme de Cipolla

Cet algorithme consiste à passer par l’extension \(\F_{p^2}\), dans laquelle tout élément de \(\F_p\) possède une racine carrée. Pour tout \(a\in\F_p\), en notant \(x\in\F_{p^2}\) une racine de \(x^2-a\), on a la disjonction

\[\begin{split}x^p = x &\Leftrightarrow a \in \F_p^2 \Leftrightarrow x\in\F_p \\ x^p = -x &\Leftrightarrow a \in \F_p\setminus \F_p^2 \Leftrightarrow \F_{p^2} = \F_p[x]\end{split}\]

de sorte que pour tout \(u\) dans \(\F_p\) et \(v\in\F_{p^2}\) une racine d’un non résidu quadratique, on a

\[(u+v)^{p+1} = (u+v)(u^p+v^p) = (u+v) (u-v) = u^2 - v^2\]

L’astuce de Cipolla consiste à choisir \(u\) tel que \(u^2-a\) n’est pas un carré modulo \(p\), et définir \(v\) comme une racine carrée de \(u^2-a\). Alors le calcul ci-dessus montre que l’élément

\[x = (u+v)^{\frac{p+1}2}\]

est une racine carrée de \(a\), dans \(\F_{p^2}\). Il appartient en particulier à \(\F_p\) si et seulement si \(a\) est un carré dans \(\F_p\).

Le calcul de \(x\) se fait alors de la manière suivante :

• déterminer \(u\) tel que \(u^2-a\) n’est pas un carré modulo \(p\)
• construire \(\F_{p^2}\) comme \(\F_p[v]/(v^2-(u^2-a))\)
• calculer \(x=(u+v)^{\frac{p+1}2}\) par exponentiation rapide
• le résultat \(x\) est dans \(\F_p\) et est une racine carrée de \(a\).

12. Programmer cet algorithme et calculer les racines de \(6\).