TD 3

Rappels.

Soit \((G, \circ)\) un groupe fini, et \(H\) un sous-groupe de \((G, \circ)\). Alors \(H\) est un groupe fini, et \(|H|\) divise \(|G|\). (Lagrange)

Q6.

Soit \((G, \circ)\) un groupe d'ordre \(p\), avec \(p\) un nombre premier. Comme \(p\geq 2\), il existe un élément \(a \in G\) différent de l'élément neutre, et donc \(\omega(a) \geq 2\). Considérons le groupe cyclique \(H = \langle a \rangle\) engendré par \(a\). Alors \(H\) est un sous-groupe de \((G, \circ)\), et \(|H| = \omega(a)\) divise \(|G| = p\), donc \(|H| = p\). Ainsi, \(H = G\), et donc \(G\) est cyclique.

Q7.

On a déjà \(\langle [\frac{n}{d}]g\rangle\) comme sous-groupe de \(G\) d'ordre \(d\), où \(g\) est un générateur de \(G\). Montrons que si \(H\) est un sous-groupe de \(G\) d'ordre \(d\), alors \(H = \langle [\frac{n}{d}]g\rangle\). Bien sûr, il suffit de montrer que \(H\subset \langle [\frac{n}{d}]g\rangle\).

Soit \(a \in H\) un élément quelconque. Comme \(g\) engendre \(G\), il existe un entier \(k\) tel que \(a = [k]g\). D'après Q4, on a \(\omega(a) = \omega([k]g) = \frac{\omega(g)}{\gcd(\omega(g), k)} = \frac{n}{\gcd(n, k)}\). Or, \(\omega(a) = |\langle a \rangle| \subset H\), donc par le théorème de Lagrange, on a \(\frac{n}{\gcd(n, k)} = \omega(a) \mid |H| = d\). Ainsi, \(\frac{n}{d} \mid \gcd(n,k) \mid k\), et donc \(a = [k]g \in \langle [\frac{n}{d}]g\rangle\). Comme \(a\) est arbitraire, on a \(H \subset \langle [\frac{n}{d}]g\rangle\), et donc \(H = \langle [\frac{n}{d}]g\rangle\).

Q1.

Si \(a\) est inversible, il ne peut pas être un diviseur de \(0\). La preuve est similaire à celle de l'exercice 14, Q1. En bref, si \(a\) est inversible, et \(b \in \mathbb{Z}/n\mathbb{Z}^{\times}\) est tel que \(ab = 0\), alors \(b = (a^{-1} a) b = a^{-1} (a b) = 0\), donc \(b = 0\), ce qui est absurde.

Maintenant, si \(a\) est diviseur de \(0\), l'exercice 16, Q4 nous donne la formule pour calculer \(b \in \mathbb{Z}/n\mathbb{Z}\) tel que \(ab = 0\), à savoir \(b = \frac{n}{\gcd(n, a)}\). Bien sûr, \(b\) peut être obtenu avec l'algorithme d'Euclide étendu.

Q2.

Pour déterminer le pgcd et la relation de Bézout entre \(a\) et \(b\), on va faire au plus \(\lfloor \log_{\phi} \min(a, b) \rfloor\) boucles, et au plus \(\mathcal{O}(\log(a) \log(b))\) opérations élémentaires.

Pour les calculs intermédiaires, rappelons que

• \(u_0 = 1\), \(u_1 = 0\), \(u_{i+1} = u_{i-1} - q_i u_i\) pour \(i \geq 1\).
• \(v_0 = 0\), \(v_1 = 1\), \(v_{i+1} = v_{i-1} - q_i v_i\) pour \(i \geq 1\).
• \(r_0 = a\), \(r_1 = b\), \(r_{i+1} = r_{i-1} - q_i r_i\) pour \(i \geq 1\).
• \(q_i = \lfloor \frac{r_{i-1}}{r_i} \rfloor\) pour \(i \geq 1\), si \(r_i \neq 0\), et arrêt sinon.

Donc, pour \(a = 5005\) et \(b = 1014\), on a le tableau suivant. Je vous invite à refaire les calculs sur papier pour vous entraîner.

L'invariant de boucle est \(r_i = a u_i + b v_i\) pour \(i \geq 0\). Donc, pour la ligne 5, on a \(13 = 5005 \times 31 + 1014 \times (-153)\) (Bézout).

Q3.

