X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/modelisationMathS3.git/blobdiff_plain/b4b8308e890b04add28f4a3991c9117d81908071..7d35709eec25c5d67b07004710bb49813f9c4477:/rsa.tex

diff --git a/rsa.tex b/rsa.tex
index fae4839..7301393 100644
--- a/rsa.tex
+++ b/rsa.tex
@@ -24,8 +24,8 @@ 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.pdf}
-%\includegraphics[scale=0.5]{schemacrypto.eps}
+%\includegraphics[scale=0.5]{schemacrypto.pdf}
+\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}
@@ -259,6 +259,7 @@ 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 
@@ -295,7 +296,8 @@ d'inconnues $x$ et $y$.
 
 
 \begin{Exo}[Sujet du bac S Liban 2005]
-On rappelle le rÃ©sultat suivant appelÃ© petit thÃ©orÃ¨me de Fermat.
+On rappelle le rÃ©sultat suivant appelÃ© le corollaire du 
+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$.}
@@ -368,10 +370,40 @@ que $ax \equiv 1[n]$.
 \begin{itemize}
 \item[\textbf{Existence.}]
 Comme $a$ et $n$ sont premiers entre eux, d'aprÃ¨s le thÃ©orÃ¨me de BÃ©zout,
-il exite $x$ et $y$ entiers tels que 
+il existe $x$ et $y$ entiers tels que 
+PREUVE A FINIR
+
+
 \end{itemize} 
 \end{Proof}
 
+\begin{Exp}
+Trouvons les nombres $x$ tels que $7x+11$ soit multiple de 36. Dit autrement, 
+rÃ©soudre l'Ã©quation $7x \equiv -11 [36]$. 
+
+On cherche un \og inverse \fg{} de 7 c.-Ã -d. un nombre $t$, $1 < t < 35$ 
+tel que $7t \equiv 1 [36]$. 
+Soit Ã  rÃ©soudre $7t \equiv 1 [36]$ qui revient Ã  trouver $t$ et $u$ tels
+que  $7t -36u = 1$, soit encore les coefficient de BÃ©zout relatifs Ã  
+(7 et 36). On trouve successivement 
+\begin{eqnarray*}
+36 & = & 7  \times 5 +1 \\ 
+7 & = & 7 \times 1 + 0 \\
+& \textrm{et donc}&\\
+1 & = & 36 - 7 \time 5
+\end{eqnarray*}
+et donc $t = -5$ (et $u=-1$). 
+On en dÃ©duit $7x \equiv -11 [36]$ est Ã©quivalent Ã  
+$(-5).7x \equiv (-5).-11 [36]$ soit encore 
+$x \equiv 55 [36] \equiv 19 [36]$.
+\end{Exp}
+
+\begin{Exo}
+Trouver les entiers relatif $x$ tels que 
+$261x +2$ soit multiple de 305.
+\end{Exo}
+
+
 
 \begin{Exo}
 \begin{enumerate}
@@ -385,13 +417,92 @@ il exite $x$ et $y$ entiers tels que
 \end{Exo}
 
 
