TD 4

Cette semaine, nous avons fait une séance de révision, en traitant les exercices des annales dans la feuille de TD. Cependant, je doute que faire des annales d'il y a dix ans vous aidera à préparer le partiel de 2025 ; j'ai donc distribué les exercices supplémentaires.

Si vous n'êtes pas présent au TD, vous pouvez venir à mon bureau (26-00/315) pour récupérer les feuilles d'exercices supplémentaires ; envoyez-moi un mail avant de venir afin que je puisse confirmer ma présence.

Exercice 12 - Cryptanalyse de Vigenère par mot probable

(Partiel 2012 - Exercice 2)

Q2.

Sachant que les partiels ont toujours lieu le mercredi, hier se traduit par MARDI, et YURGQ - MARDI = MUADI, donc la clé est MUADI de longueur 5. Le texte clair est donc :

  YURGQ ZOAJM EYTDD QLSHA MNTDY GYSXZ XCLHX MLLHA F
- MUADI MUADI MUADI MUADI MUADI MUADI MUADI MUADI M
= MARDI NUAGE SETAV ERSES ATTAQ UESUR LILEP ARLES T

Q1.

Si on connaît le mot probable, et en plus sa position dans le texte, on peut retrouver une portion de la clé en faisant la différence entre le mot probable et le texte chiffré. En particulier, si le mot probable est plus long que la clé, on peut retrouver la clé en entier comme une partie répétée de la différence.

Exercice 13 - Sur le chiffrement de Vigenère et le problème d'échange de clé

(Partiel 2013 - Exercice 2)

Q1.

On a \(e_{K_1}\circ e_{K_2} = e_{(K_1+K_2)\% 26}\). Ici, j'abuse un peu de la notation :

\begin{equation*} (K_1+K_2)\% 26:=(K_{1,1}+K_{2,1})\% 26,\ldots,(K_{1,\ell}+K_{2,\ell})\% 26. \end{equation*}

Si ceci n'est pas clair, on peut aussi faire le calcul : soit \(m\) un texte clair de longueur \(\ell\), on a

\begin{align*} (e_{K_1}\circ e_{K_2})(m) &= e_{K_1}(e_{K_2}(m)) \\ &= e_{K_1}((m+K_2) \% 26) \\ &= ((m+K_2) \% 26 + K_1) \% 26 \\ &= (m + (K_1+K_2) \% 26) \% 26 \\ &= e_{(K_1+K_2)\% 26}(m). \end{align*}

Q2.

D'après Q1, \(\circ\) est une loi interne sur \(\mathcal{V}_{\ell}\). Vérifions les autres propriétés :

Associativité : claire, car l'addition modulo 26 est associative (faites le calcul pour vous en convaincre).
Existence d'un élément neutre : \(e_{A\ldots A}\) est l'élément neutre, car \(e_{A\ldots A}(m)=m\) pour tout texte clair \(m\).
Existence d'inverses : \(e_{K_1}\) est inversible, et son inverse est \(e_{-K_1\% 26}\).

Donc \((\mathcal{V}_{\ell},\circ)\) est un groupe. Il est même abélien, car l'addition modulo 26 est commutative.

Q3.

Rappelons que \(s_2 = (e_{K_2}\circ e_{K_1})(K)\), et que Bob n'a l'accès qu'à \(K_2\). Alice doit donc éliminer \(K_1\) de \(s_2\) pour que Bob puisse retrouver \(K\). Pour cela, elle envoie à Bob \(s_3 = e_{-K_1\% 26}(s_2)\), qui vaut

\begin{equation*} s_3 = e_{-K_1\% 26}(s_2) = (e_{K_1}^{-1}\circ e_{K_2}\circ e_{K_1})(K) = e_{K_2}(K). \end{equation*}

Ainsi, Bob peut retrouver \(K\) en déchiffrant \(s_3\) avec \(K_2\).

Q4.

Si un attaquant intercepte \(s_1\) et \(s_2\), il peut retrouver \(K_2 = e_{s_1}^{-1}(s_2)\), et donc déchiffrer \(K\) de la même manière que Bob.

Q5.

Il faut que la connaissance d'une couple clair/chiffré ne permette pas de retrouver la clé.

Q6.

Non, car one-time pad n'est rien d'autre que le chiffrement de Vigenère avec une clé de longueur égale à celle du texte clair.

Q7.

Sous l'hypothèse de Q5, il suffit de remplacer \(K\) par le message, Alice par l'indicateur, et Bob par l'agent de police. Je vous laisse recopier les étapes dans l'énoncé.

Exercice A - Algèbre et arithmétique

(Partiel 2024 - Exercice 2)

Exercice B - Questions diverses

(Partiel 2023 (sujet 1) - Exercice 1)

Q2.

Pour la définition d'un élément inversible et d'un diviseur de 0, voir Feuille 1, Exo 14, Q1.

Pour la preuve demandée dans la deuxième question, voir Feuille 1, Exo 17, Q1.

Pour les exemples d'anneaux, on a :

