Université Paris 8 Année 2023–2024

M1 Mathématiques et applications, parcours ACC

Cryptographie à clef publique – Devoir à rendre n°2

devoir du 04/03/2024
à rendre jusqu’au 03/04/2024

Consignes :
1. C’est un travail à effectuer individuellement.
2. Le code doit être commenté, sans être surchargé. Des exemples d’utilisation de vos fonctions sont
bienvenus.
3. Il est conseillé d’utiliser python et sa bibliothèque cryptodome. Pour l’installation de cryptodome,
voir :

[Link]

Néanmoins, tout autre langage (assez standard) est accepté.

4. Votre code doit refléter un travail personnel. L’utilisation de ressources externes (humaines, ou
informatiques telles que ChatGPT) doit être aussi limitée que possible. En particulier, vous devez
comprendre et savoir expliquer toutes les lignes de code que vous avez écrites. En cas de doute, je
m’autorise à vous poser des questions en cours pour vérifier l’authenticité de votre travail.

1
Exercice
Exercice 1.
Exercice 1. Implantation
1. Implantation de
Implantation de la
de la signature
la signature ECDSA.
signature ECDSA.
ECDSA.
Dans cet exercice, on considère le schéma de signature ECDSA instancié avec la fonction de hachage
SHA3, de sortie 256 bits. L’objectif est de réaliser à la fois l’implantation de la signature, mais également
de l’arithmétique de la courbe elliptique sous-jacente.

Description d’ECDSA (voir également les slides de cours). Les paramètres du système sont un sous-
groupe cyclique du groupe de points d’une courbe elliptique E (F p ), qui est engendré par un point G de
la courbe d’ordre q. On suppose que l’entier q est premier. Enfin, on dispose d’une fonction de hachage
cryptographique H.

Algorithme 1 : Génération de clés ECDSA

Entrée :
Sortie : une paire de clé publique / privée
1 Choisir aléatoirement a ∈ {1, . . . , q − 1}.
2 Calculer A = aG.
3 Retourner la clé publique A et la clé privée a.

Algorithme 2 : Signature ECDSA

Entrée : un message m ∈ {0, 1}∗ , la clé privée a ∈ {1, . . . , q − 1}
Sortie : une signature s ∈ (Z/qZ)2
1 Calculer h = H (m), le convertir en entier et le réduire mod q.
2 Choisir aléatoirement k ∈ {1, . . . , q − 1}.
3 Calculer B = kG, puis b = x B mod q (où x B est la coordonnée x du point B).
4 Calculer c = (h + ab)k−1 mod q.
5 Si b = 0 ou c = 0, revenir à l’étape 2.
6 Retourner la signature s = (b, c).

Algorithme 3 : Vérification ECDSA

Entrée : un message m ∈ {0,1}∗ , une signature s = (b, c) ∈ (Z/qZ)2 , la clé publique A
Sortie : Vrai/Faux
1 Calculer h = H (m), le convertir en entier et le réduire mod q.
2 Calculer P = (hc−1 mod q) G
3 Calculer Q = (bc−1 mod q) A.
4 Calculer R = P + Q.
5 Retourner la valeur logique du test x R = b

Aide (en python).

— On pourra utiliser la bibliothèque pycryptodome pour accéder à la fonction de hachage SHA3_256.
Cette fonction prend en entrée une séquence d’octets 1 .
— On aura donc probablement besoin de convertir une chaine de caractères m (encodée en utf-8) en
une chaîne d’octets. Cela peut se faire par la fonction bytes(m, ’utf-8’). Ainsi, pour transformer
une chaîne m en haché h sous forme hexadécimale, grâce à la fonction de hachage SHA3_256, on écrit
les instructions python suivantes :
1 from Crypto . Hash import SHA3_256
2 h = SHA3_256 . new ( bytes (m , " utf -8 " ) ) . hexdigest ()

1. voir la documentation ici : [Link]

2
 — Il est également possible d’utiliser la bibliothèque hashlib, si crtyptodome ne vous convient pas.
— Pour lire le contenu d’un fichier, il existe deux fonctions importantes : open() et read(). Voici un
exemple d’utilisation :
1 # pour ouvrir le fichier et stocker l ’ objet correspondant dans la variable f :
2 f = open ( " nom_du_fichier . txt " , ’r ’)
3
4 # pour stocker dans une chaine de caracteres s le contenu du fichier associe a f
5 s = f . read ()
6
7 # pour fermer le fichier ( ne pas oublier )
8 f . close ()

— Enfin, pour transformer une écriture hexadécimale hexa en un entier, on peut utiliser
int(hexa, 16).

Partie 1 : courbes elliptiques

Dans cette partie, on souhaite implanter des fonctions élémentaires de l’arithmétique des courbes ellip-
tiques : test à 0, opposé, doublement, addition, multiplication rapide.
Pour réprésenter une courbe elliptique E , nous utiliserons l’équation de Weierstrass :

