\documentclass[12pt]{article}
\usepackage{kbexo}
\course{MHT633 -- Arithmétique et Cryptologie}
\num{6}
\begin{document}
\exotitle[Cryptographie asymétrique (2)]

\exo[L'algorithme $\rho$ de Pollard pour la factorisation]
\noindent Soit $n$ un nombre entier dont on veut calculer un facteur non
trivial. Soit $p$ le plus petit facteur premier (inconnu) de $n$. L'idée est de
construire une suite «aléatoire» $x_1,x_2,\dots, x_i,\dots$ d'éléments de
$\ZM/n\ZM$, de sorte qu'une collision $x_i=x_j \mod p$  pour $i<j$ permette de
trouver un facteur de $n$ donné par $(x_i-x_j, n)$.

On admettra le résultat suivant, connu sous le nom de \emph{paradoxe des
anniversaires}: en tirant au hasard des éléments d'un ensemble de cardinal $N$,
on obtient une collision avec probabilité supérieure à $1/2$ au bout d'environ
$\sqrt{N}$ tirages.

\Q Estimez le nombre de termes de la suite et le nombre de pgcd à calculer
avant de trouver un facteur de $n$.

\Q On choisit de définir la suite $x_i$ par la donnée de $x_1$ et la formule de
récurrence $x_{i+1} = P(x_{i})$, où $P\in \ZM[X]$.

\qq Montrez que $x_i=x_j \mod p \Longrightarrow x_{i+1}=x_{j+1}\mod p$.
\qq En déduire que,
si $x_i=x_j \mod p$ avec $i<j$ alors $x_{u}=x_{2u} \mod p$ pour un indice $u$
tel que $u<j$. 
\qq Comment calculer $(x_{i+1}, x_{2(i+1)})$ à partir de $(x_i,x_{2i})$ ?
\qq On \emph{suppose} que la suite $(x_i)$ obtenue a le même comportement 
qu'une suite de tirages indépendants dans $\ZM/N\ZM$, et donc qu'on peut
appliquer le paradoxe des anniversaires. En déduire un algorithme qui nécessite
environ $\sqrt{p}$ calculs de pgcd de nombres entiers naturels $\leq n$ pour
factoriser $n$.

\Q Factorisez $n=7171$ avec $x_1=1$ et $P(x)=x^2+1$.

\exo[Le cryptosystème de Rabin]
\Q Soit $p$ un nombre premier impair. Soit 
\begin{align*}
\phi:(\ZM/p\ZM)^*&\to (\ZM/p\ZM)^*\\
  x&\mapsto x^2
\end{align*}
\qq Montrez que $\ker\phi=\set{\pm 1}$.
\qq En déduire que $\im \phi$ est un sous-groupe de $(\ZM/p\ZM)^*$ d'ordre
$(p-1)/2$, et que, si $y\in \im \phi$ alors l'équation $x^2 = y$ a exactement
deux solutions.

\qq En déduire que $y$ est un carré de $(\ZM/p\ZM)^*$ si et seulement si
$y^{\frac{p-1}{2}}=1$.

\qq On suppose de plus que $p\equiv 3\mod 4$. Montrez que, si $y$ est un carré
de $(\ZM/p\ZM)^*$, alors 
$$y=(\pm y^{\frac{p+1}{4}})^2.$$

\Q Soit $n=pq$ avec $p$, $q$ deux nombres premiers impairs distincts.
Montrez que, si $y\in (\ZM/n\ZM)^*$, l'équation $x^2=y$ a soit aucune
soit quatre solutions (on pourra utiliser le théorème Chinois).
Caractérisez ce dernier cas.

\Q Le cryptosystème de Rabin utilise un entier $n=pq$ avec 
$p$, $q$ deux nombres premiers distincts tels que $p,q\equiv 3\mod 4$.
La clé publique est $n$, la clé privée est $(n,p,q)$.
La fonction de chiffrement est $e(x)=x^2\mod n$.
\qq Expliquez pourquoi la fonction de chiffrement n'est pas injective.
\qq Expliquez comment Bob, qui connait la clé privée, peut calculer à partir
d'un chiffré, un ensemble de quatre éléments contenant le clair.
\qq Soit $n=77$. Le chiffré est $23$. Calculez les quatre possibilités pour le
 clair.

\exo Trouvez un diviseur non trivial de $N=1829$ avec l'algorithme de Dixon et
la base de facteurs $\mathcal{B}=\set{-1,2,3,5,7,11,13}$. On pourra utiliser
les entiers $42,43,61,74,85,86$.

\exo Soit $n$ un entier de la forme $n=pq$ avec $p,q$ premiers distincts.
\Q Montrez que $p$ et $q$ sont racines de  l'équation 
$$ X^2-(n-\phi(n)+1)X +n=0. $$
\Q En déduire qu'il n'est pas plus facile de calculer $\phi(n)$ que de
factoriser $n$.
\Q Soit $n=84773093$. Sachant que $\phi(n)=84754668$, factorisez $n$.
\end{document}
