\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Mes commandes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\multirows}[3]{\multirow{#1}{#2}{$#3$}}%pour rester en mode math \renewcommand{\arraystretch}{1.3}%pour augmenter la taille des case \newcommand{\point}[1]{\marginnote{\small\vspace*{-1em} #1}}%pour indiquer les points ou le temps \newcommand{\dpl}[1]{\displaystyle{#1}}%megamode \newcommand{\A}{\mathscr{A}} \newcommand{\LN}{\mathscr{N}} \newcommand{\LL}{\mathscr{L}} \newcommand{\K}{\mathbb{K}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\M}{\mathcal{M}} \newcommand{\D}{\mathbb{D}} \newcommand{\E}{\mathcal{E}} \renewcommand{\P}{\mathcal{P}} \newcommand{\G}{\mathcal{G}} \newcommand{\Kk}{\mathcal{K}} \newcommand{\Cc}{\mathcal{C}} \newcommand{\Zz}{\mathcal{Z}} \newcommand{\Ss}{\mathcal{S}} \newcommand{\B}{\mathbb{B}} \newcommand{\inde}{\bot\!\!\!\bot} \newcommand{\Proba}{\mathbb{P}} \newcommand{\Esp}[1]{\dpl{\mathbb{E}\left(#1\right)}} \newcommand{\Var}[1]{\dpl{\mathbb{V}\left(#1\right)}} \newcommand{\Cov}[1]{\dpl{Cov\left(#1\right)}} \newcommand{\base}{\mathcal{B}} \newcommand{\Som}{\textbf{Som}} \newcommand{\Chain}{\textbf{Chain}} \newcommand{\Ar}{\textbf{Ar}} \newcommand{\Arc}{\textbf{Arc}} \newcommand{\Min}{\text{Min}} \newcommand{\Max}{\text{Max}} \newcommand{\Ker}{\text{Ker}} \renewcommand{\Im}{\text{Im}} \newcommand{\Sup}{\text{Sup}} \newcommand{\Inf}{\text{Inf}} \renewcommand{\det}{\texttt{det}} \newcommand{\GL}{\text{GL}} \newcommand{\crossmark}{\text{\ding{55}}} \renewcommand{\checkmark}{\text{\ding{51}}} \newcommand{\Card}{\sharp} \newcommand{\Surligne}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\SurligneMM}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \renewcommand{\lim}[1]{\underset{#1}{lim}\,} \newcommand{\nonor}[1]{\left|#1\right|} \newcommand{\Un}{1\!\!1} \newcommand{\sepon}{\setlength{\columnseprule}{0.5pt}} \newcommand{\sepoff}{\setlength{\columnseprule}{0pt}} \newcommand{\flux}{Flux} \newcommand{\Cpp}{\texttt{C++\ }} \newcommand{\Python}{\texttt{Python\ }} %\newcommand{\comb}[2]{\begin{pmatrix} #1\\ #2\end{pmatrix}} \newcommand{\comb}[2]{C_{#1}^{#2}} \newcommand{\arrang}[2]{A_{#1}^{#2}} \newcommand{\supp}[1]{Supp\left(#1\right)} \newcommand{\BB}{\mathcal{B}} \newcommand{\arc}[1]{\overset{\rotatebox{90}{)}}{#1}} \newcommand{\modpi}{\equiv_{2\pi}} \renewcommand{\Re}{Re} \renewcommand{\Im}{Im} \renewcommand{\bar}[1]{\overline{#1}} \newcommand{\mat}{\mathcal{M}} \newcommand{\und}[1]{{\mathbf{\color{red}\underline{#1}}}} \newcommand{\rdots}{\text{\reflectbox{$\ddots$}}} \newcommand{\Compa}{Compa} \newcommand{\dint}{\dpl{\int}} \newcommand{\intEFF}[2]{\left[\!\left[#1 ; #2\right]\!\right]} \newcommand{\intEFO}[2]{\left[\!\left[#1 ; #2\right[\!\right[} \newcommand{\intEOF}[2]{\left]\!\left]#1 ; #2\right]\!\right]} \newcommand{\intEOO}[2]{\left]\!\left]#1 ; #2\right[\!\right[} \newcommand{\ou}{\vee} \newcommand{\et}{\wedge} \newcommand{\non}{\neg} \newcommand{\implique}{\Rightarrow} \newcommand{\equivalent}{\Leftrightarrow} \newcommand{\Ab}{\overline{A}} \newcommand{\Bb}{\overline{B}} \newcommand{\Cb}{\overline{C}} \newcommand{\Cl}{\texttt{Cl}} \newcommand{\ab}{\overline{a}} \newcommand{\bb}{\overline{b}} \newcommand{\cb}{\overline{c}} \newcommand{\Rel}{\mathcal{R}} \newcommand{\superepsilon}{\varepsilon\!\!\varepsilon} \newcommand{\supere}{e\!\!e} \makeatletter \newenvironment{console}{\noindent\color{white}\begin{lrbox}{\@tempboxa}\begin{minipage}{\columnwidth} \ttfamily \bfseries\vspace*{0.5cm}} {\vspace*{0.5cm}\end{minipage}\end{lrbox}\colorbox{black}{\usebox{\@tempboxa}} } \makeatother \def\ie{\textit{i.e. }} \def\cf{\textit{c.f. }} \def\vide{ { $ {\text{ }} $ } } %Commande pour les vecteurs \newcommand{\grad}{\overrightarrow{Grad}} \newcommand{\Vv}{\overrightarrow{v}} \newcommand{\Vu}{\overrightarrow{u}} \newcommand{\Vw}{\overrightarrow{w}} \newcommand{\Vup}{\overrightarrow{u'}} \newcommand{\Zero}{\overrightarrow{0}} \newcommand{\Vx}{\overrightarrow{x}} \newcommand{\Vy}{\overrightarrow{y}} \newcommand{\Vz}{\overrightarrow{z}} \newcommand{\Vt}{\overrightarrow{t}} \newcommand{\Va}{\overrightarrow{a}} \newcommand{\Vb}{\overrightarrow{b}} \newcommand{\Vc}{\overrightarrow{c}} \newcommand{\Vd}{\overrightarrow{d}} \newcommand{\Ve}[1]{\overrightarrow{e_{#1}}} \newcommand{\Vf}[1]{\overrightarrow{f_{#1}}} \newcommand{\Vn}{\overrightarrow{0}} \newcommand{\Mat}{Mat} \newcommand{\Pass}{Pass} \newcommand{\mkF}{\mathfrak{F}} \renewcommand{\sp}{Sp} \newcommand{\Co}{Co} \newcommand{\vect}[1]{\texttt{Vect}\dpl{\left( #1\right)}} \newcommand{\prodscal}[2]{\dpl{\left\langle #1\left|\vphantom{#1 #2}\right. #2\right\rangle}} \newcommand{\trans}[1]{{\vphantom{#1}}^{t}{#1}} \newcommand{\ortho}[1]{{#1}^{\bot}} \newcommand{\oplusbot}{\overset{\bot}{\oplus}} \SelectTips{cm}{12}%Change le bout des flèches dans un xymatrix \newcommand{\pourDES}[8]{ \begin{itemize} \item Pour la ligne : le premier et dernier caractère forment $#1#2$ soit $#4$ en base 10. \item Pour la colonne : les autres caractères du bloc forment $#3$ soit $#5$ en base 10. \item A l'intersection de la ligne $#4+1$ et de la colonne $#5+1$ de $S_{#8}$ se trouve l'entier $#6$ qui, codé sur $4$ bits, est \textbf{\texttt{$#7$}}. \end{itemize} } \)
Exercice

L'exercice suivant est automatiquement et aléatoirement généré par ataraXy.
Si vous regénérez la page (F5) les valeurs seront changées.
La correction se trouve en bas de page.


Exercice


On considère dans le système RSA, la clef publique \( (3869, 1883)\) .
  1. Déterminer deux entiers \( p\) et \( q\) tel que \( p {<} q\) et \( 3869=pq\) .
  2. Justifier que \( (3869, 1883)\) est une clef publique valide du cryptosystème RSA.
    1. Déterminer la décomposition de \( 1883\) en binaire.
    2. Calculer \( 55^{1883}\) modulo \( 3869\) .
    3. Quel est le message chiffré de \( M=55\) .
  3. Déterminer la clef privé associée à la clef publique \( (3869, 1883)\) .
  4. Déchiffrer le message \( M'=222\)
Cliquer ici pour afficher la solution

Exercice


  1. On observe que \( 3869=73\times 53\) .
  2. Pour vérifier que \( (3869, 1883)\) est une clef publique valide du cryptosystème RSA, il faut d'une part que \( 3869\) soit le produit de deux nombres premiers, ce que nous avons vérifier à la question précédente. Il faut d'autre part que \( 1883\) soit inversible modulo \( \phi=(p-1)(q-1)=72\times52=3744\) . Ce qui se vérifie avec l'algorithme d'Euclide : \[\begin{array}{|c|c|c|c||c|c|}\hline a&b&r&q&u&v \\ \hline 3744 & 1883 & 1861 & 1&-428 & 851 \\ \hline 1883 & 1861 & 22 & 1&423 & -428 \\ \hline 1861 & 22 & 13 & 84&-5 & 423 \\ \hline 22 & 13 & 9 & 1&3 & -5 \\ \hline 13 & 9 & 4 & 1&-2 & 3 \\ \hline 9 & 4 & 1 & 2&1 & -2 \\ \hline 4 & 1 & 0 & 4&0 & 1 \\ \hline \end{array}\]
    1. Le nombre \( 1883\) en binaire s'écrit \( 11101011011\) .
    2. On appliquel'algorithme d'exponentiation modulaire : \[ \begin{array}{r|*{11}{|c}} k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\\hline55^{2^k} & 55 & 3025 & 9150625 & 193600 & 22500 & 9954025 & 8743849 & 14273284 & 294849 & 648025 & 3617604\\mod\ 3869 & \fbox{55} & \fbox{3025} & 440 & \fbox{150} & \fbox{3155} & 2957 & \fbox{3778} & 543 & \fbox{805} & \fbox{1902} & \fbox{89} \end{array} \] Finalement \( 55^{1883}=1200\)
    3. Lorsque l'on applique le processus de chiffrement RSA avec \( (3869, 1883)\) comme clef publique a un message \( M\) , il faut réaliser l'opération \( M^e\% n\) soit ici \( M=55\) soit \( 55^{1883}\) modulo \( 3869\) que nous avons fait à la question précédente. Le chiffrement de \( M=55\) est donc \( 1200\) .
  3. Pour déterminer la clef privé associée à \( (3869, 1883)\) , il suffit de déterminer l'inverse de \( 1883\) modulo \( 3744\) . Nous avons précédement appliquer l'algorithme d'Euclide étendue. Nous observons donc que la clef privé est \( (3869, 851)\) .
  4. Comme précédement on va appliquer l'algorithme d'exponentiation modulaire rapide pour calculer \( 222^{851}\) modulo \( 3869\) . \[ \begin{array}{r|*{10}{|c}} k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\\hline222^{2^k} & 222 & 49284 & 8156736 & 781456 & 14341369 & 8151025 & 8473921 & 657721 & 14899600 & 6561\\mod\ 3869 & \fbox{222} & \fbox{2856} & 884 & 3787 & \fbox{2855} & 2911 & \fbox{811} & 3860 & \fbox{81} & \fbox{2692} \end{array} \] Finalement le déchiffrement de \( 222\) est \( 49\) .