\documentclass[a4paper,12pt]{article}

\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amssymb,amsthm,amsmath,amsfonts,mathrsfs}
\newtheoremstyle{custom}%    <name>
{\topsep}%   <space above>
{\topsep}%   <space below>
{\normalfont}%  <body font>
{}%          <indent amount>
{\bfseries}% <Theorem head font>
{.}%         <punctuation after theorem head>
{\newline}%  <space after theorem head> (default .5em)
{}%          <Theorem head spec>
\theoremstyle{custom}
\usepackage{textcomp}
%\usepackage{bbm}
\usepackage{geometry}
\usepackage{mathrsfs}
\usepackage{enumitem}
\usepackage{csquotes}
%\usepackage{esvect}       % Pour des vecteurs 
\usepackage{hyperref}      %Pour des liens hypertexte !
\hypersetup{
	% backref=true,    %permet d'ajouter des liens dans...
	% pagebackref=true,%...les bibliographies
	% hyperindex=true, %ajoute des liens dans les index.
	colorlinks=true, %colorise les liens
	%     breaklinks=true, %permet le retour à la ligne dans les liens trop longs
	%     urlcolor= blue,  %couleur des hyperliens
	%     linkcolor= black, %couleur des liens internes
	%     linktoc	=all,	%defines which part of an entry in the table of contents is made into a link
	%     citecolor=black,	%color of citation links (bibliography)
	%     filecolor=black,	%color of file links
	% bookmarks=true,  %créé des signets pour Acrobat
	bookmarksopen=true,            %si les signets Acrobat sont créés,
	%les afficher complètement.
	pdftitle={M1 algèbre effective}, %informations apparaissant dans
	pdfauthor={Samuel Le Fourn},     %dans les informations du document
}
\frenchspacing



\newtheorem{thm}{Théorème}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollaire}
\newtheorem*{thmsansnom}{Théorème}
\newtheorem*{propsansnom}{Proposition}
\newtheorem{lem}[thm]{Lemme}



\theoremstyle{custom}
\newtheorem{defi}[thm]{Définition}
\newtheorem{rem}[thm]{Remarque}
\newtheorem{exe}[thm]{Exemple}
\newtheorem{exocours}[thm]{Exercice de cours}
\newtheorem{exerciseaux}[thm]{Exercice}
%\newenvironment{exo}{\begin{exerciseaux}\leavevmode\par}{\end{exo}}
\newtheorem{exo}[thm]{Exercice}

\def\R{\mathbb{R}}
\def\C{\mathbb{C}}
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\def\F{\mathbb{F}}
\def\1{\mathbbm{1}}
\def\Ncal{\mathcal{N}}

\DeclareMathOperator{\pgcd}{pgcd}
\DeclareMathOperator{\ppcm}{ppcm}

\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Inn}{Inn}
\DeclareMathOperator{\id}{id}
\newcommand{\Ker}{\operatorname{Ker}}

\setlist{noitemsep}
\setlist[1]{labelindent=\parindent} % < Usually \setlist[itemize]{leftmargin=*}
%d\setlist[itemize]{label = ($(\arabic*)$)}
\setlist[enumerate]{label = ($\alph*$)}



%%%%%%%%%%%%%%%%%%
% Alphabet Grec  %
%%%%%%%%%%%%%%%%%%
\renewcommand{\a}{\alpha}
\renewcommand{\b}{\beta}
\newcommand{\g}{\gamma}
\renewcommand{\d}{\delta}
\newcommand{\e}{\epsilon}
\newcommand{\f}{\varphi}
\renewcommand{\l}{\lambda}
\renewcommand{\k}{\kappa}
\newcommand{\m}{\mu}
\newcommand{\n}{\nu}
\renewcommand{\o}{\omega}
\renewcommand{\r}{\rho}
\newcommand{\s}{\sigma}
\renewcommand{\t}{\tau}
\newcommand{\z}{\zeta}
\newcommand{\D}{\Delta}
\newcommand{\G}{\Gamma}




