From: couchot Date: Tue, 2 Sep 2014 06:53:32 +0000 (+0200) Subject: initialisation X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/modelisationMathS3.git/commitdiff_plain/ffce293ccbd93a8d34365b009c246eead8d3b0be initialisation --- ffce293ccbd93a8d34365b009c246eead8d3b0be diff --git a/C.tex b/C.tex new file mode 100644 index 0000000..ab8d9b7 --- /dev/null +++ b/C.tex @@ -0,0 +1,58 @@ +\relax +\providecommand\hyper@newdestlabel[2]{} +\@setckpt{}{ +\setcounter{page}{4} +\setcounter{equation}{0} +\setcounter{enumi}{6} +\setcounter{enumii}{0} +\setcounter{enumiii}{0} +\setcounter{enumiv}{0} +\setcounter{footnote}{0} +\setcounter{mpfootnote}{0} +\setcounter{part}{0} +\setcounter{chapter}{1} +\setcounter{section}{8} +\setcounter{subsection}{0} +\setcounter{subsubsection}{0} +\setcounter{paragraph}{0} +\setcounter{subparagraph}{0} +\setcounter{figure}{1} +\setcounter{table}{0} +\setcounter{parentequation}{0} +\setcounter{endNonectr}{3} +\setcounter{currNonectr}{0} +\setcounter{subfigure}{0} +\setcounter{lofdepth}{1} +\setcounter{subtable}{0} +\setcounter{lotdepth}{1} +\setcounter{lstnumber}{1} +\setcounter{LT@tables}{0} +\setcounter{LT@chunks}{0} +\setcounter{cnt@a}{100} +\setcounter{cnt@b}{0} +\setcounter{cnt@c}{0} +\setcounter{cnt@@a}{0} +\setcounter{cnt@@b}{0} +\setcounter{cnt@@c}{0} +\setcounter{AlgoLine}{0} +\setcounter{algocfline}{0} +\setcounter{algocfproc}{0} +\setcounter{algocf}{0} +\setcounter{currExoctr}{0} +\setcounter{endExoctr}{0} +\setcounter{Exo}{0} +\setcounter{currTPctr}{0} +\setcounter{endTPctr}{0} +\setcounter{TP}{0} +\setcounter{currDefctr}{0} +\setcounter{endDefctr}{0} +\setcounter{Def}{0} +\setcounter{currPropctr}{0} +\setcounter{endPropctr}{0} +\setcounter{Prop}{0} +\setcounter{Item}{6} +\setcounter{Hfootnote}{0} +\setcounter{bookmark@seq@number}{12} +\setcounter{lstlisting}{0} +\setcounter{section@level}{1} +} diff --git a/main.tex b/main.tex new file mode 100755 index 0000000..59c3391 --- /dev/null +++ b/main.tex @@ -0,0 +1,153 @@ +\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} diff --git a/rsa.tex b/rsa.tex new file mode 100644 index 0000000..541d3c2 --- /dev/null +++ b/rsa.tex @@ -0,0 +1,346 @@ + +% 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 rb \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 diff --git a/td.tex b/td.tex new file mode 100644 index 0000000..f912800 --- /dev/null +++ b/td.tex @@ -0,0 +1,128 @@ + +% 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