TD 1

Q1, Q2.

La cryptologie est la science du secret. Elle se divise en deux disciplines :

• La cryptographie : l'étude des algorithmes (appelés cryptosystèmes) permettant de protéger de l'information.
• La cryptanalyse : l'étude du niveau de sécurité des cryptosystèmes fournis par les cryptographes.

Q3.

• La cryptographie consiste à coder des informations de manière à les rendre illisibles pour quiconque ne possède pas la clé pour les décrypter. L'objectif principal est de garantir la confidentialité, l'intégrité et l'authenticité des données.
• La stéganographie consiste à cacher l'existence même de l'information en l'intégrant dans un autre support. Contrairement à la cryptographie, l'objectif n'est pas de rendre le contenu illisible, mais de dissimuler qu'une communication existe.

Q4, Q5.

Alin Turing est le mathématicien qui a joué un rôle crucial dans le décryptage du code Enigma utilisé par les Allemands pendant la Seconde Guerre mondiale.

Q6.

La réponse est dans la Loi n° 2004-575 du 21 juin 2004 pour la confiance dans l'économie numérique.

TL;DR : L'utilisation des moyens cryptographies est libre en France, ainsi que le transfert de moyens de cryptographie assurant exclusivement des fonctions d'authentification ou de contrôle d'intégrité. Dans les autres cas, l'utilisation de moyens de cryptologie est soumise à déclaration ou autorisation préalable auprès du Premier ministre.

Rappels.

Pour cet exercice, je trouve plus clair de définir les notations suivantes, ce qui est le cas pour le groupe 3, mais pas pour le groupe 2 …

En bref, pour \(a, b\in\mathbb{Z}\), \(n\in\mathbb{Z}^{*}\),

• On définit \(a \mod n := \lbrace a + k n \mid k \in \mathbb{Z} \rbrace\).
  Par exemple, \(31 \mod 26 = \lbrace\ldots, -21, 5, 31, 57, 83, \ldots\rbrace\).
• On définit \(a \% n\) comme le reste de la division euclidienne de \(a\) par \(n\).
  Par convention, \(a \% n\) est le représentant canonique de \(a \mod n\).
  Par exemple, \(31 \% 26 = 5\), et \(-3 \% 26 = 23\).
• On note \(a = b \mod n\) si \(a \mod n = b \mod n\).
  Par exemple, \(5 = 31 \mod 26\), puisque \(5 \mod 26 = \lbrace\ldots, -47, -21, 5, 31, 57, \ldots\rbrace\).

Rappelons aussi que :

• Un nombre premier est un entier naturel qui admet exactment deux diviseurs disticts positifs, 1 et lui-même.
• Le pgcd (plus grand commun diviseur) de deux entiers naturels \(a\) et \(b\) est le plus grand entier naturel qui divise à la fois \(a\) et \(b\).

Q1, Q2, Q3.

Application directe des définitions.

Remarque.

Pour une analyse plus profonde de la relation entre les deux modulos, on définit les deux anneaux \((\mathbb{Z}/n\mathbb{Z}, +_{\textrm{mod }n}, \times_{\textrm{mod }n})\) et \((\lbrace 0, 1, \ldots, n-1 \rbrace, +_{\% n}, \times_{\% n})\), où

• \(\mathbb{Z}/n\mathbb{Z} := \lbrace m \mod n \mid m \in \mathbb{Z} \rbrace\), qui est fini et contient exactement \(n\) éléments, i.e., \(\mathbb{Z}/n\mathbb{Z} = \lbrace 0 \mod n, 1 \mod n, \ldots, n-1 \mod n \rbrace\).
• \(+_{\textrm{mod }n}\) est défini comme suit : pour tout \(a, b \in \mathbb{Z}\), \(a \mod n +_{\textrm{mod }n} b \mod n = (a + b) \mod n\).
• \(\times_{\textrm{mod }n}\) est défini comme suit : pour tout \(a, b \in \mathbb{Z}\), \(a \mod n \times_{\textrm{mod }n} b \mod n = (a \times b) \mod n\).
• \(+_{\% n}\) et \(\times_{\% n}\) sont les opérations usuelles de l'addition et de la multiplication modulo \(n\).
  Par exemple, \(5 +_{\% 12} 7 = (5 + 7) \% 12 = 0\), et \(5 \times_{\% 12} 7 = (5 \times 7) \% 12 = 11\).

