\documentclass[10pt,a4paper]{article}
\usepackage{t1enc}
\usepackage{amsmath,amssymb,amsthm,amscd,graphicx}
\pagestyle{empty}
\usepackage[frenchb]{babel}
\usepackage[utf8]{inputenc}

\newcommand{\N}{\mathbb{N}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ov}{\overline}
\def\ds{\displaystyle}
\newcommand{\mathframe}[1]{\fbox{$#1$}}
\def\ima{\mathrm{Im}}

\topmargin-2.8cm
\oddsidemargin-2.4mm
\textwidth17.5cm
\textheight26.7cm
\parskip=3pt
\parindent=0pt

\pagestyle{empty}

\def\soluce#1{} % n'affiche pas les indications de solutions

\begin{document}



\noindent
M1 alg\`ebre effective  \hfill Cryptographie, RSA, log discret \hfill UGA

\section{TD}
% {\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}


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


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

{\bf Exercice 3: RSA $e=3$}
\begin{enumerate}
\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}

{\bf Exercice 4~: Diffie-Hellman, 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}

{\bf S\'ecurit\'e}~:\\
On a vu qu'une personne qui connait
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{enumerate}
\item V\'erifier que 3 est un g\'en\'erateur de $\Z/p\Z^*$.
\item Si Alice choisit $a=12345$, combien doit-elle effectuer de
  multiplications pour calculer $A$ par l'algorithme de la puissance
  rapide~?
\item \`A quelle valeur maximale pour $a$ et $b$ Alice et Bob peuvent-ils se restreindre ?
\item Quelle est la taille de la table des puissances de 3 modulo $p$~? Comparez
  avec la question (b). La s\'ecurit\'e du secret commun
  vous semble-t-elle suffisante~?
\end{enumerate}
\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}

{\bf Exercice 5~: attaque active contre Diffie-Hellman}
On pourra travailler avec des valeurs explicites
sur un exemple jouet de groupe $\Z/19^*$ 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~?


{\bf Exercice 6~: attaque contre RSA (module partag\'e)}\\
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 connait 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}

{\bf Exercice 7: attaque RSA par it\'eration}\\
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.
En g\'en\'eral, quelles sont les valeurs de $c$ vuln\'erables \`a une
attaque par it\'eration~?

{\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}
{\bf Exercice 0} V\'erifiez les r\'esultats de TD.

{\bf Exercice 1: Générer une paire de clefs}\\
Génèrez deux grands nombres premiers $p$ et $q$ au hasard, 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

{\bf Exercice 2: Codage et décodage d'un message (sur PC)}\\
On transforme une chaine de caractère 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.
En utilisant la paire de clefs de l'exercice 1,
codez un message puis décodez ce message pour vérifier.
Décodez le message authentifié situé à l'URL\\
\verb|http://www-fourier.univ-grenoble-alpes.fr/~parisse/mat249/rsa1|.

\vspace{0.5cm}


{\bf Exercice 3: 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écodez de cette manière le message situé à l'URL\\
\verb|http://www-fourier.univ-grenoble-alpes.fr/~parisse/mat249/rsa2|

\vspace{0.5cm}

{\bf Exercice 4: Padding al\'eatoire}\\
Pour parer à cette attaque, on va augmenter le nombre de valeurs possibles de $a$ pour que
le calcul de la liste de toutes les puissances des $a$ possibles 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.

{\bf Exercice 5: 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.
Donner une condition reliant $n$ et $x$ pour que le décodage redonne le message original.
Choisissez une paire de clefs vérifiant cette condition pour $x=3$
(calculatrices avec entiers repr\'esent\'es par des flottants) ou $x=8$ (autres).
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 chaine de caractères,
en Xcas, on pourra utiliser la fonction \verb|convert(.,base,256)|d'écriture en
base 256).

\vspace{0.5cm}

{\bf Exercice 6: Sécurité du codage 1} \\
V\'erifiez sur l'exemple de l'exercice 1 que la connaissance
de $\varphi(n)$ et de $n$ permet de calculer $p$ et $q$ par résolution d'une
équation de degré 2. Si on connait seulement $c$ et $s$, peut-on
retrouver $\varphi(n)$~?
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?

\vspace{0.5cm}

{\bf Exercice 7: Sécurité du codage 2}\\
Le choix de $c$ et de $s$ est aussi important. Pour le comprendre, prenons $p=11$ et $q=13$.
Représentez 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é 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|.
Observez 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$.

\vspace{0.5cm}

{\bf Exercice 8: 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 % 180711261397,
(-111575037168) % 840724735099,
(-18270191368) % 372130013641
\end{verbatim}

{\bf Exercice 9: 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$.

{\bf Exercice 10:  Attaque RSA fraction continue.}
Fonctionne si la clef priv\'ee $d$ est petite et si $p$ et $q$ sont
du m\^eme ordre de grandeur~: 
\[ p>q, \quad p< 2q\]
Le principe consiste \`a calculer les r\'eduites de $e/n$.
Soit $k \in ]0,d[$ tel que
\[ ed=1+k \phi(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~:
\begin{eqnarray*}
 |\frac{e}{n} - \frac{k}{d} | & = & \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*}
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$.\\
Mettre en oeuvre cette attaque, par exemple pour 
\verb|n=24121770232611008805519974758722894470290624535341|\\
\verb|c=7078963133555205950174183804340026159121720607229|

{\bf Exercice 11, log discret}
Programmer l'algorithme Baby-step giant-step en stockant dans une
liste tri\'ee les pas de b\'eb\'e pour comparaison par dichotomie.

{\bf Exercice 12, Pollard-rho}
Programmer l'algorithme de Pollard-rho pour chercher un facteur de
taille au plus environ 10 digits d'un entier.

{\bf Exercice 13, Pollard-rho pour le logarithme discret}
Programmer l'algorithme de Pollard-rho pour chercher le logarithme
discret modulo un nombre premier $p$ pour des nombres d'ordre $n$
(avec $n$ divisant $p-1$).

\end{document}