%%%%%%%%%%%%%%%%%%%%
% Alphabet gothique%
%%%%%%%%%%%%%%%%%%%%
\newcommand{\ga}{{\mathfrak{a}}}
\newcommand{\gA}{{\mathfrak{A}}}
\newcommand{\gb}{{\mathfrak{b}}}
\newcommand{\gB}{{\mathfrak{B}}}
\newcommand{\gc}{{\mathfrak{c}}}
\newcommand{\gC}{{\mathfrak{C}}}
\newcommand{\gd}{{\mathfrak{d}}}
\newcommand{\gD}{{\mathfrak{D}}}
\newcommand{\gI}{{\mathfrak{I}}}
\newcommand{\gm}{{\mathfrak{m}}}
\newcommand{\gn}{{\mathfrak{n}}}
\newcommand{\go}{{\mathfrak{o}}}
\newcommand{\gO}{{\mathfrak{O}}}
\newcommand{\gp}{{\mathfrak{p}}}
\newcommand{\qg}{{\mathfrak{q}}}
\newcommand{\gP}{{\mathfrak{P}}}
\newcommand{\gQ}{{\mathfrak{Q}}}
\newcommand{\gq}{{\mathfrak{q}}}
\newcommand{\gR}{{\mathfrak{R}}}
\newcommand{\gS}{{\mathfrak{S}}}
\newcommand{\gJ}{{\mathfrak{J}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Alphabet calligraphique %
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\Acal}{{\mathcal A}}
\newcommand{\Bcal}{{\mathcal B}}
\newcommand{\Ccal}{{\mathcal C}}
\newcommand{\Dcal}{{\mathcal D}}
\newcommand{\Ecal}{{\mathcal E}}
\newcommand{\Fcal}{{\mathcal F}}
\newcommand{\Gcal}{{\mathcal G}}
\newcommand{\Hcal}{{\mathcal H}}
\newcommand{\Ical}{{\mathcal I}}
\newcommand{\Jcal}{{\mathcal J}}
\newcommand{\Kcal}{{\mathcal K}}
\newcommand{\Lcal}{{\mathcal L}}
\newcommand{\Mcal}{{\mathcal M}}
\newcommand{\Ocal}{{\mathcal O}}
\newcommand{\Pcal}{{\mathcal P}}
\newcommand{\Qcal}{{\mathcal Q}}
\newcommand{\Rcal}{{\mathcal R}}
\newcommand{\Scal}{{\mathcal S}}
\newcommand{\Tcal}{{\mathcal T}}
\newcommand{\Ucal}{{\mathcal U}}
\newcommand{\Vcal}{{\mathcal V}}
\newcommand{\Wcal}{{\mathcal W}}
\newcommand{\Xcal}{{\mathcal X}}
\newcommand{\Ycal}{{\mathcal Y}}
\newcommand{\Zcal}{{\mathcal Z}}

%%%%%%%%%%%%%%%%%%%%
% Alphabet en gras %
%%%%%%%%%%%%%%%%%%%%
\newcommand{\ab}{\mathbf{a}}

%%%%%%%%%%%%%%%%%%%%
% Ensembles usuels %
%%%%%%%%%%%%%%%%%%%%
\renewcommand{\P}{\mathbb{P}}
\newcommand{\Fp}{{\mathbb{F}_{\! p}}}
\newcommand{\A}{{\mathbb{A}}}
\newcommand{\T}{{\mathbb{T}}}

%%%%%%%%%%%%%%%%%%%%%
% Opérateurs usuels %
%%%%%%%%%%%%%%%%%%%%%
\newcommand{\Card}{\operatorname{Card}}
\newcommand{\Crit}{\operatorname{Crit}}
\renewcommand{\div}{\operatorname{div}}
\newcommand{\Div}{\operatorname{Div}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\Gal}{\operatorname{Gal}}
\newcommand{\SL}{\operatorname{SL}}
\newcommand{\Id}{\operatorname{Id}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\mult}{\operatorname{mult}}
\newcommand{\ord}{\operatorname{ord}}
\newcommand{\Proj}{\operatorname{Proj}}
\newcommand{\Spec}{\operatorname{Spec}}
\newcommand{\Borel}{\operatorname{Borel}}
\newcommand{\Stab}{\operatorname{Stab}}
\newcommand{\Cart}{\operatorname{Cart}}
\newcommand{\Cot}{\operatorname{Cot}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\cl}{\operatorname{cl}}
\newcommand{\gr}{\operatorname{gr}}
\newcommand{\init}{\operatorname{in}}
\newcommand{\PGL}{\operatorname{PGL}}
\newcommand{\PSL}{\operatorname{PSL}}
\newcommand{\Der}{\operatorname{Der}}
\newcommand{\num}{\operatorname{num}}
\renewcommand{\Re}{\operatorname{Re}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\Jac}{\operatorname{Jac}}
\newcommand{\Vect}{\operatorname{Vect}}
\newcommand{\car}{\operatorname{car}}
\newcommand{\Sp}{\operatorname{Sp}}
\newcommand{\Pic}{\operatorname{Pic}}
\newcommand{\carac}{\textrm{char}}
\newcommand{\Tr}{\operatorname{Tr}}
\renewcommand{\mod}{\, \operatorname{mod} \,}
\newcommand{\Frac}{\operatorname{Frac}}
\newcommand{\preuve}{\textcolor{blue}{$^{(P)}$}}

%%%%%%%%%%%
% Flèches %
%%%%%%%%%%%
\newcommand{\mt}{\mapsto}	
\newcommand{\lmt}{\longmapsto}
\newcommand{\ra}{\rightarrow}
\newcommand{\lra}{\longrightarrow}
\newcommand{\La}{\Leftarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\Lra}{\Leftrightarrow}
\newcommand{\Llra}{\Longleftrightarrow}

\newcommand{\dessin}{\textcolor{green}{(D)}}

%%% Commandes spécifiques à la géométrie affine %%%%
%\newcommand{Evect}{\overrightarrow{E}}
%\newcommand{Fvect}{\overrightarrow{F}}
%\newcommand{uvect}{\overrightarrow{u}}
%\newcommand{vvect}{\overrightarrow{v}}



%%%%%%%%%%%%%%%%%%
% Macros utiles %%
%%%%%%%%%%%%%%%%%%

\newcommand{\fonction}[5]{\begin{array}{c|ccl}           % Pour écrire une fonction en environnement display : le nom puis espaces de départ et d'arrrivée, puis argument et résultat
		#1: & #2 & \longrightarrow & #3 \\
		& #4 & \longmapsto & #5 \end{array}}


\newcommand{\fonctionsansnom}[4]{\begin{array}{ccl}      % La même sans le nom de la fonction à mettre
		#1 & \lra & #2 \\\
		#3 & \lmt & #4 
\end{array}}


\newtheorem{enonce}[thm]{Exercice}%[section]
\newenvironment{Ex}[0]{\begin{enonce}\rm}{\bigskip \end{enonce}}
%\newtheorem{theoreme}{Th\'eor\`eme}%[section]



\geometry{top=2cm, bottom=2cm}
\begin{document}
	\newgeometry{top=1cm,bottom=2cm,left=2cm,right=2cm}
	\noindent {\large \textsc{Université Grenoble Alpes \hfill M1 \\
			\hfill M1 Algèbre effective \hfill 2024-2025}} \\
	\hrule
	\bigskip
	
	\begin{center}
		\textbf{\Large Cryptographie, RSA}
	\end{center}
	\bigskip
	
	\section{Exercices}

% {\bf Exercice 1~: Cryptographie de Hill}
% On code les lettres de A \`a Z par les nombres de 1 \`a 26,
% l'espace par 0, \verb|,| par 27 et \verb|.| par 28. On groupe les caract\`eres par paires
% et on utilise la matrice
% $A=\left( \begin{array}{cc}5&7\\1&15\end{array}\right) \pmod{29}$.
% \begin{enumerate}
	%  \item Coder le message suivant : ``VIVE LES VACANCES''
	%  \item \`A quelle condition sur la matrice $A$ 
	% le destinataire du message cod\'e pourra-t'il le d\'echiffrer ?
	%  \item D\'ecoder : ``IKYTYEH HSAHVRDAM ''
	% % a:=[[5,7],[1,15]]
	% % b:=inv(a mod 29)
	% % M:="@VIVE@LES@VACANCES"
	% % L:=asc(M).-64
	% % m:=char(flatten(irem(seq(a*L[2j..2j+1],j,0,size(L)/2-1) mod 0,29).+64)
	% % l:=asc(m).-64
	% % char(flatten(irem(seq(b*l[2j..2j+1],j,0,size(l)/2-1) mod 0,29).+64)
	% % \item Dans cette question, la matrice $A$ n'est pas connue.
	% % Pouvez-vous d\'ecoder le message suivant sachant qu'il commence par ``les'' suivi d'un espace ?
	% % YGSCN CYSGSC
	% \end{enumerate}

%{\bf Exercice 1}
%Montrer que 65537 est premier par le crit\`ere de Lucas.

% {\bf Exercice 1~: Cryptage matriciel \`a clef secr\`ete}\\
% Pour coder des messages pouvant contenir des caract\`eres de
% diverses langues, on repr\'esente chaque caract\`ere par
% un entier sur 16 bits (codage UTF16 par exemple). On d\'ecide ensuite
% de crypter le message par blocs de 2 caract\`eres, en multipliant
% chaque vecteur $v$ des 2 entiers repr\'esentant un bloc par une matrice carr\'ee $A$ 
% de taille 2 modulo un entier $p$ qui sera suppos\'e premier dans les
% questions 1 \`a 6. La matrice $A$ est tenue
% secr\`ete, c'est la clef secr\`ete du syst\`eme de cryptage.
% \begin{enumerate}
	% \item 
	% On suppose que $p$ est un nombre premier qui permet de repr\'esenter
	% de mani\`ere unique tous les entiers sur 16 bits par leur classe dans
	% $\Z/p\Z$. Quel est le nombre minimal de bits de $p$~?
	% \item On admettra que $p=65537$ est bien premier.
	% On pose~:
	% $$ p=65537, \quad
	% A=\left(\begin{array}{cc}263&4122\\1&1799\end{array}\right)
	% $$
	% Crypter le vecteur $v$ correspondant aux deux caractÃ¨res ``intÃ©grale
	% double'' et ``intÃ©grale triple'' reprÃ©sentÃ©s respectivement par les
	% entiers 8748 et 8749,
	% %les deux caract\`eres
	% %int\'egrale double (8748) et int\'egrale triple (8749),
	% %$\left(\begin{array}{c}65\\66\end{array}\right)$,
	%  i.e. calculer $w=Av$ modulo $p$
	% \item D\'eterminer tous les vecteurs $z$ \`a coefficients
	% dans $\Z/p\Z$ tels que $Az=Av$ modulo $p$ pour $ p=65537$.\\
	% En d\'eduire tous les vecteurs $z$ \`a coefficients entiers
	% qui v\'erifient $Az=Av$ modulo $p$. \\
	% Si on impose que les coordonn\'ees de $z$ sont
	% dans l'intervalle du codage sur 16 bits, combien y-a-t-il de
	% solutions~?
	% \item
	% Que se passerait-il si on avait choisi la m\^eme matrice mais $p=6551$~?
	% \item Expliquer comment on peut d\'ecrypter, i.e. \'etant donn\'e $w$ quelconque,
	%   comment on trouve $v$ tel que $Av=w$ modulo $p$.
	% \item Quel est le nombre de matrices $A$ possibles pour $p=65537$~?
	%   Cela vous parait-il suffisant pour r\'esister \`a une attaque de la
	%   clef secr\`ete $A$ par  force brute~? Peut-on imaginer un autre
	% type d'attaque~? Comment pourrait-on renforcer la s\'ecurit\'e~?
	% \item Dans cette question, on suppose que $p=2^{16}$ et
	% n'est donc pas premier.
	% Peut-on appliquer l'algorithme du pivot de Gauss pour
	% r\'esoudre $Az=w=Av$ si on travaille modulo $p$ bien que $p$ ne
	% soit alors pas premier~? \\
	% En est-il de m\^eme pour la matrice 
	% $$ p=65536, \quad
	% A=\left(\begin{array}{cc}262&4122\\1&1799\end{array}\right)
	% $$
	% \item Quel(s) avantage(s) et inconv\'enient(s)
	% y-a-t-il \`a travailler modulo $2^{16}$
	% par rapport \`a $p=65537$~?
	% \end{enumerate}


%%%%%%%%%%%%

\begin{exo}[RSA jouet]
	On prend $p=17$ et
	$q=13$ donc $n=221$.
	\begin{enumerate}
		\item Déterminer $\varphi(n)$.
\item	V{\'e}rifier qu'on peut utiliser $e=7$ comme exposant de chiffrement.
	Calculer l'exposant de d{\'e}chiffrement $d$. 
\item	Chiffrer $M=3$. D{\'e}chiffrer $C=198$.
	\item Pour $p$ et $q$ quelconque, estimer la complexit\'e des op\'erations
	de calcul des clefs, chiffrement, d\'echiffrement.
	\end{enumerate}
\end{exo}

\begin{exo}[RSA $e=3$]

\begin{enumerate}
	\item[]
	\item Expliquer quel est l'intérêt de choisir $e=3$ comme clef publique 
	si on ne se préoccupe pas de la sécurité.
	\item Supposons que $e=3$ soit utilisé pour vérifier des signatures, prenons pour
	exemple jouet $n=587 \times 383$.
	Comment peut-on calculer efficacement
	une signature $s$ correspondant à un nombre $m=s^e \pmod n$
	sans connaitre la factorisation de $n$
	si $s$ est inférieur à  $n^{1/3}$ ? Par exemple pour $m=205379$.
	\item
	Pouquoi vaut-il mieux choisir $e=257$ ou $e=65537$ que $e=3$~?
\end{enumerate}
\end{exo}

\begin{exo}[Diffie-Hellmann, secret commun]
	{\bf Exemple jouet}~:\\ Alice et Bob choisissent de travailler dans $\Z/19\Z$
	et d'utiliser $g=2$ qui est un g\'en\'erateur de $(\Z/19\Z)^*$.

\begin{enumerate}
	\item Alice choisit $a=7$ et Bob choisit $b=13$. Donner $A$
	et $B$ puis le secret commun.
	\item Que se passe-t-il si Alice choisit $a=25$~?
	\`A quelle valeur maximale pour $a$ et $b$ Alice et Bob peuvent-ils se restreindre~?
	\item  D\'eterminer la table de toutes les puissances de 2
	dans $\mathbb{Z}/19 \mathbb{Z}$.
	\item Alice et Bob choisissent deux autres entiers $a$ et $b$ et
	s'envoient $A=4$ et $B=17$. En utilisant la table,
	d\'eterminer les valeurs de $a$ et
	$b$.  Quelle est la valeur du secret commun~?
\end{enumerate}

\noindent {\bf S\'ecurit\'e}~:\\
On a vu qu'une personne qui connaît
les entiers $A$ et $B$ (par exemple en espionnant les \'echanges entre Alice et Bob)
pouvait calculer le secret commun si on travaille dans $\mathbb{Z}/19
\mathbb{Z}$. Pour esp\'erer  s\'ecuriser le secret commun, il faut travailler
dans  $\Z/p\Z$ avec $p$ un nombre premier plus grand.
\begin{enumerate}
	\item Commen\c{c}ons par essayer avec $p=65537$ et $g=3$. 
	\begin{itemize}
		\item[$(i)$] V\'erifier que 3 est un g\'en\'erateur de $(\Z/p\Z)^*$.
		\item[$(ii)$] Si Alice choisit $a=12345$, combien doit-elle effectuer de
		multiplications pour calculer $A$ par l'algorithme de la puissance
		rapide~?
		\item[$(iii)$] \`A quelle valeur maximale pour $a$ et $b$ Alice et Bob peuvent-ils se restreindre ?
		\item[$(iv)$] Quelle est la taille de la table des puissances de 3 modulo $p$~? Comparer
		avec la question $(ii)$. La s\'ecurit\'e du secret commun
		vous semble-t-elle suffisante~?
	\end{itemize}
	\item On prend maintenant un nombre premier dont l'\'ecriture en base
	2 comporte exactement 1024 bits, et tel que $g=2$ est un
	g\'en\'erateur de $(\Z/p\Z)^*$. La s\'ecurit\'e du secret commun
	vous semble-t-elle suffisante~?
\end{enumerate}
\end{exo}
\begin{exo}[Attaque active contre Diffie-Hellman]
	
	On pourra travailler avec des valeurs explicites
	sur un exemple jouet de groupe $(\Z/19 \Z)^*$ avec comme
	générateur $g=2$.
	Alice et Bob veulent échanger un secret commun, ils choisissent
	chacun une clef secrète $a$, $b$ et envoient $g^a$ et $g^b$. Charles
	intercepte les messages et envoie à la place
	aux deux $g^e$ où $e$ est sa propre clef secrète.
	Comment Charles doit-il ensuite
	modifier les message émis par Alice qu'il intercepte
	pour les retransmettre à Bob~?
	
\end{exo}

\begin{exo}[Attaque contre RSA (module partagé)]
	Alice et Bob d\'ecident de recevoir des messages crypt\'es en
	utlisant le syst\`eme RSA. Ils publient donc chacun leur clef
	publique.
	
	On va \'etudier une attaque qu'un espion peut exploiter
	si Alice et Bob utilisent tous les deux la m\^eme valeur de $n$. On suppose
	donc que la clef publique d'Alice est $(n,e_A)$, et celle de Bob
	$(n,e_B)$. 
	On suppose que Catherine envoie une m\^eme information $m$ \`a Alice et \`a Bob,
	donc envoie le message crypt\'e $c_A=m^{e_A} \pmod n$ \`a Alice et le
	message crypt\'e $c_B=m^{e_B} \pmod n$ \`a Bob. Un espion Daniel
	intercepte les deux messages crypt\'es.
	
	Dans l'exercice, on prendra
	$n=4897$ pour pouvoir faire des calculs \`a 
	la calculatrice. 
	\begin{enumerate}
		\item Dans cette question on suppose qu'on connaît la factorisation de
		$n$~: $n=59 \times 83$. 
		Expliquer pourquoi on peut prendre $e_A=71$ et $e_B=227$.
		D\'eterminer la clef priv\'ee d'Alice.
		\item D\'eterminer une identit\'e de B\'ezout entre 71 et 227. 
		\item En d\'eduire deux entiers $u$ et $v$ tels que $m=c_A^u c_B^v
		\pmod n$
		\item Daniel intercepte $c_A=1846$ et $c_B=487$. D\'eterminer $m$
		sans utiliser la factorisation de $n$.
		\item Expliquer pourquoi Daniel ne peut pas utiliser la factorisation
		de $n$ dans une attaque r\'eelle contre RSA.
	\end{enumerate}
\end{exo}


\begin{exo}[Attaque RSA par itération]
	\begin{enumerate}
		\item[]
		\item Exemple jouet : on prend $n=77$ et une cl\'e publique $c=7$, le message
		original est  $a=2$. Retrouver le message original par it\'eration de
		la fonction de cryptage sur le message crypt\'e.
		\item En g\'en\'eral, quelles sont les valeurs de $c$ vuln\'erables \`a une
		attaque par it\'eration~?
	\end{enumerate}
\end{exo}


% {\bf Exercice 8~: Logarithme discret}
% Calculer le logarithme en base $2$ de $3$ modulo 11.

% {\bf Exercice 9~: Logarithme discret et restes chinois.}\\
% On consid{\`e}re le nombre premier 101 et on cherche, s'il existe, un entier $x\in \NN$ tel que $3^x=2~[101]$.
% \begin{enumerate}
	% \item
	% \`A l'aide de l'algorithme d'exponentiation modulaire, calculer $3^4$, $2^4$, $3^{25}$ et $2^{25}$ modulo 101.
	% \item
	% D{\'e}terminer des entiers $a$, $b$ tels que $(3^4)^a=2^4$ et $(3^{25})^b=2^{25}$ modulo 101
	% (pour d{\'e}terminer $a$, on pourra chercher les puissances successives de $3^4$ modulo 101).
	% \item
	% D\'eterminer $x$ tel que $x=a~[25]$ et $x=b~[4]$, v{\'e}rifier que
	% pour cet $x$, on a $3^x=2~[101]$.
	% \end{enumerate}

% {\bf Exercice 10~: Logarithme discret p-adique}
% Calculer le logarithme en base $2$ de $3$ modulo 197 en utilisant 2
% fois le logarithme en base 7 au lieu du logarithme en base 49.

\section{TP}
\begin{exo}[Vérification machine des calculs]
	Vérifier les résultats des exercices du TD.
\end{exo}

\begin{exo}[Générer une paire de clefs]

Générer deux grands nombres premiers $p$ et $q$ au hasard puis une paire de clefs, en utilisant par exemple les fonctions
	\verb|nextprime| et \verb|randint| de Xcas ou le test de Miller-Rabin si
	votre langage pr\'ef\'er\'e n'a pas de test de primalit\'e.
	
\end{exo}

\begin{exo}[Codage et décodage d'un message (sur PC)]
	On transforme une chaine de caractères en une liste d'entiers et réciproquement
	(avec \verb|asc| et \verb|char| en Xcas,
	ou l'application r\'ep\'et\'ee de \verb|ord| et \verb|chr|
	en Python). Pour le moment on code
	caract\`ere  par caract\`ere, sans s'inqui\'eter de la s\'ecurit\'e du codage.
	Pour coder/d\'ecoder une liste \verb|l| d'entiers, on peut utiliser
	\verb|pow(l,c,n)| en Xcas et Python.
	\begin{enumerate}
		\item 	En utilisant la paire de clefs de l'exercice précédent,
		coder un message puis décoder ce message pour vérifier.
		\item Décoder le message authentifié situé à l'URL \\
			\verb|http://www-fourier.univ-grenoble-alpes.fr/~parisse/mat249/rsa1|
	\end{enumerate}

	

	
\end{exo}

\begin{exo}[Attaque simple]
	On a vu que le codage monoalphab\'etique n'est pas une bonne
	id\'ee, une attaque possible \'etant la recherche de fr\'equences, ici
	on peut utiliser une attaque encore plus simple~:
	la personne souhaitant décoder un message codé avec une clef publique
	sans en connaitre la clef secrète calcule 
	la liste des $a^c \pmod n$ pour les 256 valeurs possibles de $a$ et compare au message.
	
	Décoder de cette manière le message situé à l'URL\\
	\verb|http://www-fourier.univ-grenoble-alpes.fr/~parisse/mat249/rsa2|
\end{exo}

\begin{exo}[Padding aléatoire]
Pour parer à l'attaque précédente, on augmente le nombre de valeurs possibles de $a$ pour que le calcul de la liste de toutes les puissances possibles de $a$ soit trop long. 

Plusieurs strat\'egies sont possibles, l'une d'elle
consiste \`a ajouter \`a $a$ un multiple al\'eatoire de 256.  
Comment la personne qui recoit un message crypt\'e retrouvera-t-elle
le message en clair~? Impl\'ementer cette m\'ethode.

\end{exo}

\begin{exo}[Groupement de lettres]
	On peut aussi
	grouper par paquets de $x$ caractères et on associe à un groupe de caractères
	l'entier correspondant en base 256. Par exemple, si on prend des groupes de $x=3$ caractères,
	"ABC" devient \verb|65*256^2+66*256+67| car le code ASCII de A, B, C est respectivement
	65, 66, 67.
	
	\begin{enumerate}
		\item 	Donner une condition reliant $n$ et $x$ pour que le décodage redonne le message original.
		\item Choisir une paire de clefs vérifiant cette condition pour $x=3$
		(calculatrices avec entiers repr\'esent\'es par des flottants) ou $x=8$ (autres).
		\item 
		\'Ecrire un programme de codage et de décodage avec groupement (on commencera par compléter
		le message original par des espaces pour qu'il soit un multiple de 8
		caractères, en Xcas et Python). L'instruction \verb|len| permet de connaitre la taille d'une chaîne de caractères,
		(En Xcas, on pourra utiliser la fonction \verb|convert(.,base,256)|d'écriture en
		base 256).
	
	\end{enumerate}



\end{exo}

\begin{exo}[Sécurité du codage]
	\begin{enumerate}
		\item[]
		\item V\'erifier sur l'exemple de l'exercice 1.1 et du 2.2 que la connaissance
		de $\varphi(n)$ et de $n$ permet de calculer $p$ et $q$ par résolution d'une
		équation de degré 2.
		\item 	 Si on connait seulement $c$ et $d$, peut-on
		retrouver $\varphi(n)$~?
		\item 	La sécurité du codage repose donc sur la difficulté de factoriser $n$. Tester sur des entiers
		de taille croissante le temps nécessaire au logiciel pour factoriser $p$ et $q$. 
		Une valeur de $n$ de taille 128 bits, 512 bits, 1024 bits parait-elle suffisante?
	\end{enumerate}


	
\end{exo}

\begin{exo}[Sécurité du codage]
	Le choix de $c$ et de $d$ est aussi important. Pour le comprendre, prenons $p=11$ et $q=13$.
	\begin{enumerate}
		\item 	Représenter pour différentes valeurs de $c$ les points $(a,a^c \pmod n)$. Plus
		le dessin obtenu est aléatoire, plus il sera difficile à  une personne mal intentionnée
		de déchiffrer un message sans connaitre la clef.
		(En Xcas, on pourra utiliser les instructions \verb|seq| pour générer une suite de terme général
		exprimée en fonction d'une variable formelle, et \verb|scatterplot(l)| qui représente
		le nuage de points donné par une liste \verb|l| de couples de
		coordonnées. En Python, on peut utiliser l'instruction \verb|plot| de \verb|matplotlib|).
		\item 
		Observer en particulier les cas où $c$ n'est pas premier avec
		$\varphi(n)$ (comment voit-on que RSA ne fonctionne pas~?) et  \'egalement le cas $c=3$.
	\end{enumerate}

\end{exo}

\begin{exo}[Attaque par les restes chinois]
	Une personne souhaite envoyer le m\^eme message $x$ \`a
	trois destinataires diff\'erents, ayant chacun leur propre
	clef publique $c=3,N_1$, $c=3,N_2$ et $c=3,N_3$ avec $c=3$
	pour les 3 destinataires.
	
	 Il envoie donc $y_1=x^3 \pmod {N_1}$,
	$y_2=x^3 \pmod{ N_2}$ et $y_3=x^3 \pmod{ N_3}$. Une personne mal
	intentionn\'ee arrive \`a intercepter $y_1, y_2$ et $y_3$. En
	appliquant les restes chinois, elle peut en d\'eduire $x$.
	
	
	Par exemple, retrouver $x$ sans chercher \`a factoriser les clefs
	pour 
	\begin{verbatim}
		46693373016 mod 180711261397, (-111575037168) mod 840724735099,
		
		(-18270191368) mod 372130013641
	\end{verbatim}
\end{exo}

\begin{exo}[Attaque RSA]
	On suppose qu'on connait un couple de cl\'e secr\`ete/publique\\
	\verb|96664445695884629095302836378328116675824715046626033|
	pour 65537 pour $n$ valant\\
	\verb|1485368763791603971165032953281737852964691152265640113|\\
	En d\'eduire la factorisation de $n$.
	
\end{exo}


\begin{exo}[Attaque RSA par fraction continue]
	Cette attaque fonctionne si la clef priv\'ee $d$ est petite et si $p$ et $q$ sont
	du m\^eme ordre de grandeur~: 
	\[ q<p< 2q.\]
	Le principe consiste \`a calculer les r\'eduites de $e/n$.
	Soit $k \in ]0,d[$ tel que
	\[ ed=1+k \varphi(n) = 1+k(n+1-p-q) = kn + 1 + k(1-p-q)\]
	On divise par $dn$~:
	\[ \frac{e}{n} = \frac{k}{d} + \frac{1+k(1-p-q)}{dn} \]
	donc~:
	
	\[
		\left|\frac{e}{n} - \frac{k}{d} \right|  =  \frac{k(p+q-1)-1}{dn}  \leq \frac{k(p+q)}{nd}.
	\]
	\begin{enumerate}
		\item 	En déduire que $	\left|\frac{e}{n} - \frac{k}{d} \right| \leq \frac{3}{\sqrt{n}}$. 
		
		Si $3/\sqrt{n} < 1/(2d^2)$, alors les r\'esultats connus sur les
		fractions continues permettent de conclure que $k/d$ est une
		r\'eduite de $e/n$. On calcule ces r\'eduites
		en utilisant les r\'esultats interm\'ediaires
		de l'algorithme d'Euclide \'etendu et on teste si
		$m^{de}=m \pmod n$.\\
		
		
		\item 
		Mettre en oeuvre cette attaque, par exemple pour 
		\begin{verbatim}
			n=24121770232611008805519974758722894470290624535341
			c=7078963133555205950174183804340026159121720607229
		\end{verbatim}
		
	\end{enumerate}

%	\begin{eqnarray*}
%	\left|\frac{e}{n} - \frac{k}{d} \right|  =  \frac{k(p+q-1)-1}{dn} & \leq & \frac{k(p+q)}{nd}\\
%		& \leq  & \frac{kq(\frac{p}{q}+1)}{nd} \\
%		& \leq & \frac{3kq}{nd} \\
%		& \leq & \frac{3k}{\sqrt{n}d} \\
%		& < & \frac{3}{\sqrt{n}}
%	\end{eqnarray*}
	
\end{exo}
\begin{exo}[Polllard=rho]
	Programmer l'algorithme de Pollard-rho pour chercher un facteur de
	taille au plus environ 10 digits d'un entier.
\end{exo}

\end{document}
