Ce cours prépare les étudiants aux UEs cryptographiques qui auront lieu par la suite. Ce cours présente:
- Des rappels sur les structures algébriques (lois de composition, groupes, anneaux, corps, sous-groupes, idéaux).
- Des rappels sur les relations d’équivalence et les structures quotients.
- Des rappels sur les polynômes.
Anneaux euclidiens. Divisibilité et irréductibilité dans Z et dans K[X].
Anneaux Z/nZ, corps Fp, anneaux Fp[X]/(P). Théorème chinois.
Algorithme d’Euclide, algorithme d’Euclide étendu, exponentiation rapide.
Il y a également des TPs ayant pour objet la mise en oeuvre des algorithmes essentiels intervenant dans le procédé RSA, dans la cryptographie elliptique ou dans le calcul de logarithmes discrets.
Cette UE apprend les compétences pour réussir l'examen-type suivant.
---> Pour chaque question, on explique le calcul cryptographique auquel elle s'applique.
======= Partie sur 8: concerne tout le monde ========================
*exercice 1/ Soit P=3.X^3 +2.X^2 mod 7 à coefficients obéissant aux lois de multiplication modulo 7.
Calculer le reste R de la division euclidienne de P par D=4.X^2 + 1
*exercice 2/ (même type de question)
---> La multiplication modulaire de polynômes est utilisée dans le standard AES-GCM (obligatoire dans TLS 1.3), dans le nouveau standard d'encryption post-quantique du NIST "ML-KEM",
et dans le circuit AES (MixColumns step)
======= Partie sur 12: utile seulement aux personnes ayant eu moins de 12 au partiel (le partiel à mi-parcours permet de sécuriser jusqu'à 12 points de la note finale, l'examen permet d'aller jusqu'à 20 et de rattraper le partiel)
*exercice 3/
(a) p=7, q=17, N=119 Combien y a-t-il de nombres x parmi [0,1,2,..., N-1] tels que x n’a pas d’inverse modulo N ?
(b) Calculer (-10)^98 modulo 119
----> (b) est le calcul utilisé pour la signature digitale RSA. La question (a) sert à répondre à la question (b) (par le théorème de Lagrange, cf ci-dessous).
*exercice 4/
(a) p=9 , q=9 , N=81 Combien y a-t-il de nombres x parmi [0,1,2,..., N-1] tels que x n’a pas d’inverse modulo N ?
(b) Calculer (-10)^57 modulo 81
Indice: utiliser le théorème de Lagrange pour (Z/NZ)*
----> Le théorème de Lagrange affirme que dans un groupe G, |G| fois un élément = l'élément neutre.
Il s'applique donc à tous les calculs de cryptographie à base de courbes elliptiques (Diffie-Hellman dans TLS 1.3 , signatures ECDSA et Schnorr)
*exercice 5/
Calculer l’inverse de 67 modulo 83
----> Tous les calculs de cryptographie sont dans un Z/NZ. On apprend donc à diviser dans Z/NZ, ce qui n'est pas la même chose que la division des nombres décimaux.
