From 6a1d659a8d09f1c48fe968a3d6b9941576e22dfe Mon Sep 17 00:00:00 2001 From: couchot <jf.couchot@gmail.com> Date: Thu, 4 Sep 2014 08:25:33 +0200 Subject: [PATCH] debut premiers --- rsa.tex | 122 +++++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 116 insertions(+), 6 deletions(-) diff --git a/rsa.tex b/rsa.tex index fae4839..d9312ed 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 @@ -384,11 +385,39 @@ il exite $x$ et $y$ entiers tels que \end{enumerate} \end{Exo} +\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} -% cf TD maths discrète; -% Corollaire 7.6 du chap RSA -% unicité de la clef de décodage - +\begin{Prop}[Théorème d'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} \subsection{Puissance de grands nombres} @@ -400,6 +429,87 @@ $$(x +1) ^n \equiv x ^n +1[n].$$ \section{Génération de grands nombres premiers} +Depuis Euclide, on sait qu'il y a une infinité de nombres premiers. +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), +et que ce nombre se termine par$\{1,3,7,9\}$, +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. + +Pour peut qu'on dispose d'un test de primalité rapide, + + +il \og suffit \fg{} +de tirer quelques nombres au hasard pour avoir + +%% 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} + +\subsection{Tests de primalité} + + \section{Factorisation} -- 2.39.5