-% cf TD maths discrÃ¨te; 
-% Corollaire 7.6 du chap RSA
-% unicitÃ© de la clef de dÃ©codage
 
 
+\begin{Exo}
+On se place dans le contexte de cryptographie par RSA.
+DÃ©montrer que si la clÃ© d'encryptage est $e < \varphi(n)$, alors 
+il existe une unique clÃ© de dÃ©codage entre 1 et $\varphi(n)$.
+\end{Exo}
+
+\begin{Prop}[ThÃ©orÃ¨me d'Euler]\label{th:Euler}
+  Si $m<n$ est  relativement premier avec $n$, alors 
+\begin{equation}
+m^{\varphi(n)}\equiv1 [n].
+\end{equation}
+\end{Prop}
+On laisse de cÃ´tÃ© la dÃ©monstration.
+
+\begin{Prop}[Correction de RSA]
+Le cryptage-dÃ©cryptage du code RSA est correct: 
+on crypte un message $m$ tel que 
+$m\land n= 1$ en $a$ avec  
+$ m^e  \equiv a [n]$ selon la clÃ© $(e,n)$.
+Alors le dÃ©cryptage selon la clÃ© $(d,n)$ redonne
+le message initial : $a^d \equiv m [n]$.
+\end{Prop} 
+\begin{Proof}
+\begin{eqnarray*}
+a^d & \equiv &   (m^e)^d [n]\\
+& \equiv &   m^{ed} [n] (\textrm{ rÃ©Ã©criture})\\
+& \equiv &   m^{k.\varphi(n)+1} [n] (\textrm{ dÃ©finition de $d$})\\
+& \equiv &   m^{k.\varphi(n)}m [n] (\textrm{ rÃ©Ã©criture})\\
+& \equiv &   (m^{\varphi(n)})^km [n] (\textrm{ rÃ©Ã©criture})\\
+& \equiv &   (1)^km [n] (\textrm{ thÃ©orÃ¨me d'Euler})\\
+& \equiv &   m [n] (\textrm{ rÃ©Ã©criture})\\
+\end{eqnarray*}
+\end{Proof}
+
+
+\begin{Prop}[Petit thÃ©orÃ¨me de Fermat]
+Si $p$ est un nombre premier et $a$ un entier 
+alors $a^{p} \equiv a [p]$.
+\end{Prop}
+
+\begin{Proof}
+La preuve se fait par rÃ©currence sur $a$. 
+\begin{itemize}
+\item Pour $a=0$, c'est trivial.
+\item Supposons la formule Ã©tablie pour $k=a$ et montrons qu'elle l'est aussi
+pour $k=a+1$. 
+On remarque tout d'abord que pour chaque $k$, $0 < k < p$, le coefficient 
+binomial $\binom{p}{k} = \frac{p!}{k!(p-k)!}$ est divisible par $p$, c.-Ã -d.
+$\binom{p}{k} \equiv 0 [p]$.
+On a alors successivement:
+\begin{eqnarray*}
+(k+1)^p &=& a^p + 
+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\dots +\binom{p}{p-1}a^{1}+1\\
+&\equiv& a^p +1 [p]\textrm{ (d'aprÃ¨s la remarque sur les coeff. binomiaux)}\\\
+&\equiv& a +1 [p]\textrm{ (par hypothÃ¨se de rÃ©currence)}\\\
+\end{eqnarray*}
+\end{Proof}
+
+\begin{Prop}[Corrolaire du petit thÃ©orÃ¨me de Fermat]
+Si $p$ est un nombre premier et $a$ un entier non divisible par $p$,
+alors $a^{p-1}-1$ est un multiple de $p$,
+\end{Prop}
+\begin{Proof}
+D'aprÃ¨s le petit thÃ©orÃ¨mede Fermat, $a^{p}  \equiv a [p]$. Dit Autrement
+$p$ divise $a^{p} - a = a (a^{p-1}-1)$. Or $p$ ne divise pas $a$ d'aprÃ¨s les 
+hypothÃ¨ses. D'aprÃ¨s le thÃ©orÃ¨me de Gau{\ss}, $p$ divise $a^{p-1}-1$.
+\end{Proof}
+
 \subsection{Puissance de grands nombres}
 
+\begin{Exp}
+Calculons $666^{999}[13]$.
+On a successivement:
+\begin{eqnarray*}
+666^{999} & \equiv & (13\times 51 + 3)^{999} [13]\\ 
+ & \equiv & 3^{999} [13]\\ 
+ & \equiv & 3^{12\times83 +3} [13] \\
+ & \equiv & 3^3 \time (3^{12})^{83} [13] \\
+ & \equiv & 3^3 \time (1)^{83} [13] \textrm{(car $3^{12}\equiv 1 [13]$ d'aprÃ¨s le corollaire du petit thÃ©orÃ¨me de Fermat)}\\ 
+ & \equiv & 27 [13]\\
+ & \equiv & 1 [13]
+\end{eqnarray*} 
+\end{Exp}
+
 
 \begin{Exo}
 Montrer que l'entier naturel $n$ est premier si et seulement si 
@@ -399,10 +510,169 @@ $$(x +1) ^n \equiv x ^n +1[n].$$
 \end{Exo}
 
 
+
+
+\begin{Exo}
+Calculer $2^{500} [13]$ et $26^{1000} [17]$.
+\end{Exo}
+
+
 \section{GÃ©nÃ©ration de grands nombres premiers}
+Dans ce qui suit, on nomme $\Prem$ l'ensemble des nombrs premiers.
+Depuis Euclide, on sait que $\Prem$ est de taille infinie.
+Fermat avait cru donner une formule ne gÃ©nÃ©rant que des nombres premiers.
+Il affirmait que pour tout $n \in \N$, le nombre 
+\begin{eqnarray}
+F_n &= & 2^{2^n} +1 
+\end{eqnarray}
+Ã©tait premier. Or 641 divise $F_5$. Aujourd'hui, on pense que seuls 
+les nombres de $F_0$ Ã  $F_4$ sont premiers, les qutres Ã©tant composÃ©s.
+
+\subsection{Distribution des nombres premier parmi les entiers}
+
+MÃªme si on ne connaÃ®t pas de formule permettant de construire tous les 
+nombres premiers, tout n'est pas perdu puisque les nombres premiers 
+ne sont pas si rares que cela. Le thÃ©orÃ¨me suivant donne mÃªme la distribution 
+la proportion approximative des entiers infÃ©rieurs ou Ã©gaux Ã 
+$N$  qui sont premiers.
+\begin{Prop}[ThÃ©orÃ¨me des nombres premiers]
+La fonction $\pi:\N \rightarrow \N$  associe 
+Ã  chaque nombre $n$ nombre d'entiers infÃ©rieurs ou Ã©gaux Ã  $n$ qui sont 
+premiers, soit $\pi(N) = |\{p \le N | p \textrm{premier}\}|$.
+Lorsque $n$ est grand, on a:
+\begin{eqnarray}
+\pi(N) &\approx& \dfrac{N}{\ln(N)}
+\end{eqnarray}
+\end{Prop}
+La preuve de ce thÃ©orÃ¨me est d'un niveau trÃ¨s avancÃ© et n'est pas reproduite 
+ici.
+
+Pour obtenir un  entier de 100 chiffres, il suffit de considÃ©rer 
+$N= 10^{100}$. Si on choisit au hasard un nombre $n$ dans $\N_{N}^{*}$,
+la probabilitÃ© qu'il soit premier est: 
+\begin{eqnarray*}
+\textrm{Prob}(n \textrm{ premier}) &\approx&
+ \dfrac{\dfrac{N}{\ln(N)}}{N} \\
+ &\approx&
+ \dfrac{1}{\ln(N)}
+\end{eqnarray*}
+Le tableau~\ref{Table:propPrem} donne une valeur approchÃ©e de 
+cette probabilitÃ© pour quelques nombres de chiffres. 
+Dans celui-ci:
+\begin{itemize}
+\item la seconde ligne n'impose aucune restriction sur le dernier chiffre;
+\item la troisiÃ¨me ligne impose que le dernier chiffre soit dans 
+  $\{1,3,5,7,9\}$: il est  inutile de vÃ©rifier que les
+  multiples de 2 sont premiers!
+\item la quatriÃ¨me ligne impose que le dernier chiffre soit dans $\{1,3,7,9\}$:
+  les multiples de 5 ne sont pas premiers!
+\end{itemize}
+On constate que si l'on tire au hasard un nombre (mÃªme de 100 chiffres), 
+parmi ceux qui se terminent par $\{1,3,7,9\}$ (ensemble notÃ© $B$ par la suite) 
+la probabilitÃ© qu'il soit premier n'est pas infime. La solution au problÃ¨me 
+de gÃ©nÃ©ration de nombres premiers repose sur la capacitÃ© ou non a disposer 
+d'un test efficace de primalitÃ© pour des grands nombres.
+
+%% Attention ce tableau est gÃ©nÃ©rÃ© par ailleurs 
+\begin{table}[ht]
+\begin{center}
+\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|}
+ \hline 
+Nombre de chiffres & \textbf{75}& \textbf{100}& \textbf{125}& \textbf{150}& \textbf{175}& \textbf{200}& \textbf{225}& \textbf{250}& \textbf{275}& \textbf{300}\\
+\hline 
+Dernier chiffre quelconque & 172& 230& 287& 345& 402& 460& 518& 575& 633& 690\\
+\hline 
+Dernier chiffre impair & 86& 115& 143& 172& 201& 230& 259& 287& 316& 345\\
+\hline 
+Dernier chiffre dans $\{1,3,7,9\}$& 69& 92& 115& 138& 161& 184& 207& 230& 253& 276\\
+\hline
+ \end{tabular}
+\end{center}
+\caption{ProbabilitÃ©s inverse d'obtenir un \label{Table:propPrem}}
+\end{table}
+
+
+On considÃ¨re comme expÃ©rience alÃ©atoire le fait de tirer un nombre au hasard 
+dans $B$. On a une probabilitÃ© $p$ que le nombre soit premier.
+Soit $X$ la variable alÃ©atoire qui compte le nombre 
+de fois oÃ¹ l'on a rÃ©alisÃ© cette expÃ©rience avant d'obtenir un nombre premier.
+$X$ suit une loi gÃ©omÃ©trique de paramÃ¨tre $p$:
+\[
+P(X=k) = (1-p)^{k-1}p.
+\]
+Or l'espÃ©rance d'une variable alÃ©atoire
+suivant une loi gÃ©omÃ©trique de paramÃ¨tre $p$ est $\frac{1}{p}$.
+Pour 100 chiffres, il faudra en moyenne 92 tirages pour gÃ©nÃ©rer un 
+nombre premier. 
+
+Il \og reste \fg{} Ã  fournir une mÃ©thode efficace pour dÃ©cider 
+de la primalitÃ© d'un entier, ce que prÃ©sente la section suivante.
+
+
+\subsection{Tests de primalitÃ©}
+Chque section donne un algorithme permettant de dÃ©cider si un entier $p$ fourni
+en entrÃ©e est premier ou non.
+
+\subsubsection{MÃ©thode naÃ¯ve}
+On vÃ©rifie s'il est divisible par l'un des entiers pairs compris entre 2 et 
+$\sqrt{p}$. Si la rÃ©ponse est nÃ©gative, alors $p$ est premier, 
+sinon il est composÃ©. Pour amÃ©liorer la performance de cette mÃ©thode, on peut 
+calculer Ã  l'avance une liste des nombres premiers infÃ©rieurs Ã  $\sqrt{p}$
+(avec un crible d'ÃratosthÃ¨ne), pour ne tester que ceux-ci.
+
+Par exemple, pour tester un nombre infÃ©rieur Ã  39 000, 
+il suffit de vÃ©rifier  qu'il nest pas multiple d'un nombre premiers infÃ©rieur
+Ã  198 (car $198^2 = 39 204$); on doit faire au maximum 45 divisions.
+
+\subsubsection{Tests probabilistes}
+
+\begin{Prop}[Corrolaire du petit thÃ©orÃ¨me de Fermat]
+Si $p$ est un nombre premier et $a$ un entier non divisible par $p$,
+alors $a^{p-1}-1$ est un multiple de $p$, c'est-Ã -dire:
+\begin{equation}
+ \forall a\in \N \forall p \in \N (   p \in \Prem \textrm{ et }   a \not\equiv  0[p] 
+  \Rightarrow a^{p-1}\equiv 1 [p]).
+\label{petittheremeFermat}
+\end{equation}
+\end{Prop}
+
+
+\paragraph{Test de Fermat.}
+Le petit thÃ©orÃ¨me de Fermat est une implication et non pas une Ã©quivalence:
+\begin{itemize}
+\item si on prend un $p\in \N$ et un $a \in\N$ quelconque, 
+  alors si $p$ est premier et $a$ non divisible par $p$, alors on peut en dÃ©duire que $a^{p-1}\equiv 1 [p]$;
+\item rien ne dit que si on a  $a^{p-1}\equiv 1 [p]$, alors $p$ est premier et $a$ non divisible par $p$.
+\item rien ne dit non plus que que si on a  $a^{p-1}\equiv 1 [p]$ et que $a$ non divisible par $p$, alors $p$ est premier.
+\end{itemize}
+Cependant si on effectue un grand nombre de fois l'expÃ©rience de choisir 
+$a \in \N_{n-1}^{*}$ et qu'Ã  chaque foit on Ã©tablit $a^{p-1}\equiv 1 [p]$, 
+alors $p$ est probablement premier.
+Cependant ce n'est pas toujours le cas: par exemple $2^{340} \equiv 1 [341]$ et 
+pourtant $341 =  11 \times 31$.
+
+\begin{Exo}
+Donner le code de la fonction \verb+testPrimaliteFermat(n,t)+ qui retourne \verb+True+ si \verb+t+ evaluations de $\texttt{a}^{\texttt{p}-1}\equiv 1 [\texttt{p}]$ pour un  
+\end{Exo}
+
+
+
+\paragrpah{Test de Miller-Rabin}
 
 \section{Factorisation}
 
 
+
+\begin{Exo}
+On considÃ¨re que l'Ã©tape 1 de l'algorithme RSA a gÃ©nÃ©rÃ© deux nombre premiers $p$ et $q$ tels que $p>q$. On definit  $t = \frac{p+q}{2}$ et $s = \frac{pâq}{2}$.
+Montrer que
+\begin{enumerate}
+\item le produit $n = pq = t^2 â s^2$;
+\item l'entier $t$ est lÃ©gÃ¨rement supÃ©rieur Ã  la racine carrÃ©e de $n$ et que $s $ est petit;
+\item l'on peut utiliser ces informations pour factoriser $n$ c.-Ã -d. retrouver $p$ et $q$.
+\item Factoriser 9623827 et  343570291, % res=2953*3259     res = 17729*19379
+\end{enumerate}
+\end{Exo}
+
 \section{Conclusion}
 cf SMATH paragraphe applications p 223.
\ No newline at end of file
