\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage{latexsym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath,amsfonts,amssymb,a4,epsfig}
\usepackage{times}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}
\begin{document}
\noindent Mat309 \hfill 2020/2021
\begin{center}
{\LARGE TP RSA}
\end{center}

{\bf Rappel du principe de codage RSA~:}
\begin{itemize}
\item Chaque personne souhaitant coder ou signer un message dispose d'une clef privée,
un entier $s$ connu de lui seul, et d'une clef publique, une paire d'entiers $(c,n)$.
\item $n$ est le produit de 2 nombres premiers $p$ et $q$, et $s$ et $c$ sont inverses
modulo $\varphi(n)$, où $\varphi(n)=(p-1)(q-1)$ 
(le nombre d'entiers de l'intervalle $[1,n[$
premiers avec $n$), on a alors (cf. devoir 1)
\begin{equation} \label{eq:rsa}
(a^c \pmod n)^s \pmod n = (a^s \pmod n)^c \pmod n = a \pmod n
\end{equation}
\item Pour coder un message à destination d'une personne dont la clef publique est $(c,n)$, 
on commence par le transformer en une suite d'entiers, On peut par exemple remplacer
chaque caractère par un entier compris entre 0 et 255, son code ASCII.
\item Puis
on envoie la liste des nombres $b=a^c \pmod n$. En principe, 
seule la personne destinataire connait $s$
et peut donc retrouver $a$ à partir de $b$ en calculant $b^s \pmod n$.
\item On peut aussi authentifier qu'on est l'auteur d'un message en le codant avec sa
clef privée, tout le monde pouvant le décoder avec la clef publique.
\end{itemize}

\vspace{0.5cm}

{\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\\
\verb|xcas.univ-grenoble-alpes.fr/forum/viewtopic.php?f=49&t=2582|\\
ou un test de Fermat ou un test
na\"if si vous travaillez avec un langage o\`u les entiers sont
repr\'esent\'es par des flottants. 
Calculez $n=p \times q$ puis $\varphi(n)=(p-1)(q-1)$
puis choisissez une clef secrète $s$ inversible modulo $\varphi(n)$ et calculez son inverse $c$.
Vérifiez sur quelques entiers la propriété (\ref{eq:rsa}), on pourra utiliser la fonction 
\verb|pow(a,c,n)| pour calculer $a^c \pmod n$ en Xcas et en Python, 
ou programmer la puissance modulaire
rapide (si elle n'est pas impl\'ement\'ee)

Programme pour l'identit\'e de B\'ezout (en Xcas on peut aussi
utiliser \verb|iegcd(a,b)|)~:
\begin{verbatim}
def bezout(a,b):
    l1=[1,0,a]; l2=[0,1,b]
    while l2[2]!=0:
        q=l1[2]//l2[2]
        l1,l2=l2,[l1[0]-q*l2[0],l1[1]-q*l2[1],l1[2]-q*l2[2]]
    return l1
\end{verbatim}

\vspace{0.5cm}

{\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.ujf-grenoble.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.ujf-grenoble.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}


\end{document}