E: y2 = x3 + ax + b

où a et b sont deux élements d’un corps fini. Pour simplier l’implantation, nous choisirons systématique-
ment des corps premiers F p .
Enfin, pour les parties suivantes, nous aurons besoin de stocker un générateur G d’un sous-groupe cy-
clique des points de la courbe, ainsi que son ordre r. Au final, nous représenterons donc une courbe
elliptique en machine par une liste EC de 5 éléments (dont les deux derniers sont optionnels) :

EC = [ p, a, b, G, r ]

Par exemple, la courbe elliptique définie sur F23 par l’équation

y2 = x3 + x + 2,

qui admet un sous-groupe cyclique d’ordre r = 12 engendré par le point affine G = (2, 14), sera repré-
sentée informatiquement par

EC = [ 23, 1, 2, (2, 14), 12]

Concernant les points d’une courbe, nous en choisirons une représentation affine, à savoir un couple
( x, y) ∈ F2p satisfiant l’équation de la courbe. Le seul point qui ne rentrera pas dans le cadre de cette
représentation est le point à l’infini, que nous représenterons par la chaîne de caractères "ZERO". Ainsi,
nous devrons créer deux fonctions particulières :
1. une fonction ec_zero() qui retourne la représentation de ce point à l’infini (le neutre du groupe de
points, autrement dit zéro), donc qui retourne la chaîne de caractères "ZERO" ;
2. une fonction ec_is_zero(P) qui retourne True si l’objet P passé en paramètre est égal à notre
représentation du point à l’infini, et qui retourne False sinon.

Question 1.– Implanter les deux fonctions ec_zero() et ec_is_zero(P) décrites ci-dessus, puis vérifier
que ec_is_zero(ec_zero()) retourne bien True.

3
 Remarquons que nous adoptons la convention de nommer toutes nos fonctions relatives aux courbes
elliptiques avec le préfixe ec_ (pour elliptic curve).

Question 2.– Implanter une fonction ec_opp(EC, P), qui prend en entrée la donnée d’une courbe ellip-
tique EC et un point P de la courbe, et qui retourne l’opposé du point P (pour l’opération de groupe). On
prendra garde à distinguer le cas où P est un point affine de la courbe, du cas où P est le point à l’infini.

Pour certaines des questions suivantes, vous aurez besoin d’une fonction d’arithmétique entière : l’inverse
modulaire. Avec python, vous pouvez utiliser la syntaxe suivante pour calculer l’inverse de u modulo n :
1 pow (u , -1 , n )

Question 3.– Implanter une fonction ec_double(EC, P), qui prend en entrée la donnée d’une courbe
elliptique EC et un point P de la courbe, et qui retourne le double du point P (pour l’opération de groupe).
On prendra garde à distinguer le cas où P est égal à son opposé des autres cas.

Question 4.– Implanter une fonction ec_add(EC, P, Q), qui prend en entrée la donnée d’une courbe
elliptique EC et deux points P et Q de la courbe, et qui retourne la somme des points P et Q (pour l’opération
de groupe). Comme pour les questions précédentes, certains cas seront à distinguer.

Question 5.– Implanter une fonction ec_fast_mult(EC, P, m), qui prend en entrée la donnée d’une
courbe elliptique EC, d’un point P de la courbe et d’un entier m, et qui retourne le point mP, c’est-à-dire le
m-ème itéré du point P. Votre fonction devra utiliser la méthode double-and-add vue en cours, qui adapte
la méthode d’exponentiation rapide au cas d’un groupe additif.

Important. Afin de pouvoir tester vos fonctions, vous trouverez en annexe de ce document trois exemples
de courbes elliptiques, avec leurs paramètres, générateurs de sous-groupes cycliques et une liste de (cer-
tains de) leurs points.

4
Partie 2 : test de la fonction de hachage
Cette partie a pour but de s’assurer de la bonne utilisation 2 de la fonction de hachage SHA3-256 et de la
bonne conversion de sa sortie en un entier.

Question 6.– Créer une variable chaine_test contenant la chaîne de caractères

"Cryptographie à clé publique"

(sans les guillemets), et vérifier que son haché par la fonction SHA3-256 est, en écriture hexadécimale :

2175c8e979e092c9dc9010e1c06ea490dff52f1bf5d9df8fd2b7f35b2ae58917

Question 7.– Convertir le haché obtenu dans la question précédente en un entier, et vérifier que cet entier
vaut
15134431753598964768903003036524780383794702900043419402360626898381641713943

Question 8.– Soit q = 1000003. Hacher le contenu du fichier [Link] disponible à l’adresse sui-
vante :

[Link]

Puis, vérifier que le haché, converti en entier, puis réduit modulo q, vaut 943673.