\(\mathbb{Z}\) et \(\mathbb{Z}/p\mathbb{Z}\) (avec \(p\) premier) ne contiennent pas de diviseur de 0.
\(\mathbb{Z}/n\mathbb{Z}\) (avec \(n\geq 2\) entier) ne contiennent que 0, des diviseurs de 0 et des éléments inversibles.
\(\mathbb{Z}\) contient des éléments autres que \(0\), des diviseurs de \(0\) et des éléments inversibles.

Q3.

Par le théorème de Lagrange, l'ordre d"un élément du groupe divise l'ordre du groupe, qui est \(p^2\) dans ce cas. Donc l'ordre d'un élément peut être \(1\), \(p\) ou \(p^2\). Notons que dans \(\mathbb{Z}/p^2\mathbb{Z}\), on a \(\omega(1\mod p^2)=p^2\), \(\omega(p\mod p^2)=p\) et \(\omega(p^2\mod p^2)=1\).

Q4.

Par le petit théorème de Fermat, on a \(12^{16} = 1 \mod 17\), donc

\begin{equation*} 12^{27} \mod 17 = 12^{16} \cdot 12^{11} \mod 17 = 12^{11} \mod 17. \end{equation*}

Ensuite, on observe que

\(12^2 = 144 = 8 \mod 17\),
\(12^4 = 64 \mod 17 = 13 \mod 17\),
\(12^8 = 169 \mod 17 = -1 \mod 17\).

Donc

\begin{align*} 12^{11} \mod 17 &= -12^{3} \mod 17 \\ &= -12 \cdot 12^2 \mod 17 = -12 \cdot 8 \mod 17 = 6 \mod 17. \end{align*}

Q5.

Si vous avez les tables de multiplication 12x12 par coeur, je pense que la manière la plus efficace est de tout calculer.

Notons \(P(x) = x^2+3x+4\), on a

	0	1	2	3	4	5	6	7	8	9	10	11	12
\(P(x)\)	4	8	14	22	32	44	58	74	92	112	134	158	184
\(P(x) \% 6\)	4	2	2	4	2	2
\(P(x) \% 7\)	4	1	0	1	4	2	2
\(P(x) \% 11\)	4	8	3	0	10	0	3	8	4	2	2
\(P(x) \% 13\)	4	8	1	9	6	5	6	9	1	8	4	2	2

Donc \(P(x)=0\) n'a pas de solution dans \(\mathbb{Z}/6\mathbb{Z}\) ou \(\mathbb{Z}/13\mathbb{Z}\), a une seule solution \(2 \mod 7\) dans \(\mathbb{Z}/7\mathbb{Z}\), et a deux solutions \(\lbrace 3 \mod 11, 5 \mod 11\rbrace\) dans \(\mathbb{Z}/11\mathbb{Z}\).

Q6.

Pour déterminer le PGCD de \(7^{100k}-1\) et \(303=3\times 101\), on vérifie que

\begin{align*} (7^{100k} - 1) \% 3 &= ((7 \% 3)^{100k} - 1) \% 3 = (1^{100k} - 1) \mod 3 = 0. \\ (7^{100k} - 1) \% 101 &= ((7^{100})^{k} - 1) \% 101 = (1^{k} - 1) \mod 101 = 0. \end{align*}

Donc \(\gcd(7^{100k}-1, 303) = 3 \times 101 = 303\).

Exercice C - Arithmétique et algèbre

(Partiel 2023 (sujet 2) - Exercice 3)

Exercice D - Divisibilité et PGCD

(Partiel 2022 - Exercice 4)

Q1, Q2.

Soit \(q\), \(r\) les entiers tels que \(b = aq + r\) avec \(0 \leq r < a\). On a

\begin{align*} n^{b}-1 &= n^{aq+r}-1 \mod (n^{a}-1) \\ &= (n^{a})^{q}n^{r}-1 \mod (n^{a}-1) \\ &= 1^{q}n^{r}-1 \mod (n^{a}-1) \\ &= n^{r}-1 \mod (n^{a}-1), \end{align*}

où \(0 \leq n^{r}-1 < n^{a}-1\).

Donc, le reste de la division euclidienne de \(n^{b}-1\) par \(n^{a}-1\) est \(n^{r}-1\), et donc \(0\) si \(r=0\).

Q3.

Si on lance l'algorithme d'Euclide simultanément sur les entrées

\(r_0 = n^{b}-1\), \(r_1 = n^{a}-1\),
\(r^{\prime}_0 = b\), \(r^{\prime}_1 = a\),

on obtient deux suites \((r_i)\) et \((r^{\prime}_i)\) telles que \(r_i = n^{r^{\prime}_i}-1\) (ce qui se démontre facilement par récurrence). Ainsi, à la fin de l'algorithme, on a \(\gcd(n^{b}-1, n^{a}-1) = n^{\gcd(a,b)}-1\).

Q4.

(a) D'après Q1, \(n-1\) est un facteur non trivial de \(n^{b}-1\).
(b) D'après Q1, soit \(a\) un facteur non trivial de \(b\), on a \(2^{a}-1\) un facteur non trivial de \(2^{b}-1\).
(c) Il faut donc que \(n=2\) et \(b\) soit premier.