Pour la ligne 6, l'invariant de boucle nous donne \(0 = 5005 \times (-78) + 1014 \times 385\). En d'autres termes, \(1014 \times 385\) est un multiple de \(5005\), et donc 0 modulo 5005. Par définition, 1014 est un diviseur de zéro dans \(\mathbb{Z}/5005\mathbb{Z}\), et \(b = 385 \mod 5005\) est tel que \(1014 b = 0 \mod 5005\).

Q4.

Il suffit d'appliquer l'algorithme d'Euclide étendu pour \(n\) et cet entier, disant \(a\). La complexité est donc \(\mathcal{O}(\log(n) \log(a))\), qui est dans \(\mathcal{O}(\log^2(n))\).

D'après le tableau des indices de coïncidence mutuelle, on a

On a en effet les trois premières équations, qui déduisent en fait les trois dernières (comme le système est cohérent). Ainsi, on peut aligner le texte avec ces différences de décalage pour obtenir un texte chiffré avec César avec \(d_0\).

WXHYJSVBTC IIDASWXBIW PIADCVGDBP CIXREDTBHS TETCSBDGTJ EDCXCRXSTC
IIWPCXCHEX GPIXDCPCSI WPIIDJIITG IWTEDTIGND UGDBPCRTAN GXRHLDJASH
JUUXRTWTCR TWXHIWTDGN RATPGANUXI ITSIDWXHDL CAXBXIPIXD CHIWPIPADC
VEDTBXHPUA PIRDCIGPSX RIXDCXCITG BHIWTRDBED CTCIHDUIWT GPKTCPGTUT
LPCSHXBEAT PBPCPQXGSP CSIWTEWPCI PHBPABTBDG NPIPLDBPC

Par une analyse de fréquence, et après plusieurs essais, on a \(d_0 = 15\), donc le texte clair est

HISJUDGMEN TTOLDHIMTH ATLONGROMA NTICPOEMSD EPENDMOREU PONINCIDEN
TTHANINSPI RATIONANDT HATTOUTTER THEPOETRYO FROMANCELY RICSWOULDS
UFFICEHENC EHISTHEORY CLEARLYFIT TEDTOHISOW NLIMITATIO NSTHATALON
GPOEMISAFL ATCONTRADI CTIONINTER MSTHECOMPO NENTSOFTHE RAVENAREFE
WANDSIMPLE AMANABIRDA NDTHEPHANT ASMALMEMOR YATAWOMAN

Q1.

Pour un texte de longueur \(n\) et une clé de longueur \(l\), la longueur du texte chiffré est \(l \lceil \frac{2n}{l} \rceil\).

Q2.

Commençons par encodage par caractère avec padding à la fin.

a t t  a q u  e s u  r p a  r i s  l e 1  2 j a  n v i  e r
FFDFDF FFGGVF VDFXVF XDGAFF XDFAFX VGVDAD FGAXFF XVXAFA VDXDXX

ce qui nous donne le tableau

FFDFDF
FFGGVF
VDFXVF
XDGAFF
XDFAFX
VGVDAD
FGAXFF
XVXAFA
VDXDXX

Ensuite, on permute les colonnes selon la transposition [2, 1, 4, 6, 3, 5]. Pour ce faire, on recopie d'abord la colonne 2, puis 1, puis 4, puis 6, puis 3, puis 5.

FFFFDD
FFGFGV
DVXFFV
DXAFGF
DXAXFF
GVDDVA
GFXFAF
VXAAXF
DVDXXX

À la fin, on lit le texte chiffré par colonne.

FFDDDGGVD FFVXXVFXV FGXAADXAD FFFFXDFAX DGFGFVAXX DVVFFAFFX

Q3.

Commençons par mettre le texte chiffré dans un tableau, colonne par colonne. Comme il y a 48 caractères, et on doit avoir 6 colonnes, chaque colonne a 8 caractères.

GFVFDF
FFDGGF
FDVXVV
FDVGFA
VFXAGF
FXFDVF
FGVAFV
DFVXXV

Ensuite, on permute les colonnes selon la permutation [3, 1, 6, 2, 5, 4].

VGFFDF
DFFFGG
VFVDVX
VFADFG
XVFFGA
FFFXVD
VFVGFA
VDVFXX

Puis, en lisant ligne par ligne, on obtient le texte clair après la substitution.