Partie 3 : implantation de la signature

Question 9.– Implanter une fonction ecdsa_keygen(EC), qui prend en entrée la donnée d’une courbe
elliptique EC, et qui retourne une paire de clés publique/privée du système de signature ECDSA.

Question 10.– Implanter une fonction ecdsa_sign(EC, message, sk), qui prend en entrée la donnée
d’une courbe elliptique EC, une chaine de caractères message et une clé privée sk, et qui retourne une
signature du message par la clé privée dans le système de signature ECDSA.

Question 11.– Implanter une fonction ecdsa_verif(EC, message, signature, pk), qui prend en entrée
la donnée d’une courbe elliptique EC, une chaine de caractères message, une signature signature et une
clé publique pk, et qui vérifie la validité de la signature vis à vis du message et de la clé, dans le système
de signature ECDSA.

La courbe elliptique Curve25519 est une courbe standardisée pour la cryptographie, car elle admet de
nombreuses proriétés intéressantes du point de vue de la sécurité et de l’efficacité d’implantation. Cette
courbe est définie sur F p où p = 2255 − 19 (d’où son nom) est un nombre premier, par l’équation

y2 = x3 + ax + b
avec 3
a = 57896044618658097711785492504343953926634992332820282019728791901641727051837,
b = 398341948620716521344.
2. Vous pouvez également vous aider de cet outil en ligne : [Link]
3. Notez que ce n’est pas ce modèle de la courbe qui est utilisé en pratique, car les coefficients a et b sont trop gros.

5
Cette courbe admet un sous-groupe cyclique d’ordre

q = 2252 + 27742317777372353535851937790883648493 ,

engendré par le point

G = (2, 2587177637973221124604506650587198648324617568965701997790174145338249409797) .

Question 12.– Stocker les paramètres de la courbe Curve25519, puis vérifier que l’entier q est premier et
que qG = O .

Pour terminer cet exercice, dans l’archive disponible à cette adresse :

[Link]

vous trouverez différents fichiers.

1. Un fichier 4 nommé [Link] contenant une spécification de l’utilisation de la courbe
Curve25519 en cryptographie.
2. Un fichier nommé [Link], qui contient deux lignes qui représentent les deux coordronnées
(x et y, dans l’ordre) d’une clé publique ECDSA instanciée avec Curve25519.
3. 100 fichiers nommés signature<ii>.txt où ii va de 00 à 99, de deux lignes chacun. Ces fichiers
représentent chacun une signature potentielle du contenu de [Link] avec la clé privée associée
à [Link] (vous n’avez pas cette clé privée, c’est normal). La première ligne de chaque fichier
correspond à l’entier b de la signature, la seconde ligne à c.

Question 13.– Déterminer, parmi ces 100 signatures, l’unique signature valide du message consistant en
le texte contenu dans le fichier [Link].

4. que vous pouvez également retrouver ici [Link]

6
Annexe.
Pour vous aider à faire des tests sur la validité de votre implantation des courbes elliptiques, voici
quelques exemples.

Courbe 1. Définie par y2 = x3 + x + 1 sur F p avec p = 19.

— Le groupe des points est cyclique d’ordre r = 21.
— Le point G = (16, 16) est un générateur de ce groupe.
— La liste des multiples de G est :

i 0 1 2 3 4 5 6 7 8 9 10
iG O (16, 16) (13, 8) (14, 2) (0, 1) (9, 6) (10, 17) (2, 7) (5, 6) (15, 16) (7, 3)
i 11 12 13 14 15 16 17 18 19 20
iG (7, 16) (15, 3) (5, 13) (2, 12) (10, 2) (9, 13) (0, 18) (14, 17) (13, 11) (16, 3)

Courbe 2. Définie par y2 = x3 + x + 2 sur F p avec p = 23.

— Le groupe des points est d’ordre n = 24 mais n’est pas cyclique.
— Le point G = (2, 14) engendre un sous-groupe cyclique d’ordre r = 12.
— La liste des multiples de G est :

i 0 1 2 3 4 5
iG O (2, 14) (0, 5) (1, 2) (3, 20) (8, 19)
i 6 7 8 9 10 11
iG (22, 0) (8, 4) (3, 3) (1, 21) (0, 18) (2, 9)

Courbe 3. Définie par y2 = x3 + 1312x + 1 sur F p avec p = 1 000 003.

— Le groupe des points est cyclique d’ordre r = 1001409.
— Le point G = (888903, 173601) est un générateur de ce groupe.
— Voici une liste de certains multiples de G :

i 0 10 20 1000 1010
iG O (372502, 123104) (357212, 885297) (75825, 679956) (570771, 767612)
i 2000 100000 100010 101000 200000
iG (364544, 463970) (748739, 689401) (198617, 526040) (63572, 119053) (625207, 25930)