\documentclass[a4paper,12pt]{article} \usepackage[french]{babel} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{amssymb,amsthm,amsmath,amsfonts,mathrsfs} \newtheoremstyle{custom}% {\topsep}% {\topsep}% {\normalfont}% {}% {\bfseries}% {.}% {\newline}% (default .5em) {}% \theoremstyle{custom} \usepackage{textcomp} %\usepackage{bbm} \usepackage{geometry} \usepackage{mathrsfs} \usepackage{enumitem} \usepackage{csquotes} %\usepackage{esvect} % Pour des vecteurs \usepackage{hyperref} %Pour des liens hypertexte ! \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= black, %couleur des liens internes % linktoc =all, %defines which part of an entry in the table of contents is made into a link % citecolor=black, %color of citation links (bibliography) % filecolor=black, %color of file links % bookmarks=true, %créé des signets pour Acrobat bookmarksopen=true, %si les signets Acrobat sont créés, %les afficher complètement. pdftitle={M1 algèbre effective}, %informations apparaissant dans pdfauthor={Samuel Le Fourn}, %dans les informations du document } \frenchspacing \newtheorem{thm}{Théorème}[section] \newtheorem{prop}[thm]{Proposition} \newtheorem{cor}[thm]{Corollaire} \newtheorem*{thmsansnom}{Théorème} \newtheorem*{propsansnom}{Proposition} \newtheorem{lem}[thm]{Lemme} \theoremstyle{custom} \newtheorem{defi}[thm]{Définition} \newtheorem{rem}[thm]{Remarque} \newtheorem{exe}[thm]{Exemple} \newtheorem{exocours}[thm]{Exercice de cours} \newtheorem{exerciseaux}[thm]{Exercice} %\newenvironment{exo}{\begin{exerciseaux}\leavevmode\par}{\end{exo}} \newtheorem{exo}[thm]{Exercice} \def\R{\mathbb{R}} \def\C{\mathbb{C}} \def\N{\mathbb{N}} \def\Z{\mathbb{Z}} \def\Q{\mathbb{Q}} \def\F{\mathbb{F}} \def\1{\mathbbm{1}} \def\Ncal{\mathcal{N}} \DeclareMathOperator{\pgcd}{pgcd} \DeclareMathOperator{\ppcm}{ppcm} \DeclareMathOperator{\GL}{GL} \DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\Inn}{Inn} \DeclareMathOperator{\id}{id} \newcommand{\Ker}{\operatorname{Ker}} \setlist{noitemsep} \setlist[1]{labelindent=\parindent} % < Usually \setlist[itemize]{leftmargin=*} %d\setlist[itemize]{label = ($(\arabic*)$)} \setlist[enumerate]{label = ($\alph*$)} %%%%%%%%%%%%%%%%%% % Alphabet Grec % %%%%%%%%%%%%%%%%%% \renewcommand{\a}{\alpha} \renewcommand{\b}{\beta} \newcommand{\g}{\gamma} \renewcommand{\d}{\delta} \newcommand{\e}{\epsilon} \newcommand{\f}{\varphi} \renewcommand{\l}{\lambda} \renewcommand{\k}{\kappa} \newcommand{\m}{\mu} \newcommand{\n}{\nu} \renewcommand{\o}{\omega} \renewcommand{\r}{\rho} \newcommand{\s}{\sigma} \renewcommand{\t}{\tau} \newcommand{\z}{\zeta} \newcommand{\D}{\Delta} \newcommand{\G}{\Gamma} %%%%%%%%%%%%%%%%%%%% % Alphabet gothique% %%%%%%%%%%%%%%%%%%%% \newcommand{\ga}{{\mathfrak{a}}} \newcommand{\gA}{{\mathfrak{A}}} \newcommand{\gb}{{\mathfrak{b}}} \newcommand{\gB}{{\mathfrak{B}}} \newcommand{\gc}{{\mathfrak{c}}} \newcommand{\gC}{{\mathfrak{C}}} \newcommand{\gd}{{\mathfrak{d}}} \newcommand{\gD}{{\mathfrak{D}}} \newcommand{\gI}{{\mathfrak{I}}} \newcommand{\gm}{{\mathfrak{m}}} \newcommand{\gn}{{\mathfrak{n}}} \newcommand{\go}{{\mathfrak{o}}} \newcommand{\gO}{{\mathfrak{O}}} \newcommand{\gp}{{\mathfrak{p}}} \newcommand{\qg}{{\mathfrak{q}}} \newcommand{\gP}{{\mathfrak{P}}} \newcommand{\gQ}{{\mathfrak{Q}}} \newcommand{\gq}{{\mathfrak{q}}} \newcommand{\gR}{{\mathfrak{R}}} \newcommand{\gS}{{\mathfrak{S}}} \newcommand{\gJ}{{\mathfrak{J}}} %%%%%%%%%%%%%%%%%%%%%%%%%%% % Alphabet calligraphique % %%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\Acal}{{\mathcal A}} \newcommand{\Bcal}{{\mathcal B}} \newcommand{\Ccal}{{\mathcal C}} \newcommand{\Dcal}{{\mathcal D}} \newcommand{\Ecal}{{\mathcal E}} \newcommand{\Fcal}{{\mathcal F}} \newcommand{\Gcal}{{\mathcal G}} \newcommand{\Hcal}{{\mathcal H}} \newcommand{\Ical}{{\mathcal I}} \newcommand{\Jcal}{{\mathcal J}} \newcommand{\Kcal}{{\mathcal K}} \newcommand{\Lcal}{{\mathcal L}} \newcommand{\Mcal}{{\mathcal M}} \newcommand{\Ocal}{{\mathcal O}} \newcommand{\Pcal}{{\mathcal P}} \newcommand{\Qcal}{{\mathcal Q}} \newcommand{\Rcal}{{\mathcal R}} \newcommand{\Scal}{{\mathcal S}} \newcommand{\Tcal}{{\mathcal T}} \newcommand{\Ucal}{{\mathcal U}} \newcommand{\Vcal}{{\mathcal V}} \newcommand{\Wcal}{{\mathcal W}} \newcommand{\Xcal}{{\mathcal X}} \newcommand{\Ycal}{{\mathcal Y}} \newcommand{\Zcal}{{\mathcal Z}} %%%%%%%%%%%%%%%%%%%% % Alphabet en gras % %%%%%%%%%%%%%%%%%%%% \newcommand{\ab}{\mathbf{a}} %%%%%%%%%%%%%%%%%%%% % Ensembles usuels % %%%%%%%%%%%%%%%%%%%% \renewcommand{\P}{\mathbb{P}} \newcommand{\Fp}{{\mathbb{F}_{\! p}}} \newcommand{\A}{{\mathbb{A}}} \newcommand{\T}{{\mathbb{T}}} %%%%%%%%%%%%%%%%%%%%% % Opérateurs usuels % %%%%%%%%%%%%%%%%%%%%% \newcommand{\Card}{\operatorname{Card}} \newcommand{\Crit}{\operatorname{Crit}} \renewcommand{\div}{\operatorname{div}} \newcommand{\Div}{\operatorname{Div}} \newcommand{\End}{\operatorname{End}} \newcommand{\Gal}{\operatorname{Gal}} \newcommand{\SL}{\operatorname{SL}} \newcommand{\Id}{\operatorname{Id}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\mult}{\operatorname{mult}} \newcommand{\ord}{\operatorname{ord}} \newcommand{\Proj}{\operatorname{Proj}} \newcommand{\Spec}{\operatorname{Spec}} \newcommand{\Borel}{\operatorname{Borel}} \newcommand{\Stab}{\operatorname{Stab}} \newcommand{\Cart}{\operatorname{Cart}} \newcommand{\Cot}{\operatorname{Cot}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cl}{\operatorname{cl}} \newcommand{\gr}{\operatorname{gr}} \newcommand{\init}{\operatorname{in}} \newcommand{\PGL}{\operatorname{PGL}} \newcommand{\PSL}{\operatorname{PSL}} \newcommand{\Der}{\operatorname{Der}} \newcommand{\num}{\operatorname{num}} \renewcommand{\Re}{\operatorname{Re}} \newcommand{\im}{\operatorname{im}} \newcommand{\Jac}{\operatorname{Jac}} \newcommand{\Vect}{\operatorname{Vect}} \newcommand{\car}{\operatorname{car}} \newcommand{\Sp}{\operatorname{Sp}} \newcommand{\Pic}{\operatorname{Pic}} \newcommand{\carac}{\textrm{char}} \newcommand{\Tr}{\operatorname{Tr}} \renewcommand{\mod}{\, \operatorname{mod} \,} \newcommand{\Frac}{\operatorname{Frac}} \newcommand{\preuve}{\textcolor{blue}{$^{(P)}$}} %%%%%%%%%%% % Flèches % %%%%%%%%%%% \newcommand{\mt}{\mapsto} \newcommand{\lmt}{\longmapsto} \newcommand{\ra}{\rightarrow} \newcommand{\lra}{\longrightarrow} \newcommand{\La}{\Leftarrow} \newcommand{\Ra}{\Rightarrow} \newcommand{\Lra}{\Leftrightarrow} \newcommand{\Llra}{\Longleftrightarrow} \newcommand{\dessin}{\textcolor{green}{(D)}} %%% Commandes spécifiques à la géométrie affine %%%% %\newcommand{Evect}{\overrightarrow{E}} %\newcommand{Fvect}{\overrightarrow{F}} %\newcommand{uvect}{\overrightarrow{u}} %\newcommand{vvect}{\overrightarrow{v}} %%%%%%%%%%%%%%%%%% % Macros utiles %% %%%%%%%%%%%%%%%%%% \newcommand{\fonction}[5]{\begin{array}{c|ccl} % Pour écrire une fonction en environnement display : le nom puis espaces de départ et d'arrrivée, puis argument et résultat #1: & #2 & \longrightarrow & #3 \\ & #4 & \longmapsto & #5 \end{array}} \newcommand{\fonctionsansnom}[4]{\begin{array}{ccl} % La même sans le nom de la fonction à mettre #1 & \lra & #2 \\\ #3 & \lmt & #4 \end{array}} \newtheorem{enonce}[thm]{Exercice}%[section] \newenvironment{Ex}[0]{\begin{enonce}\rm}{\bigskip \end{enonce}} %\newtheorem{theoreme}{Th\'eor\`eme}%[section] \geometry{top=2cm, bottom=2cm} \begin{document} \newgeometry{top=1cm,bottom=2cm,left=2cm,right=2cm} \noindent {\large \textsc{Université Grenoble Alpes \hfill M1 \\ \hfill M1 Algèbre effective \hfill 2024-2025}} \\ \hrule \bigskip \begin{center} \textbf{\Large Cryptographie, RSA} \end{center} \bigskip \section{Exercices} % {\bf Exercice 1~: Cryptographie de Hill} % On code les lettres de A \`a Z par les nombres de 1 \`a 26, % l'espace par 0, \verb|,| par 27 et \verb|.| par 28. On groupe les caract\`eres par paires % et on utilise la matrice % $A=\left( \begin{array}{cc}5&7\\1&15\end{array}\right) \pmod{29}$. % \begin{enumerate} % \item Coder le message suivant : ``VIVE LES VACANCES'' % \item \`A quelle condition sur la matrice $A$ % le destinataire du message cod\'e pourra-t'il le d\'echiffrer ? % \item D\'ecoder : ``IKYTYEH HSAHVRDAM '' % % a:=[[5,7],[1,15]] % % b:=inv(a mod 29) % % M:="@VIVE@LES@VACANCES" % % L:=asc(M).-64 % % m:=char(flatten(irem(seq(a*L[2j..2j+1],j,0,size(L)/2-1) mod 0,29).+64) % % l:=asc(m).-64 % % char(flatten(irem(seq(b*l[2j..2j+1],j,0,size(l)/2-1) mod 0,29).+64) % % \item Dans cette question, la matrice $A$ n'est pas connue. % % Pouvez-vous d\'ecoder le message suivant sachant qu'il commence par ``les'' suivi d'un espace ? % % YGSCN CYSGSC % \end{enumerate} %{\bf Exercice 1} %Montrer que 65537 est premier par le crit\`ere de Lucas. % {\bf Exercice 1~: Cryptage matriciel \`a clef secr\`ete}\\ % Pour coder des messages pouvant contenir des caract\`eres de % diverses langues, on repr\'esente chaque caract\`ere par % un entier sur 16 bits (codage UTF16 par exemple). On d\'ecide ensuite % de crypter le message par blocs de 2 caract\`eres, en multipliant % chaque vecteur $v$ des 2 entiers repr\'esentant un bloc par une matrice carr\'ee $A$ % de taille 2 modulo un entier $p$ qui sera suppos\'e premier dans les % questions 1 \`a 6. La matrice $A$ est tenue % secr\`ete, c'est la clef secr\`ete du syst\`eme de cryptage. % \begin{enumerate} % \item % On suppose que $p$ est un nombre premier qui permet de repr\'esenter % de mani\`ere unique tous les entiers sur 16 bits par leur classe dans % $\Z/p\Z$. Quel est le nombre minimal de bits de $p$~? % \item On admettra que $p=65537$ est bien premier. % On pose~: % $$ p=65537, \quad % A=\left(\begin{array}{cc}263&4122\\1&1799\end{array}\right) % $$ % Crypter le vecteur $v$ correspondant aux deux caractÃ¨res ``intÃ©grale % double'' et ``intÃ©grale triple'' reprÃ©sentÃ©s respectivement par les % entiers 8748 et 8749, % %les deux caract\`eres % %int\'egrale double (8748) et int\'egrale triple (8749), % %$\left(\begin{array}{c}65\\66\end{array}\right)$, % i.e. calculer $w=Av$ modulo $p$ % \item D\'eterminer tous les vecteurs $z$ \`a coefficients % dans $\Z/p\Z$ tels que $Az=Av$ modulo $p$ pour $ p=65537$.\\ % En d\'eduire tous les vecteurs $z$ \`a coefficients entiers % qui v\'erifient $Az=Av$ modulo $p$. \\ % Si on impose que les coordonn\'ees de $z$ sont % dans l'intervalle du codage sur 16 bits, combien y-a-t-il de % solutions~? % \item % Que se passerait-il si on avait choisi la m\^eme matrice mais $p=6551$~? % \item Expliquer comment on peut d\'ecrypter, i.e. \'etant donn\'e $w$ quelconque, % comment on trouve $v$ tel que $Av=w$ modulo $p$. % \item Quel est le nombre de matrices $A$ possibles pour $p=65537$~? % Cela vous parait-il suffisant pour r\'esister \`a une attaque de la % clef secr\`ete $A$ par force brute~? Peut-on imaginer un autre % type d'attaque~? Comment pourrait-on renforcer la s\'ecurit\'e~? % \item Dans cette question, on suppose que $p=2^{16}$ et % n'est donc pas premier. % Peut-on appliquer l'algorithme du pivot de Gauss pour % r\'esoudre $Az=w=Av$ si on travaille modulo $p$ bien que $p$ ne % soit alors pas premier~? \\ % En est-il de m\^eme pour la matrice % $$ p=65536, \quad % A=\left(\begin{array}{cc}262&4122\\1&1799\end{array}\right) % $$ % \item Quel(s) avantage(s) et inconv\'enient(s) % y-a-t-il \`a travailler modulo $2^{16}$ % par rapport \`a $p=65537$~? % \end{enumerate} %%%%%%%%%%%% \begin{exo}[RSA jouet] On prend $p=17$ et $q=13$ donc $n=221$. \begin{enumerate} \item Déterminer $\varphi(n)$. \item V{\'e}rifier qu'on peut utiliser $e=7$ comme exposant de chiffrement. Calculer l'exposant de d{\'e}chiffrement $d$. \item Chiffrer $M=3$. D{\'e}chiffrer $C=198$. \item Pour $p$ et $q$ quelconque, estimer la complexit\'e des op\'erations de calcul des clefs, chiffrement, d\'echiffrement. \end{enumerate} \end{exo} \begin{exo}[RSA $e=3$] \begin{enumerate} \item[] \item Expliquer quel est l'intérêt de choisir $e=3$ comme clef publique si on ne se préoccupe pas de la sécurité. \item Supposons que $e=3$ soit utilisé pour vérifier des signatures, prenons pour exemple jouet $n=587 \times 383$. Comment peut-on calculer efficacement une signature $s$ correspondant à un nombre $m=s^e \pmod n$ sans connaitre la factorisation de $n$ si $s$ est inférieur à $n^{1/3}$ ? Par exemple pour $m=205379$. \item Pouquoi vaut-il mieux choisir $e=257$ ou $e=65537$ que $e=3$~? \end{enumerate} \end{exo} \begin{exo}[Diffie-Hellmann, secret commun] {\bf Exemple jouet}~:\\ Alice et Bob choisissent de travailler dans $\Z/19\Z$ et d'utiliser $g=2$ qui est un g\'en\'erateur de $(\Z/19\Z)^*$. \begin{enumerate} \item Alice choisit $a=7$ et Bob choisit $b=13$. Donner $A$ et $B$ puis le secret commun. \item Que se passe-t-il si Alice choisit $a=25$~? \`A quelle valeur maximale pour $a$ et $b$ Alice et Bob peuvent-ils se restreindre~? \item D\'eterminer la table de toutes les puissances de 2 dans $\mathbb{Z}/19 \mathbb{Z}$. \item Alice et Bob choisissent deux autres entiers $a$ et $b$ et s'envoient $A=4$ et $B=17$. En utilisant la table, d\'eterminer les valeurs de $a$ et $b$. Quelle est la valeur du secret commun~? \end{enumerate} \noindent {\bf S\'ecurit\'e}~:\\ On a vu qu'une personne qui connaît les entiers $A$ et $B$ (par exemple en espionnant les \'echanges entre Alice et Bob) pouvait calculer le secret commun si on travaille dans $\mathbb{Z}/19 \mathbb{Z}$. Pour esp\'erer s\'ecuriser le secret commun, il faut travailler dans $\Z/p\Z$ avec $p$ un nombre premier plus grand. \begin{enumerate} \item Commen\c{c}ons par essayer avec $p=65537$ et $g=3$. \begin{itemize} \item[$(i)$] V\'erifier que 3 est un g\'en\'erateur de $(\Z/p\Z)^*$. \item[$(ii)$] Si Alice choisit $a=12345$, combien doit-elle effectuer de multiplications pour calculer $A$ par l'algorithme de la puissance rapide~? \item[$(iii)$] \`A quelle valeur maximale pour $a$ et $b$ Alice et Bob peuvent-ils se restreindre ? \item[$(iv)$] Quelle est la taille de la table des puissances de 3 modulo $p$~? Comparer avec la question $(ii)$. La s\'ecurit\'e du secret commun vous semble-t-elle suffisante~? \end{itemize} \item On prend maintenant un nombre premier dont l'\'ecriture en base 2 comporte exactement 1024 bits, et tel que $g=2$ est un g\'en\'erateur de $(\Z/p\Z)^*$. La s\'ecurit\'e du secret commun vous semble-t-elle suffisante~? \end{enumerate} \end{exo} \begin{exo}[Attaque active contre Diffie-Hellman] On pourra travailler avec des valeurs explicites sur un exemple jouet de groupe $(\Z/19 \Z)^*$ avec comme générateur $g=2$. Alice et Bob veulent échanger un secret commun, ils choisissent chacun une clef secrète $a$, $b$ et envoient $g^a$ et $g^b$. Charles intercepte les messages et envoie à la place aux deux $g^e$ où $e$ est sa propre clef secrète. Comment Charles doit-il ensuite modifier les message émis par Alice qu'il intercepte pour les retransmettre à Bob~? \end{exo} \begin{exo}[Attaque contre RSA (module partagé)] Alice et Bob d\'ecident de recevoir des messages crypt\'es en utlisant le syst\`eme RSA. Ils publient donc chacun leur clef publique. On va \'etudier une attaque qu'un espion peut exploiter si Alice et Bob utilisent tous les deux la m\^eme valeur de $n$. On suppose donc que la clef publique d'Alice est $(n,e_A)$, et celle de Bob $(n,e_B)$. On suppose que Catherine envoie une m\^eme information $m$ \`a Alice et \`a Bob, donc envoie le message crypt\'e $c_A=m^{e_A} \pmod n$ \`a Alice et le message crypt\'e $c_B=m^{e_B} \pmod n$ \`a Bob. Un espion Daniel intercepte les deux messages crypt\'es. Dans l'exercice, on prendra $n=4897$ pour pouvoir faire des calculs \`a la calculatrice. \begin{enumerate} \item Dans cette question on suppose qu'on connaît la factorisation de $n$~: $n=59 \times 83$. Expliquer pourquoi on peut prendre $e_A=71$ et $e_B=227$. D\'eterminer la clef priv\'ee d'Alice. \item D\'eterminer une identit\'e de B\'ezout entre 71 et 227. \item En d\'eduire deux entiers $u$ et $v$ tels que $m=c_A^u c_B^v \pmod n$ \item Daniel intercepte $c_A=1846$ et $c_B=487$. D\'eterminer $m$ sans utiliser la factorisation de $n$. \item Expliquer pourquoi Daniel ne peut pas utiliser la factorisation de $n$ dans une attaque r\'eelle contre RSA. \end{enumerate} \end{exo} \begin{exo}[Attaque RSA par itération] \begin{enumerate} \item[] \item Exemple jouet : on prend $n=77$ et une cl\'e publique $c=7$, le message original est $a=2$. Retrouver le message original par it\'eration de la fonction de cryptage sur le message crypt\'e. \item En g\'en\'eral, quelles sont les valeurs de $c$ vuln\'erables \`a une attaque par it\'eration~? \end{enumerate} \end{exo} % {\bf Exercice 8~: Logarithme discret} % Calculer le logarithme en base $2$ de $3$ modulo 11. % {\bf Exercice 9~: Logarithme discret et restes chinois.}\\ % On consid{\`e}re le nombre premier 101 et on cherche, s'il existe, un entier $x\in \NN$ tel que $3^x=2~[101]$. % \begin{enumerate} % \item % \`A l'aide de l'algorithme d'exponentiation modulaire, calculer $3^4$, $2^4$, $3^{25}$ et $2^{25}$ modulo 101. % \item % D{\'e}terminer des entiers $a$, $b$ tels que $(3^4)^a=2^4$ et $(3^{25})^b=2^{25}$ modulo 101 % (pour d{\'e}terminer $a$, on pourra chercher les puissances successives de $3^4$ modulo 101). % \item % D\'eterminer $x$ tel que $x=a~[25]$ et $x=b~[4]$, v{\'e}rifier que % pour cet $x$, on a $3^x=2~[101]$. % \end{enumerate} % {\bf Exercice 10~: Logarithme discret p-adique} % Calculer le logarithme en base $2$ de $3$ modulo 197 en utilisant 2 % fois le logarithme en base 7 au lieu du logarithme en base 49. \section{TP} \begin{exo}[Vérification machine des calculs] Vérifier les résultats des exercices du TD. \end{exo} \begin{exo}[Générer une paire de clefs] Générer deux grands nombres premiers $p$ et $q$ au hasard puis une paire de clefs, en utilisant par exemple les fonctions \verb|nextprime| et \verb|randint| de Xcas ou le test de Miller-Rabin si votre langage pr\'ef\'er\'e n'a pas de test de primalit\'e. \end{exo} \begin{exo}[Codage et décodage d'un message (sur PC)] On transforme une chaine de caractères en une liste d'entiers et réciproquement (avec \verb|asc| et \verb|char| en Xcas, ou l'application r\'ep\'et\'ee de \verb|ord| et \verb|chr| en Python). Pour le moment on code caract\`ere par caract\`ere, sans s'inqui\'eter de la s\'ecurit\'e du codage. Pour coder/d\'ecoder une liste \verb|l| d'entiers, on peut utiliser \verb|pow(l,c,n)| en Xcas et Python. \begin{enumerate} \item En utilisant la paire de clefs de l'exercice précédent, coder un message puis décoder ce message pour vérifier. \item Décoder le message authentifié situé à l'URL \\ \verb|https://www-fourier.univ-grenoble-alpes.fr/~parisse/mat249/rsa1| \end{enumerate} \end{exo} \begin{exo}[Attaque simple] On a vu que le codage monoalphab\'etique n'est pas une bonne id\'ee, une attaque possible \'etant la recherche de fr\'equences, ici on peut utiliser une attaque encore plus simple~: la personne souhaitant décoder un message codé avec une clef publique sans en connaitre la clef secrète calcule la liste des $a^c \pmod n$ pour les 256 valeurs possibles de $a$ et compare au message. Décoder de cette manière le message situé à l'URL\\ \verb|https://www-fourier.univ-grenoble-alpes.fr/~parisse/mat249/rsa2| \end{exo} \begin{exo}[Padding aléatoire] Pour parer à l'attaque précédente, on augmente le nombre de valeurs possibles de $a$ pour que le calcul de la liste de toutes les puissances possibles de $a$ soit trop long. Plusieurs strat\'egies sont possibles, l'une d'elle consiste \`a ajouter \`a $a$ un multiple al\'eatoire de 256. Comment la personne qui recoit un message crypt\'e retrouvera-t-elle le message en clair~? Impl\'ementer cette m\'ethode. \end{exo} \begin{exo}[Groupement de lettres] On peut aussi grouper par paquets de $x$ caractères et on associe à un groupe de caractères l'entier correspondant en base 256. Par exemple, si on prend des groupes de $x=3$ caractères, "ABC" devient \verb|65*256^2+66*256+67| car le code ASCII de A, B, C est respectivement 65, 66, 67. \begin{enumerate} \item Donner une condition reliant $n$ et $x$ pour que le décodage redonne le message original. \item Choisir une paire de clefs vérifiant cette condition pour $x=3$ (calculatrices avec entiers repr\'esent\'es par des flottants) ou $x=8$ (autres). \item \'Ecrire un programme de codage et de décodage avec groupement (on commencera par compléter le message original par des espaces pour qu'il soit un multiple de 8 caractères, en Xcas et Python). L'instruction \verb|len| permet de connaitre la taille d'une chaîne de caractères, (En Xcas, on pourra utiliser la fonction \verb|convert(.,base,256)|d'écriture en base 256). \end{enumerate} \end{exo} \begin{exo}[Sécurité du codage] \begin{enumerate} \item[] \item V\'erifier sur l'exemple de l'exercice 1.1 et du 2.2 que la connaissance de $\varphi(n)$ et de $n$ permet de calculer $p$ et $q$ par résolution d'une équation de degré 2. \item Si on connait seulement $c$ et $d$, peut-on retrouver $\varphi(n)$~? \item La sécurité du codage repose donc sur la difficulté de factoriser $n$. Tester sur des entiers de taille croissante le temps nécessaire au logiciel pour factoriser $p$ et $q$. Une valeur de $n$ de taille 128 bits, 512 bits, 1024 bits parait-elle suffisante? \end{enumerate} \end{exo} \begin{exo}[Sécurité du codage] Le choix de $c$ et de $d$ est aussi important. Pour le comprendre, prenons $p=11$ et $q=13$. \begin{enumerate} \item Représenter pour différentes valeurs de $c$ les points $(a,a^c \pmod n)$. Plus le dessin obtenu est aléatoire, plus il sera difficile à une personne mal intentionnée de déchiffrer un message sans connaitre la clef. (En Xcas, on pourra utiliser les instructions \verb|seq| pour générer une suite de terme général exprimée en fonction d'une variable formelle, et \verb|scatterplot(l)| qui représente le nuage de points donné par une liste \verb|l| de couples de coordonnées. En Python, on peut utiliser l'instruction \verb|plot| de \verb|matplotlib|). \item Observer en particulier les cas où $c$ n'est pas premier avec $\varphi(n)$ (comment voit-on que RSA ne fonctionne pas~?) et \'egalement le cas $c=3$. \end{enumerate} \end{exo} \begin{exo}[Attaque par les restes chinois] Une personne souhaite envoyer le m\^eme message $x$ \`a trois destinataires diff\'erents, ayant chacun leur propre clef publique $c=3,N_1$, $c=3,N_2$ et $c=3,N_3$ avec $c=3$ pour les 3 destinataires. Il envoie donc $y_1=x^3 \pmod {N_1}$, $y_2=x^3 \pmod{ N_2}$ et $y_3=x^3 \pmod{ N_3}$. Une personne mal intentionn\'ee arrive \`a intercepter $y_1, y_2$ et $y_3$. En appliquant les restes chinois, elle peut en d\'eduire $x$. Par exemple, retrouver $x$ sans chercher \`a factoriser les clefs pour \begin{verbatim} 46693373016 mod 180711261397, (-111575037168) mod 840724735099, (-18270191368) mod 372130013641 \end{verbatim} \end{exo} \begin{exo}[Attaque RSA] On suppose qu'on connait un couple de cl\'e secr\`ete/publique\\ \verb|96664445695884629095302836378328116675824715046626033| pour 65537 pour $n$ valant\\ \verb|1485368763791603971165032953281737852964691152265640113|\\ En d\'eduire la factorisation de $n$. \end{exo} \begin{exo}[Attaque RSA par fraction continue] Cette attaque fonctionne si la clef priv\'ee $d$ est petite et si $p$ et $q$ sont du m\^eme ordre de grandeur~: \[ q