Télécharger au format pdf
fiche
Cours
\({\mathbb{Z}}/n{\mathbb{Z}}\)
Soit \(n \in {\mathbb{N}}\) \(a\) inversible dans \({\mathbb{Z}}/n{\mathbb{Z}}\) ssi \(\text{pgcd}(a,n) = 1\) \(\Rightarrow\) \({\mathbb{Z}}/p{\mathbb{Z}}\) est un
corps
\(a\) diviseur de 0 dans \({\mathbb{Z}}/n{\mathbb{Z}}\) ssi \(\text{pgcd}(a,n) \neq 1\)
Algorithme d’Euclide étendu
Cf tableaux de con dans les TD Le déroulé de l’algorithme donne si existant l’inverse et le diviseur de 0
Formules:
\[\begin{array}{r}
u_{i} = u_{i - 2} - q_{i} \times u_{i - 1} \\
v_{i} = v_{i - 2} - q_{i} \times v_{i - 1}
\end{array}\]
Indice de coincidence
avec \(n_{i}\) le nombre
d’occurrences de la lettre d’indice \(i\) dans le texte \[\text{ IC } = \sum_{i = 0}^{25}\frac{n_{i}\left(
n_{i} - 1 \right)}{n(n - 1)}\]
\(\text{IC}\left( \text{fr} \right) \approx
0.074\)
Indice de coincidence mutuelle
\[\text{ ICM } = \sum_{i = 0}^{25}\frac{m_{i}n_{i}}{nm}\]
Corrélation de Pearson
\[\rho_{X,Y} = \frac{\sum_{i}\left( X_{i} - \overline{X} \right)\left( Y_{i} - \overline{Y} \right)}{\sqrt{\sum_{i}\left( X_{i} - \overline{X} \right)^{2}}\sqrt{\sum_{i}\left( X_{i} - \overline{X} \right)^{2}}}\]
Chiffrement parfait
\(\mathcal{P}\) et \(\mathcal{K}\) les alphabets clairs et
chiffrés.
\(\mathcal{K}\) l’ensemble des clefs
possibles.
\(K \in \mathcal{K}:e_{K}:P \rightarrow
C\text{ et }d_{K}:C \rightarrow P\text{ avec }\forall x \in
\mathcal{P},d_{K}\left( e_{K}(x) \right) = x.\)
Les applications \(e_{K}\) et \(d_{K}\) nécessitent la connaissance
complète de \(K\) pour être
définies.
Supposons qu’un cryptosystème vérifie \(|\mathcal{K}| = |\mathcal{P}| =
|\mathcal{C}|\).
Alors il sera un chiffrement parfait ssi on a
Toutes les clefs sont utilisées avec la même probabilité
Pour tout couple \((m,c) \in \mathcal{P} \times \mathcal{C}\) il existe une unique clef \(k\) telle que \(e_{k}(m) = c\).
Méthodes
Algorithme d’euclide
pgcd(a,b) \(\begin{array}{r} a = b \times m_{1} + r_{1} \\ b = r_{1} \times m_{2} + r_{2} \\ \ldots \\ r_{n} = 0 \\ \text{alors }\text{ pgcd}(a,b) = r_{n - 1} \end{array}\)
Formule rapide pour l’ordre
\(\text{ord}(a) = \frac{n}{\text{ pgcd}(a,n)}\)
\(E^{\times} =\) ensemble des éléments inversibles
RSA
Principe
Chiffrement asymétrique. Soit \(p,q\) deux nombres premiers. \(n = pq\). On choisit \(e,d \in {\mathbb{Z}}/n{\mathbb{Z}}\) tels que \(ed = 1\operatorname{mod}\varphi(n)\). On a \(\varphi(n) = \varphi(q)\varphi(q) = (p - 1)(q - 1)\)
Clé publique: \((n,e)\) Clé privée: \(d\)
Bob peut chiffrer un message \(m \in {{\mathbb{Z}}/n{\mathbb{Z}}}^{\times}\) avec \(f:m \rightarrow m^{e}\operatorname{mod}n\)
Alice peut déchiffrer un message \(c \in {{\mathbb{Z}}/n{\mathbb{Z}}}^{\times}\) avec \(f:c \rightarrow c^{d}\operatorname{mod}n\)
Th des restes chinois
Soit p et q premiers entre eux. Alors Z/pqZ est isomorphe à Z/pZ times Z/qZ
Page incomplète ou erronée? Contribuez sur le repo