Les deux anneaux sont isomorphes, car l'application \(\phi: \mathbb{Z}/n\mathbb{Z} \to \lbrace 0, 1, \ldots, n-1 \rbrace\) définie par \(\phi(a \mod n) := a \% n\) est un isomorphisme d'anneaux. En d'autres termes, \(\phi\) est une application bijective telle que

• \(\forall a, b \in \mathbb{Z}, \phi(a \mod n +_{\textrm{mod }n} b \mod n) = \phi(a \mod n) +_{\% n} \phi(b \mod n)\),
• \(\forall a, b \in \mathbb{Z}, \phi(a \mod n \times_{\textrm{mod }n} b \mod n) = \phi(a \mod n) \times_{\% n} \phi(b \mod n)\),
• \(\phi(1 \mod n) = 1 \% n\).

Qu'est-ce que cela signifie ? En bref, \((\mathbb{Z}/n\mathbb{Z}, +_{\textrm{mod }n}, \times_{\textrm{mod }n})\) et \((\lbrace 0, 1, \ldots, n-1 \rbrace, +_{\% n}, \times_{\% n})\) ont la même structure algébrique, permettant de traduire les propriétés de l'un à l'autre. Par exemple :

• \(\forall a, b \in \mathbb{Z}\), \(a \mod n = b \mod n\) si et seulement si \(a \% n = b \% n\).
• \(\forall a, b, c \in \lbrace 0, 1, \ldots, n-1 \rbrace\), \(a \times_{\% n} b = c\) si et seulement si \((a \mod n) \times_{\textrm{mod }n} (b \mod n) = c \mod n\).

Ainsi, on peut se concentrer sur \((\lbrace 0, 1, \ldots, n-1 \rbrace, +_{\% n}, \times_{\% n})\) pour les questions suivantes.

Q4.

Rappelons que j'ai dessiné la table de multiplication modulo 12 suivante :

La seule différence avec la table de multiplication usuelle est que les éléments sont remplacés par leur reste modulo 12. Par exemple, \(5 \times_{\% 12} 7 = (5 \times 7) \% 12 = 35 \% 12 = 11\). On met donc 11 dans la case correspondante.

Pour construire cette table, on peut bien sûr calculer tous les produits, puis modulo 12 ; cependant, quelques observations peuvent nous aider à simplifier le travail. Par exemple, pour la ligne 3, on voit que les éléments s'incrémentent de 3 modulo 12 régulièrement, et ne font que boucler lorsqu'ils atteignent 0. Il est donc un bon exercice de trouver la manière la plus efficace de construire cette table.

Q5, Q6, Q7.

• Pour l'addition, (0, 0), (1, 11), (2, 10), (3, 9), (4, 8), (5, 7), (6, 6), (7, 5), (8, 4), (9, 3), (10, 2), (11, 1) sont des couples d'éléments dont la somme est 0 modulo 12. On n'a pas besoin de la table pour voir cela …
• Pour la multiplication, on voit que (1, 1), (5, 5), (7, 7), (11, 11) sont des couples d'éléments dont le produit est 1 modulo 12. En fait, ce sont les seuls endroits dans la table où on trouve des 1.
• De plus, on voit que 2, 3, 4, 6, 8, 9, 10 sont des diviseurs de 0 modulo 12. En fait, ce sont les seuls lignes où on trouve des 0 hors de la colonne 0.

Q8.

• L'équation \(7x + 5 = 4 \mod 12\) est équivalente à \(7x = 11 \mod 12\), i.e., \(7 \times_{\% 12} (x \% 12) = 11\).
  Dans la ligne 7 de la table de multiplication modulo 12, on trouve que \(7 \times_{\% 12} 5 = 11\), donc \(x \% 12 = 5\), i.e., l'ensemble des solutions est \(5 \mod 12\).
