\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage{fullpage}
\usepackage{amsfonts}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage[T1]{fontenc}

%\usepackage[dvips]{graphicx}
\def\application#1#2#3#4{%                                                      
\left\{\begin{array}{lcl}#1 & \longrightarrow & #2\\ #3 & \longmapsto &         
#4\end{array}\right.}

\newtheorem{theoreme}{Théorème}

\def\mod{~\mathrm{mod}~}
\def\Z{\mathbb{Z}}
\def\F{\mathbb{F}}

\title{TD 6 de Cryptologie}
\date{Lundi 21 novembre 2005}

\begin{document}
\maketitle
\thispagestyle{empty}

\section*{RSA et \emph{cycling attacks}}

Dans la suite $n = pq$ est le produit de deux nombres premiers
impairs, $e$ l'exposant public et $d$ l'exposant secret.

\begin{enumerate}

\item Montrer que pour un groupe commutatif fini $G$ de cardinal $N$
l'application $\varphi_k:\application{G}{G}{x}{x^k}$ est une
bijection si et seulement si $\mathrm{pgcd}(N, k) = 1$.
\item Pour un message clair $m$ et son chiffré $c$, montrer que si on
connait $k$ tel que $c^{e^k} = c$
alors on sait retrouver $m$.

\item Application : $n = 77$, $c = 52$, $e = 7$. On sait que $c^{e^4}
= c$. En déduire $m$ (pour accélérer les calculs on pourra utiliser
les restes chinois). Vérifier le résultat en cassant la clef.

\item Montrer que s'il existe $P$ tel que $c^P =
1$ alors on peut retrouver $m$. 
\end{enumerate}

On peut montrer que la connaissance d'un tel $P$ permet de factoriser
$n$ (si on sait factoriser $P$). Nous allons montrer plus simplement
comment factoriser $n$ lorsqu'on connait un multiple noté $u$ de
$\varphi(n)=(p-1)(q-1)$.

\begin{enumerate}
\setcounter{enumi}{4}
\item Dans $\Z/n\Z$, combien y-a-t-il de nombres qui sont soit des carrés
modulo $p$, soit modulo $q$, mais pas les deux ?

\item Montrer que la connaissance d'une racine carrée non triviale
(\emph{i.e.} différente de $1$ ou $-1$) de l'unité dans $\Z/n\Z$
permet de factoriser $n$.

\item Justifier que pour tout élément inversible $a$ de $\Z/n\Z$, $a^u
= 1$.

\item On note $u = 2^tv$ avec $v$ impair, et on définit $j = \min
\left\{ i ~| ~ \forall a \in \left(\Z/n\Z\right)^*, a^{2^iv} =
1\right\}$. Donner une borne inférieure de $\mathrm{Card}\left\{ a \in
\left(\Z/n\Z\right)^* ~ | ~ a^{2^{j-1}v} \neq \pm 1 \right\}$.

\item En déduire une méthode probabiliste de factorisation à partir de
la connaissance d'un multiple de $(p-1)(q-1)$.

\end{enumerate}

\end{document}