\documentclass[12pt]{article}
\usepackage{kbexo}
\course{MHT633 -- Arithmétique et Cryptologie}
\num{7}

\begin{document}
\exotitle[Cryptographie asymétrique (3)]

\exo[Crible quadratique]

\noindent On désire factoriser un entier impair $N$, en utilisant une
variante de l'algorithme de Dixon:
\begin{enumerate}
\item On choisit une base de facteurs
$\mathcal{B}=\set{-1, p_1,\dots,p_k}$ où les $p_i$ sont premiers.

\item Pour chaque $j\in\NM$, on pose
  $t=\pm j$, $x_t=\floor{\sqrt{N}}+t$
et on calcule $y_t=x_t^2-N$ jusqu'à ce qu'on trouve $k+2$ tels nombres
se décomposant entièrement sur $\mathcal{B}$. Pour chaque tel $t$ on a
$y_t=\pm\prod_{i=1}^k p_i^{a_{i,t}}$,
et l'on forme le $(k+1)$-uplet $(v_{0,t},v_{1,t},\ldots,v_{k,t})$ où
$v_{0,t}=0$ si $y_t>0$, $v_{0,t}=1$ si $y_t<0$ et $v_{i,t}=a_{i,t}\bmod 2$ si
$i\geq 1$.

\item On cherche un sous-ensemble $S$ des valeurs de $t$ obtenues
précédemment tel que pour tout $i=0,1,\dots,k$, on ait
$\sum_{t\in S}v_{i,t} \equiv 0 \bmod 2$. Alors si $x=\prod_{t\in S}x_t$ et
$y^2=\prod_{t\in S} y_t$ on a $x^2\equiv y^2\bmod N$;
si de plus $x\not\equiv\pm y\bmod N$, alors
$(x\pm y,N)$ fournit un facteur non trivial de $N$.
\end{enumerate}

\Q Pourquoi peut-on exclure de $\mathcal{B}$ les $p$ tels que $N$ ne soit
pas résidu quadratique modulo $p$?

\Q Soit $N=30167$ et
${\mathcal B}=\set{-1,2,7,11,17,29,31,37,41,43,53,67}$. On calcule
$$
\begin{array}{|r|c|c|} \hline
   t & x_t & y_t \\\hline
   0 & 173 & -2 \cdot 7 \cdot 17 \\\hline
   -1 & 172 &  -11 \cdot 53      \\\hline
    -5 & 168 & -29 \cdot 67      \\\hline
    5 & 178 & 37 \cdot 41        \\\hline
    -6 & 167 & -2 \cdot 17 \cdot 67 \\\hline
    7  & 180 & 7 \cdot 11 \cdot 29  \\\hline
    11 & 184 & 7 \cdot 17 \cdot 31  \\\hline
\end{array}
\qquad
\begin{array}{|r|c|c|} \hline
   t & x_t & y_t \\\hline
    14 & 187 & 2 \cdot 7^4          \\\hline
    -15 & 158 & -11 \cdot 43        \\\hline
    -17 & 156 & -7^3 \cdot 17       \\\hline
    18 & 191 & 2 \cdot 7 \cdot 11 \cdot 41  \\\hline
    -23 & 150 & -11 \cdot 17 \cdot 41       \\\hline
    28  & 201 & 2 \cdot 7 \cdot 17 \cdot 43 \\\hline
\end{array}
$$
Factoriser $N$.

\exo[Méthode $p-1$ de Pollard]

\noindent
Si $B>1$, un entier $N$ est dit \emph{$B$-friable} si pour tout premier
$q$ et tout $s$ tel que $q^s \mid N$, alors $q^s\leq B$.
On considère l'algorithme suivant:
\begin{algorithmic}[1]
\REQUIRE $N$ un entier impair, $B>2$ une borne de friabilité.
\STATE $a\leftarrow 2$.
\FOR{$j$ from 2 to $B$}
\STATE $a\leftarrow a^j \bmod N$
\ENDFOR
\STATE $d \leftarrow (a-1, N)$
\IF{ $1<d<N$}
  \STATE on renvoie $d$.
\ENDIF
\STATE On renvoie «Échec».
\end{algorithmic}

