%\makeindex
\documentclass{article}
\usepackage[T1]{fontenc}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{xspace}
\usepackage{times}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}
\newcommand{\Q}{{\mathbb{Q}}}

\begin{document}


\section{Le cryptage avec la m\'ethode RSA}

Il faut d'abord une correspondance entre lettres d'un message
\`a coder et nombres.
Pour passer d'un message \`a une suite de nombres, on groupe
plusieurs caract\`eres (car sinon on pourrait d\'ecrypter le
message en utilisant des statistiques de fr\'equence des
caract\`eres en fonction de la langue), le groupement est
l'\'ecriture d'un nombre en une base donn\'ee (256 ici correspondant
au codage ASCII d'un caract\`ere), par exemple, puisque asc("BONJOUR")=[66,79,78,74,79,85,82], si on groupe par 3, 
{\tt BONJOUR } devient les nombres
(66*256+79)*256+78=4345678, (74*256+79)*256+85=4869973,  
(82*256+0)*256+0 =5373952.


\ \\
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
\ 0  &&&&&&&&&\\
\ 1~ ! &\ 2~ " &\ 3 \# &\ 4 \$ &\ 5 \% &\ 6 \& &\ 7~ ' &\ 8 ( &\ 9 ) &10 * \\
11 + &12 , &13 - &14 . &15 / &16 0 &17 1 &18 2 &19 3 &20 4 \\
21 5 &22 6 &23 7 &24 8 &25 9 &26 : &27~ ; &28 < &29 = &30 > \\
31 ? &32 @ &33 A &34 B &35 C &36 D &37 E &38 F &39 G &40 H \\
41 I &42 J &43 K &44 L &45 M &46 N &47 O &48 P &49 Q &50 R \\
51 S &52 T &53 U &54 V &55 W &56 X &57 Y &58 Z &59 [ &60 $\backslash$ \\
61 ] &62 \^ &63 \_ &64 ` &65 a &66 b &67 c &68 d &69 e &70 f \\
71 g &72 h &73 i &74 j &75 k &76 l &77 m &78 n &79 o &80 p \\
81 q &82 r &83 s &84 t &85 u &86 v &87 w &88 x &89 y &90 z \\
91 \{ &92 | &93 \} &94 \~ &95 � &96 � &97 � &98 � &99 � &100 � \\\hline
\end{tabular}\\

Tartampion choisit deux grand nombres premiers $p$ et $q$ et pose $n=pq$, puis 
il choisit $m$ un nombre premier avec $(p-1)(q-1)$ (par exemple il prend pour 
$m$  un nombre premier plus grand que $(p-1)/2$ et que $(q-1)/2$).\\
Il calcule l'entier $u$ pour que $um=1 \bmod (p-1)(q-1)$ (d'apr\`es 
l'identit\'e de B\'ezout il existe des entiers $u$ et $v$ tel que 
$um=1+v(p-1)(q-1)$). Puis il 
met dans l'annuaire les nombres  $u$ et $n$ (quand $n$ est grand $p$ et $q$ 
sont difficiles \`a obtenir \`a partir de $n$), le couple $(u,n)$ est la cl\'e 
publique alors que $(m,n)$ est la cl\'e secr\'ete qui va servir \`a d\'ecoder 
le message : bien s\^ur $p$ et $q$ restent secrets  car sinon n'importe qui
peut calculer $m$ en fonction de $u$ avec l'identit\'e de B\'ezout.

La fonction de codage $f$ est la suivante :\\
\`a un entier  $a$ (de pr\'ef\'erence premier avec $pq$, c'est le cas si
$a<p$ et $a<q$), $f$ fait correspondre $a^u \bmod n$.

Par exemple, {\tt BONJOUR } cod\'e par les nombres
4345678, 4869973, 5373952. qui seront transform\'es par
$f$ en 156330358492191937, 126697584810299952, 50295601528998788 car
powmod(4345678,u,n)=15633035849219193 etc...\\

La fonction de d\'ecodage $g$ est la suivante :\\
\`a un entier  $b$, $g$ on fait correspondre $b^m \bmod n$.
Pour d\'ecoder l'exemple, on a :\\
powmod(15633035849219193,m,n)=4345678 etc...

Pour montrer que $g(f(a))=a$, on utilise le petit th\'eor\`eme de Fermat :\\
si $p$ et $q$ sont premiers, si  $n=pq$ et si $a$ est premier avec $n$ alors :\\
$a^{(p-1)(q-1)}=1 \bmod n$\\
On peut appliquer ce th\'eor\`eme ici car :
$p$ et $q$ sont premiers, $n=pq$ et $a$ est premier avec $n$ puisque 
$a<p$ et $a<q$ donc $a^{v(p-1)(q-1)}=1^v=1 \bmod n$
on a donc bien :\\
$g(f(a))=g(a^u) \bmod n=a^{um} \bmod n=a*a^{v(p-1)(q-1)}\bmod n=a $ \\
Un exemple :\\
$p=123456791$ et $q=1234567891$ \\:
$n=p*q=152415790094497781$ \\
$\varphi=(p-1)(q-1)=152415788736473100$\\ 
$m=12345701$ ($m$ est un nombre premier et $m$ ne divise pas $\varphi$)\\
On cherche $u$ en tapant ${\tt inv(m \% \varphi)}$ on trouve :\\
{\tt (-36645934363466299) \% 152415788736473100 } et on a :\\
$u=-36645934363466299+\varphi=115769854373006801$\\
Pour coder, on utilise la cl\'e publique $u$ et $n$  et pour d\'ecoder, on 
utilise la cl\'e secr\'ete $m$ et $n$.

Exemple avec {\tt xcas}
\begin{verbatim}
examples/arit/rsa.cxx ->chaine2n("BON")=4345678 etc.
u:=115769854373006801; n:=152415790094497781; l:=codrsa("BONJOUR",u,n);
m:=12345701; n:=152415790094497781; decodrsa(l,m,n);
\end{verbatim}



\end{document}