• L'équation \(3x + 5 = 7 \mod 12\) est équivalente à \(3x = 2 \mod 12\), i.e., \(3 \times_{\% 12} (x \% 12) = 2\).
  Dans la ligne 3 de la table de multiplication modulo 12, il n'y a pas de \(a\in\lbrace 0,\ldots,n-1\rbrace\) tel que \(3 \times_{\% 12} a = 2\), donc il n'y a pas de solution.
  (Cependant, si on considère \(3x = 3 \mod 12\), on trouve que \(x \% 12 \in \lbrace 1,5,9 \rbrace\). Autrement dit, l'ensemble des solutions est \((1 \mod 12)\cup(5 \mod 12)\cup(9 \mod 12) = 1 \mod 4\).)

Rappels.

Un monoïde \((E, \cdot)\) est un ensemble \(E\) muni d'une loi de composition interne \(\cdot: E \times E \to E\) telle que :

• \(\forall a, b, c \in E, (a \cdot b) \cdot c = a \cdot (b \cdot c)\) (associativité),
• \(\exists e \in E, \forall a \in E, e \cdot a = a \cdot e = a\) (neutre).

Un groupe \((G, \cdot)\) est un monoïde \((G, \cdot)\) tel que :

• \(\forall a \in G, \exists a^{-1} \in G, a \cdot a^{-1} = a^{-1} \cdot a = e\) (inverse).

Un groupe abélien est un groupe \((G, \cdot)\) tel que :

• \(\forall a, b \in G, a \cdot b = b \cdot a\) (commutativité).

Un groupe \((G, \cdot)\) est dit monogène s'il existe un élément \(g \in G\) tel que \(G = \lbrace g^n \mid n \in \mathbb{N}^{*} \rbrace\), i.e., chaque élément \(a\in G\) s'écrit comme \(g^n:=g\cdot g\cdots g\) (où \(g\) apparaît \(n\) fois) pour un certain \(n\in\mathbb{N}^{*}\). Un tel élément \(g\) est appelé générateur de \(G\), et on dit que \(G\) est engendré par \(g\), noté \(G = \langle g \rangle\). En plus, si \(G\) est fini, on dit que \(G\) est un groupe cyclique.

Deux groupes \((G, \cdot)\) et \((H, \circ)\) sont dits isomorphes s'il existe une isomorphisme de groupes \(\phi: G \to H\), i.e., une bijection telle que :

• \(\forall a, b \in G, \phi(a \cdot b) = \phi(a) \circ \phi(b)\).

Par conséquent, on a \(\phi(e_G) = e_H\) et \(\forall a \in G\), \(\phi(a^{-1}) = \phi(a)^{-1}\).

Q1.

Il s'agit de questions du cours.

Q2.

On reprend la définition de \(\mathbb{Z}/n\mathbb{Z}\) et \(+_{\textrm{mod }n}\) de la remarque précédente. On observe que

• L'associativité : pour tout \(a, b, c \in \mathbb{Z}\), on a par définition

  \begin{align*} &(a \mod n +_{\textrm{mod }n} b \mod n) +_{\textrm{mod }n} c \mod n \\ = &((a + b) \mod n) +_{\textrm{mod }n} c \mod n \\ = &((a + b) + c) \mod n, \\ &a \mod n +_{\textrm{mod }n} (b \mod n +_{\textrm{mod }n} c \mod n) \\ = &a \mod n +_{\textrm{mod }n} ((b + c) \mod n) \\ = &(a + (b + c)) \mod n, \end{align*}

  dont l'égalité découle de l'associativité de l'addition dans \(\mathbb{Z}\).

• L'élément neutre est \(0 \mod n\).
• L'inverse de \(a \mod n\) est \(-a \mod n\).

Donc, \((\mathbb{Z}/n\mathbb{Z}, +_{\textrm{mod }n})\) est un groupe.

Q3.

Pour le groupe \((\mathbb{Z}/n\mathbb{Z}, +_{\textrm{mod }n})\), on sait déjà qu'il est fini ; en plus, chaque élément de la forme \(a \mod n\) s'écrit facilement comme une somme finie de \(1 \mod n\). Donc \((\mathbb{Z}/n\mathbb{Z}, +_{\textrm{mod }n})\) est cyclique.

Q4.

Soit \((G, \cdot)\) un groupe cyclique d'ordre \(n\), et soit \(g\) un générateur de \(G\), tel que \(G = \lbrace g^0, g^1, \ldots, g^{n-1} \rbrace\). Définissons \(\phi: \mathbb{Z}/n\mathbb{Z} \to G\) par \(\phi(k \mod n) = g^{k}\). On vérifie que :

• \(\phi\) est bien définie : pour la même entrée \(k \mod n = k^\prime \mod n\), on a \(k \% n = k^\prime \% n\), donc la même sortie \(g^{k} = g^{k\% n} = g^{k^\prime\% n} = g^{k^\prime}\).
• \(\phi\) est une bijection : elle renvoie \(0 \mod n\) à \(g^0\), puis \(1 \mod n\) à \(g^1\), …, puis \(n-1 \mod n\) à \(g^{n-1}\).

• \(\phi\) est un isomorphisme : \(\forall k,k^\prime\in\mathbb{Z}\),

  \begin{align*} \phi(k \mod n +_{\textrm{mod }n} k^\prime \mod n) = \phi((k + k^\prime) \mod n) = g^{k + k^\prime} = g^{k} \cdot g^{k^\prime} = \phi(k) \cdot \phi(k^\prime). \end{align*}

Donc \((\mathbb{Z}/n\mathbb{Z}, +_{\textrm{mod }n})\) et \((G, \cdot)\) sont isomorphes.

Q5.

Il s'agit de questions du cours.

Rappelons l'exemple de permutations non commutatives : prenons \(\sigma_1 : 1\to 2, 2\to 1, 3\to 3\) et \(\sigma_2 : 1\to 1, 2\to 3, 3\to 2\). On a \(\sigma_1 \circ \sigma_2 = 1\to 2, 2\to 3, 3\to 1\) et \(\sigma_2 \circ \sigma_1 = 1\to 3, 2\to 1, 3\to 2\), qui sont deux permutations distinctes.

Q1.

Le chiffrement mono-alphabétique est une méthode de chiffrement par substitution où chaque lettre du texte en clair est remplacée par un symbole unique dans le texte chiffré. Il s'agit donc, en mathématiques, d'une bijection entre deux alphabets finis de même taille. La clé secrète est, par convention, la chaîne de symboles en laquelle l'alphabet initial est transformé.

(On peut aussi dire que le chiffrement est un isomorphisme entre deux monoïdes libres (étoile de Kleene) générés par deux alphabets finis, si on s'intéresse plutôt aux mots.)

Q2.

Le chiffrement de César est un exemple de substitution mono-alphabétique où chaque lettre du texte en clair est décalée d'un certain nombre de positions dans le même alphabet. Il s'agit donc, en mathématique, une opération de décalage modulo la taille de l'alphabet. La clé secrète est ainsi uniquement déterminée par sa première symbole.

Q3.

Pour chiffrer le message ATTAQUESURLUTECEDEMAIN avec la clé R, la substitution est donnée par :

ABCDEFGHIJKLMNOPQRSTUVWXYZ
RSTUVWXYZABCDEFGHIJKLMNOPQ

Avec un peu de temps, on trouve le message chiffré RKKRHLVJLICLKVTVUVDRZE.

Pour déchiffrer le message IVIRYNPELCGBYBTVR avec la clé N, la substitution est donnée par :

ABCDEFGHIJKLMNOPQRSTUVWXYZ
NOPQRSTUVWXYZABCDEFGHIJKLM

Avec encore un peu de temps, on retrouve le message déchiffré VIVELACRYPTOLOGIE.

Q4.

On a 26 choix pour la clé du chiffrement de César, et 26! choix pour la clé du chiffrement mono-alphabétique.

Q5.

Une analyse de fréquence nous donne facilement l'emplacement de la lettre E dans le texte chiffré, qui est la lettre la plus fréquente en français. Pour le chiffrement de César, cela suffit pour trouver la clé. Pour le chiffrement mono-alphabétique, on continue l'analyse de fréquence pour trouver les autres lettres.