VGFFDF DFFFGG VFVDVX VFADFG XVFFGA FFFXVD VFVGFA VDVFXX
l a t  t a q  u e d  u 1 2  n a p  a s e  u l i  e u 9

Q1.

Pour la définition de \(A=\mathbb{Z}/7\mathbb{Z}\) et les tables d'addition et de multiplication, voir l'exercice 2.

Comme 7 est un nombre premier, \(A\) est un corps, et donc un anneau intègre (sans diviseurs de zéro). Bien sûr, les propriétés se voient aussi dans la table de multiplication.

Cependant, \(26 = 2\times 13\), donc \(2 \mod 26\) est un diviseur de zéro dans \(\mathbb{Z}/26\mathbb{Z}\), et donc \(\mathbb{Z}/26\mathbb{Z}\) n'est pas un anneau intègre (ni un corps).

Q2.

Rappelons que le chiffrement affine est donné par

• \(\mathcal{P} = \mathcal{C} = A\),
• \(\mathcal{K} = A^{\times} \times A\),
• \(\forall (a,b)\in K\), \(e_{(a,b)}(x) = ax + b\), \(d_{(a,b)}(y) = a^{-1}(y-b)\).

La différence principale est que \(A^{\times} = A \setminus \{0\}\) pour \(A=\mathbb{Z}/7\mathbb{Z}\), alors que le groupe d'unités de \(\mathbb{Z}/26\mathbb{Z}\) est représenté par \(\{1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25\}\), qui est sans doute plus difficile à énumérer.

Q3.

Dans le cas du chiffrement de Hill, on a

• \(\mathcal{P} = \mathcal{C} = A^2\),
• \(\mathcal{K} = \operatorname{GL}_2(A) := \{K\in \mathcal{M}_2(A) \mid K \text{ inversible}\}\),
• \(\forall K\in K\), \(e_{K}(x) = Kx\), \(d_{K}(y) = K^{-1}y\).

Q4.

Pour montrer que \((\mathcal{M}_2(A),+,\times)\) forme un anneau, il suffit de vérifier que

• \((\mathcal{M}_2(A),+)\) est un groupe abélien. Ceci est clair, car l'addition dans \(\mathcal{M}_2(A)\) est par élément, et \((A,+)\) est un groupe abélien.
• \((\mathcal{M}_2(A),\times)\) est un monoïde. L'élément neutre est clairement la matrice identité \(I_2\). L'associativité est un exercice de calcul matriciel.
• La distributivité de \(\times\) par rapport à \(+\). C'est aussi un exercice de calcul matriciel.

Q5.

Il faut vérifier que \(AB = BA = I_2\) lorsque \(\det(A)\) est inversible, qui est encore un exercice de calcul matriciel.

D'ailleurs, si \(\det(A) = 0\), on peut vérifier que pour \(B=\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}\), \(AB = BA = 0\), et donc \(A\) n'est pas inversible.

Q6.

D'après Q5, une matrice \(K\in \mathcal{M}_2(A)\) est inversible si et seulement si \(\det(K)\) est inversible dans \(A\). Donc, on a en effet

• \(\mathcal{K} = \{K\in \mathcal{M}_2(A) \mid \det(K) \in A^{\times}\}\).

Pour un exemple de chiffrement et déchiffrement, prenons \(A=\begin{pmatrix} 2 & 3 \\ 1 & 2 \end{pmatrix}\), et chiffrons le texte clair 12 34 56 : on a

donc le texte chiffré est 15 44 03.

Q2, Q3.

Il suffit d'avoir \(m\) couples clair/chiffré pour déterminer \(K\).

Par exemple, dans Q3, on a FRIDAY = 5 17 8 3 0 24, et PQCFKU = 15 16 2 5 10 20, et donc en prenant les deux premiers couples,

Comme on sait comment inverser une matrice d'après l'exercice 10, Q5, on peut déterminer \(K\), qui est

On vérifie facilement que \(K \begin{pmatrix} 0 \\ 24 \end{pmatrix} = \begin{pmatrix} 10 \\ 20 \end{pmatrix} \mod 26\).

Q1.

Dans cet exercice, la cryptanalyse demande d'avoir plusieurs couple clair/chiffré en utilisant le cryptosystème en boîte noire. On peut bien sûr faire d'autres hypothèses, par exemple avoir moins de couples, ou avoir un nombre d'accès limité à la boîte noire.