\Q Que vaut $a$ à la fin de la boucle \textbf{for} ?

\Q Supposons que $p$ premier divise $N$ et que $p-1$ soit $B$-friable.
Montrer que $p$ divise $d$ et que l'algorithme retourne un facteur non
trivial de $N$ sauf si $a=1$.

%\Q Montrer que l'on peut prendre $B$ plus petit que la borne de friabilité
%précédemment définie.

\Q Appliquer avec $N=13927189$ et $B=14$.
\Q Écrire un autre algorithme qui s'appuiera sur le calcul d'un autre $a$ ne faisant appel qu'aux $q$ premiers $\leq B$ et aux exposants $m_q=\floor{\log N/\log q}$.

\exo[Le chiffrement de ElGamal]

\noindent
On rappelle le principe du chiffrement de ElGamal :
\begin{center}
\fbox{
\begin{tabular}{ll}
Clé publique & $(p,\alpha,\beta)$ où $p$ premier, $\alpha$ d'ordre $q$ dans
$\FM_p^*$,\\
& $\beta\in\langle \alpha\rangle$, $\beta\neq 1$.\\
&\\
Clé privée & $a\in [1\dots q-1]$ tel que $\beta= \alpha^a\mod p$.\\
&\\
Chiffrement de $m<p$ & $E(m)=(\alpha^k,m\beta^k)$ où $1\leq k < q$ est 
aléatoire.\\
&\\
Déchiffrement de $c=(r,t)$ &  $D(c)=tr^{-a} \mod p$.
\end{tabular}
}
\end{center}

\Q La clé publique de Bob est $p=17$, $\alpha=3$, $\beta=10$. Aidez Alice à
  chiffrer le message $m=5$ et Bob à déchiffrer $(7,6)$.

\Q Montrez que $D(E(m))=m$.

\Q Montrez qu'un attaquant peut déchiffrer tous les messages dès qu'il sait
calculer le log en base $\alpha$ de $\beta$.

\Q Montrez qu'un attaquant peut déchiffrer $c=(r,t)$ dès qu'il sait calculer
  le log en base $\alpha$ de $r$.

\Q Pourquoi faut-il que l'ordre de $\alpha$ modulo $p$ soit un
  «grand» nombre $q$ ?
\Q Quel avantage procure l'utilisation du nombre aléatoire $k$ ?
\Q Alice chiffre deux messages $m_1$ et $m_2$
  avec le même $k$. Montrez que, si Oscar connaît $m_1$, alors
  il connaît aussi $m_2$.

\exo[Une attaque sur RSA : module commun]

\noindent On rappelle le principe du chiffrement RSA :
\begin{center}
\fbox{
\begin{tabular}{ll}
Clé publique & $(N,e)$ où $N=pq$ et $(e,\varphi(N))=1$\\
&\\
Clé privée & $d$ tel que $ed\equiv 1\mod (p-1)(q-1)$\\
&\\
Chiffrement de $m<N$ & $E(m)=m^e \mod N$ \\
&\\
Déchiffrement de $c$ &  $D(c)=c^d \mod N$\\
\end{tabular}
}
\end{center}
\noindent
Bob et Catherine ont choisi le même module RSA $N$. Leurs exposants publics
$e_B$ et $e_C$ sont distincts.

\Q Expliquez pourquoi Bob peut déchiffrer les messages reçus
  par Catherine et réciproquement.

\Q On suppose que $(e_B,e_C)=1$ et qu'Alice envoie un même message chiffré à
  Bob et à Catherine. Expliquez comment l'attaquant Oscar peut obtenir $m$.

\exo[Une attaque sur RSA : petit exposant public commun]

\noindent
On suppose que $k$ personnes $B_1,\dots, B_k$ ont  pour exposant public RSA
$e=3$ avec des modules respectifs $N_i$, $1\leq i\leq k$ deux à deux premiers
entre eux. Si Alice envoie un même message $m$ à tous les $B_i$, montrez
qu'un attaquant peut déterminer $m^3$ modulo $ P:=\prod_{i=1}^k n_i$; en
déduire qu'il peut calculer $m$ si $P > m^3$.
\end{document}
