Tris et Complexité

Option Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'Orsay

Le Groupe Symétrique

1  Introduction

1.1  À quoi sert la cryptographie?

1.2  Objectifs principaux de la cryptologie

1. Cryptographie:
   1. Authentification
   2. Chiffrement
   3. Signature
   4. Tatouage
2. Cryptanalyse

1.3  Exemples de protocoles cryptographiques

1.3.1  Chiffrement symmétrique

1. Permutation d'alphabet, César et ROT13
2. Enigma
   
   Exercice 1   On considère une mini machine Enigma pour l'alphabet {E,I,L,N,S,T} disposant de deux rotors à choisir parmi trois et du réflecteur représentés ci-dessous. Pour des questions pratiques, les sommets de l'hexagone extérieur représentent les six contacts de la face droite du rotor, et les sommets de l'hexagone intérieur ceux de la face gauche:
   
   
   
   Plus précisément:

   1. La rotation d'un rotor est décrite par sa lettre la plus à droite.
   2. Les six contacts sont décrits par les lettres E,I,L,N,S,T de sorte que les labels coïncident avec ceux des rotors lorsque ces derniers sont en position E (comme dans la figure).
   3. Le rotor en position 1 tourne d'un cran dans le sens trigonométrique après chaque appui de touche;
   4. Le rotor en position 2 tourne d'un cran dans le sens trigonométrique après chaque passage du rotor en position 1 de la lettre I à la lettre E;
   5. Le réflecteur est fixé sur la lettre E;
   6. Le courant passe successivement de la droite vers la gauche à travers le rotor en position 1, le rotor en position 2, rebondit via le réflecteur puis repasse en sens inverse à travers les deux rotors.

   Par exemple, avec le rotor II en position 1 sur la lettre N, et le rotor III en position 2 sur la lettre I, vérifiez que le courant rentrant par le contact I est envoyé successivement sur les contacts S, T, N, L, puis T. Autrement dit, la lettre I est chiffrée par T. Vérifiez que réciproquement la lettreT est chiffrée par I.
   
   Décoder le message IENILILESNI avec le rotor I en position 1, le rotor III en position 2, respectivement sur les lettres T et N au départ.
   
   Modéliser mathématiquement la substitution d'alphabet appliquée à chaque étape par la machine Enigma.
3. Masque jetable

1.3.2  Chiffrement assymétrique

1. El-Gammal
   
   Log discret et courbes elliptiques http://fr.wikipedia.org/wiki/Courbe_elliptique#La_loi_de_groupe.2C_description_g.C3.A9om.C3.A9trique

1.4  Partage de secret à zéro information a priori

1. Valise à double serrure
2. Diffie-Hellmann

1.4.1  Secret partagé

1.5  Sécurité des protocoles cryptographiques et complexité des algorithmes

2  TP: Implantation simple et usage de RSA

2.1  Échauffements

2.2  Implantation de RSA

2.3  Expérimentation: échange de données confidentielles par dessus un media non sûr

1. Chaque message envoyé de manière sûre donne un point à l'expéditeur et au destinataire;
2. Chaque message intercepté et déchiffré par une tierce personne lui donne trois points;
3. Celui qui marque le plus grand nombre de points a gagné.

2.4  Applications de RSA

2.5  Préparation à l'oral d'agrégation

Références

[1]

www.wikipedia.org, et en particulier les articles sur Enigma http://en.wikipedia.org/wiki/Enigma_machine

[2]

Modern Computer Algebra, chapitre 12

Tris et Complexité

Option Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'Orsay

Le Groupe Symétrique