--- /dev/null
+\documentclass[a4paper,french,11pt]{report}
+%\usepackage{hyperlatex}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage{lmodern}
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{stmaryrd}
+\usepackage{amssymb}
+\usepackage{optional}
+\usepackage{framed}
+\usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
+\usepackage[dvips]{graphics}
+\usepackage{epsfig}
+\usepackage{epsfig,psfrag}
+\usepackage{subfigure}
+\usepackage{color}
+\usepackage{calc}
+\usepackage{listings}
+\usepackage{url}
+\usepackage{makeidx}
+\usepackage{longtable}
+\usepackage{tabls}
+\usepackage{textcomp}
+%\usepackage{slashbox}
+\usepackage{times}
+\usepackage{gastex}
+\usepackage{multirow}
+\usepackage{algorithm2e}
+\usepackage{pst-plot}
+%\input{format.sty}
+\usepackage[frenchb]{babel}
+\usepackage[a4paper]{geometry}
+
+\input{symboles.sty}
+
+\geometry{hmargin=1.5cm, vmargin=1.5cm }
+
+
+
+\theoremstyle{plain}
+\theoremheaderfont{\normalfont\sc}
+\theorembodyfont{\slshape}
+\theoremsymbol{$\dagger$}
+\theoremprework{\medskip}
+%\theorempostwork{}
+\theoremseparator{. }
+\newtheorem{Proof}{Preuve}%[chapter]
+
+
+\theoremstyle{plain}
+%\theoremsymbol{\ensuremath{\clubsuit}}
+\theoremseparator{.}
+%\theoremprework{\hrulefill}
+%\theorempostwork{\hrulefill\newline}
+\newtheorem{Exo}{Exercice}[chapter]
+
+
+
+\theoremstyle{plain}
+%\theoremsymbol{\ensuremath{\clubsuit}}
+\theoremseparator{.}
+%\theoremprework{\hrulefill}
+%\theorempostwork{\hrulefill\newline}
+\newtheorem{TP}{Travaux pratiques}[chapter]
+
+
+
+
+\theoremstyle{plain}
+\theoremheaderfont{\normalfont\bfseries\sc}
+\theorembodyfont{\normalfont}
+%\theoremsymbol{\ensuremath{}}
+\theoremprework{\bigskip}
+\theoremseparator{.}
+\newtheorem{Def}{Définition}[chapter]
+
+
+\theoremstyle{plain}
+\theoremheaderfont{\normalfont\bfseries\sc}
+\theorembodyfont{\normalfont}
+%\theoremsymbol{\ensuremath{}}
+\theoremprework{\bigskip}
+\theoremseparator{.}
+\newtheorem{Prop}{Proposition}[chapter]
+
+
+\lstset{% general command to set parameter(s)
+basicstyle=\small, % print whole listing small
+keywordstyle=\color{black}\bfseries\underbar,
+ % underlined bold black keywords
+identifierstyle=, % nothing happens
+commentstyle=\color{white}, % white comments
+stringstyle=\ttfamily, % typewriter type for strings
+extendedchars = true,
+showstringspaces=false} % no special string spaces
+
+
+
+\usepackage{hyperref}
+\pdfcompresslevel=9
+\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= blue, %couleur des liens internes
+ %bookmarks=true, %créé des signets pour Acrobat
+ bookmarksopen=true, %si les signets Acrobat sont créés,
+ %les afficher complÚtement.
+ pdftitle={}, %informations apparaissant dans
+ pdfauthor={}, %dans les informations du document
+ pdfsubject={} %sous Acrobat.
+}
+
+
+
+
+\makeindex
+
+%\renewcommand{\thesubsection}{~~~~\arabic{subsection}}
+%\renewcommand{\theparagraph}{~~~~~~~~\arabic{paragraph}}
+
+
+\begin{document}
+\title{Modélisation mathématique}
+\author{Jean-Fran\c{c}ois {\sc Couchot} \\
+ \url{couchot [arobase]univ-fcomte
+ [point] fr}}
+
+
+
+%\lstset{language=C}
+\maketitle
+\tableofcontents
+
+\setcounter{secnumdepth}{3}
+
+
+
+
+\chapter{Cryptographie par RSA}
+\input{rsa}
+
+
+\bibliographystyle{alpha}
+\bibliography{biblio}
+
+
+
+\end{document}
--- /dev/null
+
+% Objectifs pédagogiques :
+% arithmétique classique (pgcd, diviseur)
+% algorithme RSA
+% calculs modulo
+% Théorème de Bezout, petit Fermat
+% Nombres premiers : tests simples, avancés, disctribution
+% Multiplications rapides:
+% Puissance rapides
+% Factorisation
+
+% Cryptographie RSA : comprendre et approfondir
+% on doit discuter de la taille des nombres premier pour pouvoir coder tout mot.
+% on doit pouvoir déduire de l'unicité de la clé d pour une cle e
+
+\section{Introduction}
+
+La \emph{cryptographie}, où l'art d'écrire avec une clé,
+est apparue en même temps que l'écriture.
+Dès qu'une information doit être transmise de manière sure,
+le message doit être protégé de toute interception: il est crypté par l'émetteur
+et décrypté par le récepteur.
+Dans le cas où l'on utilise une clé de cryptage, on a le schéma présenté
+à la figure~\ref{Fig:schemageneral}.
+\begin{figure}[ht]
+\begin{center}
+\includegraphics[scale=0.5]{schemacrypto.eps}
+\end{center}
+\caption{Schéma général d'une méthode de cryptage/décryptage}\label{Fig:schemageneral}
+\end{figure}
+Dans cette figure, rien ne précise cependant que la clé de
+cryptage est la même que celle de décryptage.
+Lorsqu'une méthode se fondent sur une clé unique pour chiffrer et déchiffrer
+un message on emploie le terme de cryptographie \emph{symétrique}.
+Se pose immédiatement le problème de confidentialité de la clé et la mise
+en {\oe}uvre de celle-ci
+surtout lorsque le nombre de destinataires est grand:
+il faut une clé pour chacun d'entre eux.
+
+Pour résoudre ce problème d'échange de clés, la cryptographie
+\emph{asymétrique} a été mise au point dans les années 1970.
+Elle se base sur le principe d'une clé publique pour le chiffrement et
+d'une clé privée pour le déchiffrement.
+Chaque destinataire (receveur)
+diffuse sa clé publique à quiconque désire chiffrer
+un message. Le message crypté ne pourra être déchiffré qu'avec la clé privée,
+qui elle reste confidentielle.
+
+RSA est un algorithme de cette famille. Son étude d'un point de vue mathématique
+ est l'objectif de ce TD.
+Il s'inspire largement de~\cite{RSA09}
+
+% Annonce plan
+
+
+
+\section{L'algorithme RSA}
+
+\subsection{Les étapes détaillées de l'algorithme}
+
+On rappelle qu'un système cryptographique à clé publique est
+initialisé par le receveur, c.-à-d. celui qui veut recevoir des messages de
+manière sure.
+
+\paragraph{Première étape: choix des deux nombres $p$ et $q$.}
+Le receveur choisit deux grands nombres premiers
+$p$ et $q$ et calcule $n = pq$. Puis il calcule $\varphi(n)$,
+où $\varphi : \N^* \rightarrow \N^* $ est la \emph{fonction d'Euler}
+définie par $\varphi(n)$ est le nombre d'entiers dans $\{1, 2, \dots , n -1 \}$
+qui sont premiers avec $n$.
+\paragraph{Deuxième étape: choix de la clé publique.}
+Le receveur choisit $e \in
+\{1, \dots , n-1\}$ premier avec $\varphi(n)$.
+La clé publique est la paire $(e,n)$. L'expéditeur
+va s'en servir pour crypter son message à la quatrième étape ci-dessous.
+\paragraph{Troisième étape: construction de la clé privée.}
+Le receveur calcule l'entier $d \in \{1,\dots, n-1\}$
+tel que le reste de la division de $ed$ par $\varphi(n)$ est 1.
+Ceci se note aussi $ed \equiv 1 [\varphi(n)]$ qui se lie $ed$ est congru
+à 1 modulo $\varphi(n)$.
+La paire $(d,n)$ est la clé privée de décryptage. Elle
+est secrète et permet au receveur de décrypter tous les messages reçus
+et cryptés avec $(e,n)$.
+\paragraph{Quatrième étape: cryptage du message.}
+L’expéditeur peut crypter tout message écrit sous la forme
+d'un nombre $m$ appartenant à $\{1, \dots , n-1\}$ et qui est
+premier avec $n$.
+Le message codé est le reste $a$ de la division de $m^e$ par $n$.
+On a donc $m^e \equiv a [n]$, où $a \in \{1, \dots , n - 1\}$.
+\paragraph{Cinquième étape: décryptage du message.}
+Le receveur dispose de $a$ et de sa clé privée $(d,n)$.
+Pour décrypter $a$, il calcule le reste dans la division par $n$
+de $a^d$ (c.-à-d. $a^d [n]$).
+Si aucune erreur de calcul n'a été effectuée, c'est le message initial $m$.
+
+
+\subsection{Sur un exemple très petit}
+Le receveur choisit $p=7$, $q=13$.
+\begin{enumerate}
+\item Construire l'ensemble des entiers qui sont premiers avec $n=pq$
+ et en déduire que $\varphi(91)=72$.
+\item Montrer que $(29,91)$ est un candidat acceptable de clé publique.
+\item Trouver la clé privée associée.
+\item Montrer que l'expéditeur a la possibilité de crypter le message $m=59$.
+\item Construire le message crypté $a$ à l'aide de la clé publique.
+\item Décrypter
+ le message $a$ à l'aide de la clé privée. Il doit s'agir de $m$.
+\end{enumerate}
+
+
+\subsection{Les points clés}
+L'algorithme RSA repose sur plusieurs points clés rencontrés successivement:
+\begin{itemize}
+\item la génération de deux grands nombres premiers $p$ et $q$ ;
+\item la multiplication de grands nombres : $pq$, $ed$,
+\item l'arithmétique modulaire;
+\item l'algorithme d'Euclide de génération de PGCD et son corollaire de Bézout;
+\item la factorisation, qui tant qu'elle n'est pas réalisable sur des grands nombres, garantit la sécurité du cryptage des données.
+\end{itemize}
+
+\section{Rappels d'arithmétique}
+
+Soit deux entiers $a$ et $b$ dans $\Z$.
+On dit que $a$ divise $b$ (que l'on note $a | b$)
+s'il existe un entier $q \in \Z$ tel que $b = aq$.
+
+Le plus grand diviseur commun (PGCD) de
+$a$ et $b$, noté $a\land b$ est l'entier naturel qui vérifie
+\begin{itemize}
+\item $a \land b | a$ et $a \land b | b$;
+\item Si $d | a$ et $d | b$, alors $d | a\land b$.
+\end{itemize}
+
+\subsection{Algorithme d'Euclide de calcul de PGCD}
+
+Par définition, le PGCD de $a$ non nul avec
+0 est $a$ (définition raisonnable, car 0
+est divisible par tout entier non nul, donc par $a$, qui l'est aussi par $a$)
+et enfin le PGCD de 0 et de 0 n'est pas
+défini.
+
+On se limite ici au cas de deux entiers $a$ et $b$ strictement positifs. Supposons par exemple $a>b$
+
+\begin{enumerate}
+\item La division euclidienne de $a$ par $b$ peut s'écrire $a=bq+r$ avec $0\infeg r<b$.
+
+\item Montrons que \og $d$ est un diviseur commun à $a$ et $b$ \fg{}
+ est équivalent à \og $d$ est un diviseur commun à $b$ et $r$ \fg{}.
+\begin{itemize}
+\item Soit $d$ un diviseur commun à $a$ et $b$, qui peuvent alors s'écrire $a=da'$ et $b=db'$. L'égalité $a=bq+r$ devient $da'=db'q+r$ ou encore $r=d(a'-b'q)$, donc $d$ est aussi un diviseur commun à $b$ et $r$.
+
+\item Réciproquement, soit $d$ un diviseur commun à $b$ et $r$, qui peuvent alors s'écrire $b=db'$ et $r=dr'$ et l'égalité $a=bq+r$ devient $a=d(b'q+r')$.
+Donc $d$ est un diviseur commun à $a$ et $b$.
+\end{itemize}
+
+Ainsi, les ensembles des diviseurs communs à $a$ et $b$
+d'une part et à $b$ et $r$ d'autre part sont identiques.
+En particulier $a\et b=b\et r$.
+
+\item Si $r=0$ on a $a\et b= b\et 0$ qui est égal à $b$.
+
+\item Sinon, $r$ est différent de $0$ et on peut donc effectuer la
+ division euclidienne de $b$ par $r$, qui donne un reste $r_{1}$,
+ tel que $0 \le r_{1}<r$ et $b\et r=r\et r_{1}$.
+
+\item Cet algorithme est itéré jusqu'à l'obtention d'un reste nul, ce qui se produit obligatoirement puisqu'il s'agit d'entiers et que la suite des restes ainsi construite est strictement décroissante.
+ Le PGCD est alors l'avant-dernier reste (le dernier non nul).
+\end{enumerate}
+
+\begin{Exo}
+Déterminer $154 \land 35$ par l'algorithme d'Euclide.
+\end{Exo}
+
+
+\begin{Exo}
+Donner le code d'un programme qui prend en entrée deux entiers naturels $a$
+et $b$ tels que $a>b \ge 0$ et qui retourne leur PGCD
+\end{Exo}
+
+\subsection{Les incontournables Bézout et Gau{\ss}}
+
+\begin{Prop}[Identite de Bézout]
+On considère deux nombres entiers strictement positifs $a$ et $b$.
+Il existe un couple d'entiers $x$ et $y$ tels que $ax+by=d$,
+où $d$ est le PGCD de $a$ et de $b$.
+\end{Prop}
+
+\begin{Proof}
+Dans la preuve de la proposition précédente, on avait successivement
+
+\begin{eqnarray}
+a &=& b \times q_1 +r_1 \label{eq:def:r1} \\
+b &=& r_1 \times q_2 +r_2 \\
+r_1 &=& r_2 \times q_3 +r_3 \\
+& \vdots & \nonumber\\
+r_{n-4} & = & r_{n-3} \times q_{n-2} + r_{n-2} \label{eq:def:rnm4} \\
+r_{n-3} & = & r_{n-2} \times q_{n-1} + r_{n-1} \label{eq:def:rnm3} \\
+r_{n-2} & = & r_{n-1} \times q_{n} + r_{n} \label{eq:def:rnm2}\\
+r_{n-1} & = & r_{n} \times q_{n+1} + 0
+\end{eqnarray}
+
+
+On sait que $a\land b$ est $r_n$ le dernier reste non nul.
+On remonte les équations une à une en démarrant de (\ref{eq:def:rnm2}).
+\begin{eqnarray}
+r_{n} & = & r_{n-2} - r_{n-1} \times q_{n} \nonumber \\
+ & = & r_{n-2} - (r_{n-3} - r_{n-2} \times q_{n-1}) \times q_{n} (\textrm{on remplace $r_{n-1}$ par sa def dans (\ref{eq:def:rnm3})}) \nonumber\\
+ & = & r_{n-2}. (1 + q_{n-1}. q_{n}) - r_{n-3}. q_{n} (\textrm{factorisation})\nonumber \\
+ & = & (r_{n-4} - r_{n-3} \times q_{n-2}). (1 + q_{n-1}. q_{n}) - r_{n-3}. q_{n}(\textrm{on remplace $r_{n-2}$ par sa def dans (\ref{eq:def:rnm4})}) \nonumber \\
+& \vdots & \nonumber \\
+& = & \ldots (\textrm{on remplace $r_{1}$ par sa def dans (\ref{eq:def:r1})}) \nonumber\\
+& = ax + by \nonumber
+\end{eqnarray}
+
+\end{Proof}
+
+
+
+\begin{Def}[Nombres premiers entre eux]
+Les deux entiers relatifs $a$ et $b$ sont premiers entre eux s
+leur plus grand commun diviseur est égal à 1.
+\end{Def}
+
+
+
+\begin{Prop}[Théorème de Bézout]
+Deux entiers strictement positifs
+$a$ et $b$ sont premiers entre eux, si et seulement s'il
+existe un couple $(x,y)$ d'entiers relatifs vérifiant $ax + by = 1$.
+\end{Prop}
+\begin{Proof}
+\begin{itemize}
+\item[\textbf{Seulement si.}] Supposons $a$ et $b$ premiers entre eux.
+D'après l'identité de Bézout,
+il existe donc un couple d'entiers $x$ et $y$ tels que $ax+by=1$,
+car 1 est le PGCD de $a$ et de $b$.
+\item[\textbf{Si.}]
+ Supposons qu'il existe un couple $(x,y)$
+ d'entiers relatifs vérifiant $ax + by = 1$ et $d = a \land b$.
+ Le $d$ divise $ax$ et $d$ divise $by$. Donc $d$ divise
+ $ax + by$ et donc $d$ est 1.
+\end{itemize}
+\end{Proof}
+
+\begin{Prop}[Théorème de Gau{\ss}]
+Soient $a$, $b$ et $c$ trois entiers naturels.
+Si $a$ divise le produit $bc$
+et s'il est premier avec $b$, alors il divise $c$.
+\end{Prop}
+
+\begin{Exo}
+Faire la preuve de ce théorème
+\end{Exo}
+
+\begin{Prop}[Fonction d'Euler]
+Si $p$ et $q$ sont deux nombres premiers distincts alors l'égalité
+suivante permet de trouver le valeur de la fonction d'Euler en un seul
+produit:
+\begin{equation}
+\varphi(pq)=(p-1)(q-1) \label{FEuler}
+\end{equation}
+\end{Prop}
+\begin{Exo}[Preuve de l'expression d'Euler]
+On doit compter le cardinal des nombres de $\{1, 2, . . . , pq -1\}$ qui sont
+premiers avec $pq$.
+\begin{enumerate}
+\item Construire l'ensemble $P$ des entiers naturels multiples de $p$ inférieurs à $pq -1$. Combien en a-t-on?
+\item Construire l'ensemble $Q$ des entiers naturels multiples de $q$ inférieurs à $pq -1$. Combien en a-t-on?
+\item Supposons qu'un élément $k$ appartienne à la fois à $P$ et à $Q$.
+ Montrer que cela implique qu'il existe deux entiers naturels
+ $m_1$ et $m_2$ tels que $m_1.p = m_2.q$.
+\item En utilisant le théorème de Gau{\ss}, montrer que cela est absurde.
+\item En déduire l'équation (\ref{FEuler}).
+\end{enumerate}
+\end{Exo}
+
+
+
+
+%Refaire cet exo avec 27x +8y = 1
+\begin{Exo}
+L'objectif est de résoudre l'équation $(E)$ d'inconnues $x$ et $y$
+$405x -120y =15$.
+\begin{enumerate}
+\item Trouver le PGCD de 405 et 120 à l'aide de l'algorithme d'Euclide.
+\item En déduire une solution particulière de cette équation.
+\item En utilisant la solution particulière, montrer que $(E)$ est
+ équivalente à $27(x-3) = 8(y-10)$.
+\item Utiliser le théorème de Gauss pour montrer que
+ l'ensemble solution de $(E)$ est $\{(8k+3;27k+10)| k \in \Z\}$.
+\end{enumerate}
+\end{Exo}
+
+
+
+
+\begin{Exo}[Sujet du bac S Liban 2005]
+On rappelle le résultat suivant appelé petit théorème de Fermat.
+
+\emph{Si $p$ est un nombre premier et $a$ un entier non divisible par $p$,
+ alors $a^{p-1}-1$ est un multiple de $p$.}
+\begin{enumerate}
+\item On considère l’équation $(E)$ : $109x-226y=1$ où $x$ et $y$
+ sont des entiers relatifs.
+\begin{enumerate}
+\item Déterminer $109\land 226$.
+ Que peut-on en conclure pour l'équation $(E)$?
+\item Montrer que l'ensemble des solutions de $(E)$
+ est l'ensemble des couples de la forme
+ $(141+226k ;68+109k)$, où $k$ appartient à $\Z$.
+ En déduire qu'il existe un unique entier naturel non nul $d$
+ inférieur ou égal à 226 et un unique entier naturel non nul $e$ tels que
+ $109d =1+226 e$ (on précisera les valeurs des entiers $d$ et $e$).
+\end{enumerate}
+\item Démontrer que 227 est un nombre premier.
+\item On note $A=\{0,1,2,\dots,226\}$. On considère les deux fonctions
+ $f$ et $g$ de $A$ dans $A$ définies de la manière suivante:
+\begin{itemize}
+\item A tout entier $a\in A$, $f$ associe le reste de
+ la division euclidienne de $a^{109}$ par 227.
+\item A tout entier $a\in A$, $g$ associe le reste de la
+ division euclidienne de $a^{141}$ par 227.
+\end{itemize}
+\begin{enumerate}
+\item Vérifier que $g(f(0))=0$ .
+\item Montrer que, quel que soit l'entier non nul $a$ de $A$ , $a^{226}-1$ est multiple de 227.
+\item En déduire que, quel que soit l'entier non nul $a$ de $A$,
+$g(f(a))=a$ . Que peut-on dire de $f(g(a))=a$?
+\end{enumerate}
+\end{enumerate}
+\end{Exo}
+\section{Arithmétique modulaire}
+% cf TD maths discrète;
+% Corollaire 7.6 du chap RSA
+% unicité de la clef de décodage
+
+
+\subsection{Puissance de grands nombres}
+
+\section{Génération de grands nombres premiers}
+
+\section{Factorisation}
+
+
+\section{Conclusion}
+cf SMATH paragraphe applications p 223.
\ No newline at end of file
--- /dev/null
+
+% Objectifs pédagogiques :
+% arithmétique classique (pgcd, diviseur)
+% algorithme RSA
+% calculs modulo
+% Théorème de Bezout, petit Fermat
+% Nombres premiers : tests simples, avancés, disctribution
+% Multiplications rapides:
+% Puissance rapides
+% Factorisation
+
+% Cryptographie RSA : comprendre et approfondir
+
+
+\section{Introduction}
+
+La \emph{cryptographie}, où l'art d'écrire avec une clé,
+est apparue en même temps que l'écriture.
+Dès qu'une information doit être transmise de manière sure,
+le message doit être protégé de toute interception: il est crypté par l'éméteur
+et décrypté parle récepteur.
+Dans le cas où l'on utilise une clef de cryptage, on a le schéma présenté
+à la figure~\ref{Fig:schemageneral}.
+\begin{figure}[ht]
+\includegraphics[scale=0.3]{schemacrypto.eps}
+\caption{Schéma général d'une méthode de cryptage/décryptage}\label{Fig:schemageneral}
+\end{figure}
+Dans cette figure, rien ne précise cependant que la clef de
+cryptage est la même que celle de décryptage.
+Lorsqu'une méthode se fondent sur une clé unique pour chiffrer et déchiffrer
+un message on emploie le terme de cryptographie \emph{symétrique}.
+Se pose immédiatement le problème de confidentialité de la clef et la mise
+en {\oe}uvre de celle-ci
+surtout lorsque le nombre de destinataires est grand:
+il faut une cle pour chacun d'entre eux.
+
+Pour résoudre ce problème d'échange de clés, la cryptographie
+\emph{asymétrique} a été mise au point dans les années 1970.
+Elle se base sur le principe d'une clé publique pour le chiffrement et
+d'une clef privée pour le déchiffrement.
+Chaque destinataire (receveur)
+diffuse sa clé publique à quiconque désire chiffrer
+un message. Le message crypté ne pourra être déchiffré qu'avec la clé privée,
+qui elle reste confidentielle.
+
+RSA est un algorithme de cette famille. Son étude d'un point de vue mathématique
+ est l'objectif de ce TD.
+Il s'inspire largement de~\cite{RSA09}
+
+% Annonce plan
+
+
+
+\section{L'algorithme RSA}
+
+\subsection{Les étapes détaillées de l'algorithme}
+
+On rappelle qu'un système cryptographique à clé publique est
+initialisé par le receveur, c.-à-d. celui qui veut recevoir des messages de
+manière sure.
+
+\paragraph{Première étape: choix des deux nombres $p$ et $q$.}
+Le receveur choisit deux grands nombres premiers
+$p$ et $q$ et calcule $n = pq$. Puis il calcule $\varphi(n)$,
+où $\varphi : \Nat^* \rightarrow \Nat^* $ est la \emph{fonction d'Euler}
+définie par $\varph(n)$ est le nombre d'entiers dans $\{1, 2, \dots , n -1 \}$
+qui sont premiers avec $n$.
+\paragraph{Deuxième étape: choix de la clef publique.}
+Le receveur choisit $e \in
+\{1, \dots , n-1\}$ premier avec $\varphi(n)$.
+La clef publique est la paire $(e,n)$. L'expéditeur
+va s'en servir pour encoder son message.
+\paragraph{Troisième étape: construction de la clef privée.}
+Le receveur calcule l'entier $d \in \{1,\dots, n-1\}$
+tel que le reste de la division de $ed$ par $\varphi(n)$ est 1.
+Ceci se note aussi $ed \equiv 1 [\varphi(n)]$ qui se lie $ed$ est congru
+à 1 modulo $\varphi(n)$.
+La paire $(d,n)$ est la clef privée de décryptage. Elle
+est secrète et permet au receveur de décrypter tous les messages recus
+et cryptés avec $(e,n)$.
+\paragraph{Quatrième étape: cryptage du message.}
+L’expéditeur peut crypter tout message écrit sous la forme
+d'un nombre $m$ appartenant à $\{1, \dots , n-1\}$ et qui est
+premier avec $n$.
+Le message codé est le reste $a$ de la division de $me$ par $n$.
+On a donc $me \equiv a [n]$, où $a \in \{1, \dots , n - 1\}$.
+\paragraph{Cinquième étape: décryptage du message.}
+Le receveur dispose de $a$ et de sa clé privée $(d,n)$.
+Pour décrypter $a$, il calcule le reste dans la division par $n$
+de $ad$ (c.-à-d. $ad [n]$). C'est précisément le message initial $m$.
+
+
+\subsection{Sur un exemple très petit}
+Le receveur choisit $p=7$, $q=13$.
+\begin{enumerate}
+\item Construire l'ensemble des entiers qui sont premiers avec $n=pq$
+ et en déduire que $\varphi(91)=72$.
+\item Montrer que $(29,91)$ est un candidat acceptable de clef publique.
+\item Trouver la clef privée associée.
+\item Montrer que l'expéditeur a la possibilité de crypter le message $m=59$.
+\item Construire le message codé $a$ à l'aide de la clé publique.
+\item Décoder le message $a$ à l'aide de la clé privée. Il doit s'agir de $m$.
+\end{enumerate}
+
+
+\subsection{Les points clés}
+L'algorithme RSA repose sur plusieurs points clés rencontrés successivement:
+\begin{itemize}
+\item la génération de deux grands nombres premiers $p$ et $q$ ;
+\item la multiplication de grands nombres : $pq$, $ed$,
+\item l'arithmétique modulaire;
+\item l'algorithme d'Euclide de génération de PGCD et son corollaire de Bezout;
+\item la factorisation, qui tant qu'elle n'est pas réalisable sur des grands nombres, garantit la sécurité du cryptage des données.
+\end{itemize}
+
+\section{Arithmétique modulaire}
+
+\section{Coefficients de Bézout}
+
+\section{Puissance de grands nombres}
+
+\section{Génération de grands nombres premiers}
+
+\section{Factorisation}
+
+
+\section{Conclusion}
+cf SMATH paragraphe applications p 223.
\ No newline at end of file
