7.4. Cryptographie¶

Exercice 1: Cryptographie conventionnelle

Dans un interpréteur Python créez la chaîne de caractères message contenant la valeur ‘ceci est mon message a chiffrer’. A l’aide d’une boucle for sur cette chaîne, chiffrer la par un décalage de 3 (chiffre de César). Par exemple la lettre a sera chiffrée en la lettre d (et la lettre x en la lettre a).
Écrire un script Python qui chiffre (ou déchiffre selon le choix de l’utilisateur) une chaîne de caractères entrée au clavier avec une clé (i.e.un décalage) choisi aussi par l’utilisateur. On définira les fonctions chiffrer et dechiffrer.
Modifier le script précédent pour qu’il utilise la méthode de chiffrement de Vigenère : la clé est désormais une chaîne de caractères et le chiffrement se fait en décalant la i-ème lettre du message gràce à la i-ème lettre de la clé (on reprend au début de la clef quand on a fini de lire celle-ci) suivant la règle naturelle A=1,B=2,...,Z=26.
Modifier le script précédent pour qu’il chiffre/déchiffre un fichier dont le chemin est entré par l’utilisateur. On pourra utiliser cette nouvelle de Edgar Poe pour tester le script.

Exercice 2: Cryptanalyse fréquentielle

Comme expliqué dans la nouvelle de E. Poe, les chiffrements par substitution alphabétique peuvent être casser facilement par une analyse fréquentielle. Par exemple, dans un texte écrit en langue française, la lettre la plus fréquente est généralement le “E” et puisqu’un chiffrement de César ne modifie pas les fréquences, la lettre qui apparaît le plus fréquemment dans le texte chiffré correspond vraisemblablement à “E” et si c’est le cas le décalage entre les deux lettres donne la clé et permet de retrouver l’intégralité du message clair.

Écrire une fonction Python qui prenant en entrée une chaîne de caractères (ou un fichier texte) affiche la fréquence des caractères qui le composent.
Utiliser cette fonction pour créer une fonction qui prend un entrée un texte chiffré avec le chiffrement de César (mais pas la clé) et retourne un texte clair associé. On pourra demander à l’utilisateur de valider que ce texte est correct (et si ce n’est pas le cas proposer un nouveau texte clair probable).
L’encyclopédie Wikipedia propose un article expliquant une méthode de cryptanalyse du chiffrement de Vigenère reposant sur les mêmes principes. Écrire une fonction Python qui prend un entrée un texte chiffré avec le chiffrement de Vigenère (mais pas la clé) et retourne un texte clair associé possible.

Exercice 3: Cryptographie à clé publique basée sur les courbes elliptiques

En mathématiques, une courbe elliptique est une courbe algébrique définie sur un corps $\mathbb{K}$ , unie entre autres propriétés, d’une loi de groupe définie sur l’ensemble de ses points.

Si la caractéristique du corps est différente de 2 et 3, une courbe elliptique est donnée par l’équation de Weierstrass $y^2=x^3+ax+b$ , où $a$ et $b$ sont des éléments du corps $\mathbb{K}$ vérifiant $4a^3+27b^2 \neq 0$ .

Nous considérons l’ensemble des points de la courbe

$\{(x,y) \in \mathbb{K}^2 \vert y^2=x^3+ax+b \} \cup \{ \mathcal{O} \}$

où $\mathcal{O}$ est un point sur la droite à l’infini (dans le plan projectif correspondant). Ce point représente l’élément neutre pour la loi d’addition de la courbe.

L’usage des courbes elliptiques en cryptographie a été proposé en 1986, indépendamment par Neal Koblitz et Victor Miller, pour l’instanciation des opérations cryptographiques asymétriques, comme l’échange de clé entre deux personnes sur un canal non-sécurisé. Par rapport aux systèmes fondés sur RSA, les systèmes de chiffrement sur les courbes elliptiques utilisent des clés plus courtes, pour un niveau de sécurité équivalent.

Par la suite, on considéra une courbe elliptique définie sur un un corps fini $\mathbb{F}_p$ avec $p$ un nombre premier $p > 3$ . Pour définir l’addition de deux points distincts $P=(x_P,y_P)$ et $P=(x_Q,y_Q)$ sur la courbe elliptique $E$ , on remarque d’abord que par ces deux points passe une droite bien définie. Par le théorème de Bézout, cette droite recoupe la courbe $E$ en un troisième point. La somme des points $P$ et $Q$ est alors donnée par le symétrique de ce point par rapport à l’axe des abscisses. On donne maintenant des équations explicites pour calculer les coordonnées affines du point somme.

Si $x_P=x_Q$ et $y_P=-y_Q$ , alors $P+Q=\mathcal{O}$ . Autrement dit, l’inverse d’un point pour la loi du groupe est son symétrique par rapport à l’axe des abscisses.
Sinon, on définit les quantités suivantes:

$\lambda=\left \{\begin{array}{ll} \frac{y_Q-y_P}{x_Q-x_P} & \mbox{si}\,\, P\neq Q,\\ \frac{3x_P^2+a}{2y_P} &\mbox{si}\,\, P=Q~\mbox{et}~y_P\neq 0. \end{array} \right.$

$\mu=\left \{\begin{array}{ll} \frac{x_Qy_P-y_Qx_P}{x_Q-x_P} & \mbox{si}\,\, P\neq Q,\\ \frac{-x_P^3+ax_P+2b}{2y_P} &\mbox{si}\,\, P=Q~\mbox{et}~y_P\neq 0. \end{array} \right.$

Alors la droite $y=\lambda x+\mu$ passe par $P$ et $Q$ et les coordonnées de $P+Q$ sont :

$x_{P+Q}=\lambda^2-x_P-x_Q,$

$y_{P+Q}=-\lambda x_{P+Q}-\mu.$

Loi d’addition sur la courbe elliptique. Soit $E$ la courbe elliptique donnée par l’équation $y^2=x^3+5$ , définie sur le corps fini $\mathbb{F}_q$ , avec $q=17252297107$ . Le nombre de points sur cette courbe est $N=4r$ , avec $r=4313008603$ .
1. Écrire une fonction qui calcule un point au hasard de la courbe. Indication: pour cela, on écrit d’abord une fonction calculant des racines carrées $\bmod q$ . On se rappelle que lorsque $q=4m+3$ , la racine carrée de $a \bmod q$ (quand elle existe) est $a^{m+1} \bmod q$ .
2. Écrire une fonction qui calcule la somme des deux points de la courbe. On testera cette fonction à l’aide des exemples suivants (avec P=[6587596005,10930896470], Q=[2846256190,0], R=[1099048983,3110000776])
  P+Q=[10674847433,12569638509], P+R=[6587596005,6321400637]
  
  P+P=[1099048983,14142296331], Q+Q=O
  
  3P=[8376961733,938225291], 5P=[1708109053,5741342158]
3. Écrire une fonction qui étant donné un point $P$ de la courbe, et un entier $k$ , calcule efficacement le point $kP$ . Pour cela, on utilisera l’algorithme de multiplication rapide (double and add ou square and multiply). On testera cette fonction sur un point au hasard $P$ d’ordre $r$ de la courbe (i.e. $rP=O$ ).
Échange de clé Diffie-Hellman. Deux personnes, Alice et Bob, veulent échanger un message chiffré nécessitant une clé $K$ , qui est un nombre entier. Ils doivent échanger la clé $K$ d’abord, mais ils ne disposent pas de canal sécurisé pour cela. En 1976, Diffie et Hellman ont proposé une méthode qui répond à ce problème. Le protocole de Diffie Hellman utilise un groupe cyclique $\mathbb{G}$ (noté additivement) d’ordre $r$ et repose sur l’idée suivante:
- Étant donné un nombre entier $k$ et un élément $P$ dans le groupe $\mathbb{G}$ , il est facile de calculer $kP$ .
- Étant donné $Q=kP$ , $P$ , il est calculatoirement difficile de retrouver $k$
Le fonctionnement du protocole est le suivant. Alice choisit un nombre au hasard $a$ , calcule $aP$ et l’envoie à Bob. Bob choisit à son tour un nombre $b$ et envoie à Alice $bP$ . Alice peut alors calculer $K=a(bP)$ . Bob calcule $b(aP)$ et obtient la même clé $K$ qu’Alice.
1. (Travail en binôme) En utilisant le groupe d’ordre $r$ des points de la courbe $E$ , échangez avec un collègue une clé secrete .
L’attaque pas de bébé, pas de géant sur le logarithme discret. La méthode de Shanks pour résoudre le problème du logarithme discret est basée sur l’observation suivante :

En notant $m = \lceil \sqrt{r} \rceil$ la partie entière supérieure de la racine carrée de $r$ , on peut écrire tout élément $x$ inférieur à $r$ comme $x=x_1+x_2 m$ , avec $x_1,x_2 \leq m$ . Par conséquent, l’égalité $Q=xP$ peut s’écrire $Q-x_2(mP)=x_1P$ .

Dans un premier temps (le pas de bébé), l’algorithme construit l’ensemble $L = \{O,P,2P,...,(m-1)P\}$ . Dans un deuxième temps (le pas de géant), il calcule S=(-m)P puis recherche la valeur du membre de droite de l’équation précédente dans la liste L
```
construire l'ensemble L = {O,P,2P,...,(m-1)P}
pour i de 1 à m-1 faire
si Q+iS est dans L alors
   retourner (j-im mod r) tel que jP=Q+iS.
```
Pour chercher de manière efficace dans l’ensemble L on pourra utiliser une structure de dictionnaire.
1. Implanter l’attaque de Shanks, afin de retrouver, à partir du point de la courbe qui vous a été envoyé, le secret de votre collègue.

Navigation

7.4. Cryptographie¶

Navigation