Séance 10 : ECDSA

Séance 10 : ECDSA#

Dans ce TP, nous allons explorer l’utilisation de l’algorithme de signature ECDSA. Les objectifs sont les suivants :

  1. Implémenter la signature ECDSA grâce à l’implémentation de l’arithmétique des courbes elliptiques réalisée à la séance précédente.

  2. Comprendre l’utilisation de la bibliothèque de cryptographie openssl, libre et multi-plateforme, ainsi que des modules de la bibliothèque python pycryptodome

  3. Faire interagir notre implémentation avec ces bibliothèques, et ainsi vérifier sa validité.

Exercice 1 : utilisation de openssl#

Dans cet exercice, nous allons manipuler la bibliothèque openssl afin de signer le contenu d’un fichier avec la signature ECDSA. Pour cela, notons :

  • {type_de_courbe} une chaîne de caractères représentant une courbe elliptique utilisée dans ECDSA (ici, nous utiliserons la courbe NIST P-256 nommée prime256v1 dans openssl) ;

  • {public_key} un préfixe de fichier pour la clé publique ;

  • {private_key} un préfixe de fichier pour la clé privée ;

  • {fichier} le nom d’un fichier à signer ;

  • {signature} le nom de fichier dans lequel stocker la signature (en binaire).

Le contenu du fichier sera haché avec la fonction de hachage SHA-256. Les commandes listées ci-dessous permettent alors respectivement de :

  • créer les paramètres de la courbe elliptique à utiliser, et les stocker dans le fichier {type_de_courbe}.pem ;

  • créer une paire de clés, et stocker la clé privée dans {private_key}.pem ;

  • dériver la clé publique, et la stocker dans {public_key}.pem ;

  • afficher la paire de clés et les paramètres de la courbe ;

  • signer le fichier ;

  • vérifier la signature obtenue.

openssl ecparam -name {type_de_courbe} -out {type_de_courbe}.pem
openssl ecparam -in {type_de_courbe}.pem -genkey -noout -out {private_key}.pem
openssl ec -in {private_key}.pem -pubout > {public_key}.pem
openssl ec -in {private_key}.pem -text -param_enc explicit -noout
openssl dgst -sha256 -sign {private_key}.pem -out {signature} {fichier}
openssl dgst -sha256 -verify {public_key}.pem -signature {signature} {fichier}

Question 1. Dans un terminal, effectuer ces opérations, en choisissant des noms de fichiers appropriés. Observer les résultats (création de fichiers, affichage des paramètres, etc.).

Si l’on passe par python (sera utile plus tard), on pourra exécuter les commandes :

type_de_courbe = "prime256v1"
public_key = type_de_courbe + "-pubkey"
private_key = type_de_courbe + "-privkey"
fichier = "fichier.txt"
signature = "sign.bin"

commands = [
    f"openssl ecparam -name {type_de_courbe} -out {type_de_courbe}.pem",
    f"openssl ecparam -in {type_de_courbe}.pem -genkey -noout -out {private_key}.pem",
    f"openssl ec -in {private_key}.pem -pubout > {public_key}.pem",
    f"openssl ec -in {private_key}.pem -text -param_enc explicit -noout",
    f"openssl dgst -sha256 -sign {private_key}.pem -out {signature} {fichier}",
    f"openssl dgst -sha256 -verify {public_key}.pem -signature {signature} {fichier}",
    ]

for cmd in commands:
    print(cmd)
    os.system(cmd)

Exercice 2 : implémentation personnelle de ECDSA#

Dans le but d’implémenter une version d’ECDSA, nous avons de fixer certains paramètres du sytème.

D’abord, nous utiliserons la courbe elliptique NIST P-256, d’équation \(y^2 = x^3 + ax + b\) sur \(\mathbb{F}_p\), qui admet un groupe de points cyclique, d’ordre premier \(q\), et engendré par un point \(G\), avec les valeurs suivantes :

p  = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a  = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b  = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
Gx = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
Gy = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
G = (Gx, Gy)
q = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551

Ensuite, nous utiliserons la fonction de hachage SHA-256. Pour l’utiliser facilement avec pycryptodome, on pourra utilisera la fonction suivante :

from Crypto.Hash import SHA256

def HASH(text):
    aux = SHA256.new(bytes(text, "utf-8")).hexdigest()
    return int(aux, 16)

Cette fonction prend en entrée une chaîne de caractères text au format utf-8, et retourne l’entier associé au haché de la chaîne par la fonction SHA-256.

Enfin, on utilisera les fonctions d’arithémtique de courbe elliptique qu’on a développées à la séance précédente. Elles sont regroupées dans ce fichier.

Question 1. Implémenter une fonction de génération de clé ECDSA keygen(EC_group), qui prend en entrée une liste de \(5\) éléments EC_group = (p, a, b, G, q) correspondant aux paramètres du système, et qui retourne une paire de clés publique/privée.

from ec import *

def keygen(EC_group):
    G, q = EC_group[3:]
    a = random.randint(1, q-1)
    A = ec_mult(EC_group[:3], G, a)
    return (A, a)

Question 2. Implémenter une fonction de signature ECDSA nommée sign(EC_group, message, sk), qui prend en entrée les paramètres systèmes EC_group, le message (au format chaîne de caractères) message et la clé privée sk, et qui retourne la signature associée.

def sign(EC_group, message, sk, to_bytes=False):
    G, q = EC_group[3:]
    h = HASH(message)
    ok = False
    while not(ok):
        k = random.randint(1, q-1)
        inv_k = pow(k, -1, q)
        M = ec_mult(EC_group[:3], G, k)
        b = M[0] % q
        c = ((h + sk * b) * inv_k) % q
        ok = (b != 0 and c != 0)
    return (b, c)

Question 3. Implémenter une fonction de vérification ECDSA verif(EC_group, message, signature, pk), qui prend en entrée les paramètres systèmes EC_group, le message (au format chaîne de caractères) message, la signature signature (un couple d’entiers) et la clé publique pk, et qui teste si la signature donnée est valide.

def verif(EC_group, message, signature, pk):
    G, q = EC_group[3:]
    h = HASH(message)
    b, c = signature
    inv_c = pow(c, -1, q)
    Q1 = ec_mult(EC_group[:3], G, (h * inv_c) % q)
    Q2 = ec_mult(EC_group[:3], pk, (b * inv_c) % q)
    Q = ec_add(EC_group[:3], Q1, Q2)
    return (Q[0] % q) == b

Question 4. Créer un message, des clés, signer et vérifier avec vos fonctions.

P256_group = (p, a, b, G, q)
message = "Bonjour !"
pk, sk = keygen(P256_group)
s = sign(P256_group, message, sk)
v = verif(P256_group, message, s, pk)
print("Véritable signature =>", v)

v2 = verif(P256_group, message, (1234, 5678), pk)
print("Signature modifiée  =>", v2)
v3 = verif(P256_group, message, s, (1234, 5678))
print("Message modifiée    =>", v3)

Véritable signature => True
Signature modifiée  => False
Message modifiée    => False

Le module pycryptodome permet aussi de signer et de vérifier des signatures ECDSA. Nous allons voir si le module peut vérifier nos signatures.

Attention ! La fonction verify de vérification de signature de pycryptodome utilise les conventions suivantes :

  • elle prend en entrée le haché du message (et non le message brut) ;

  • la signature doit être fournie sous un format binaire (et non un couple d’entiers), pour lequel sont concaténés les \(32\) octets de chacun des entiers ;

  • si la signature est n’est pas valide, verify retourne une erreur (qu’il faut traiter) ;

  • si la signature est valide, verify retourne False. Elle ne renvoie donc jamais True.

Pour résumer, voici une manière d’utiliser les fonctions du module pycryptodome :

from Crypto.Signature import DSS
from Crypto.PublicKey import ECC

def pair_to_bytes(b, c):
    return b"".join([b.to_bytes(32, 'big'), c.to_bytes(32, 'big')])
    
def bytes_to_pair(signature):
    b = int.from_bytes(signature[:32], 'big')
    c = int.from_bytes(signature[32:], 'big')
    return b, c

key_cryptodome = ECC.construct(curve='p256', d=sk, point_x=pk[0], point_y=pk[1])
signer = DSS.new(key_cryptodome, 'deterministic-rfc6979')

h = SHA256.new(message.encode("utf-8"))
s = pair_to_bytes(b, c)

try:
    signer.verify(h, s)
    print("La signature est valide")
except:
    print("La signature n'est pas valide")

Question 5. Éxécutez les lignes précédentes et vérifiez que la signature construite est valide. Puis, modifiez le message et/ou la signature et observez que la signature n’est plus valide.

from Crypto.Signature import DSS
from Crypto.PublicKey import ECC

def pair_to_bytes(b, c):
    return b"".join([b.to_bytes(32, 'big'), c.to_bytes(32, 'big')])
    
def bytes_to_pair(signature):
    b = int.from_bytes(signature[:32], 'big')
    c = int.from_bytes(signature[32:], 'big')
    return b, c

key_cryptodome = ECC.construct(curve='p256', d=sk, point_x=pk[0], point_y=pk[1])
signer = DSS.new(key_cryptodome, 'deterministic-rfc6979')

h = SHA256.new(message.encode("utf-8"))
s = pair_to_bytes(*s)

try:
    signer.verify(h, s)
    print("La signature est valide")
except:
    print("La signature n'est pas valide")

h2 = SHA256.new((message + " modifié").encode("utf-8"))
try:
    signer.verify(h2, s)
    print("La signature est valide")
except:
    print("La signature n'est pas valide")

s2 = [ s[0] - 3, s[1] + 2 ]
try:
    signer.verify(h, s2)
    print("La signature est valide")
except:
    print("La signature n'est pas valide")

La signature est valide
La signature n'est pas valide
La signature n'est pas valide

Exercice 3 : interaction avec openssl#

Dans l’exercice 1, nous avons observé que openssl produisait des clés et des signatures sous des formats très particuliers. Voici des manières de « parser » ces fichiers :

import os
import base64

# lit une clé publique au format .pem (pour la courbe considérée ici)
# et retourne le point correspondant sous forme de couple d'entiers
def read_public_key(filename):
    with open(filename, "r") as f:
        coded_key = f.readlines()[1:-1]
        coded_key = [ c[:-1] for c in coded_key ]
        key = base64.b64decode("".join(coded_key))
        pk_x = int.from_bytes(key[-64:-32], 'big')
        pk_y = int.from_bytes(key[-32:], 'big')
        return (pk_x, pk_y)

# lit une clé privée au format .pem (pour la courbe considérée ici)
# et retourne l'entier correspondant
def read_private_key(filename):
    with open(filename, "r") as f:
        coded_key = f.readlines()[1:-1]
        coded_key = [ c[:-1] for c in coded_key ]
        key = base64.b64decode("".join(coded_key))
        sk = int.from_bytes(key[7:39], 'big')
        return sk


# lit une signature au format binaire
# et retourne la paire d'entiers correspondant
def read_signature(filename):
    with open(filename, "rb") as f:
        b = f.read()
        r = int.from_bytes(b[-67:-35], "big")   # les octets de r (ou b)
        s = int.from_bytes(b[-32:], "big")      # les octets de s (ou c)
        return (r,s)

Question. Vérifier la signature générée par openssl à l’aide de la fonction de vérification verif implémentée plus haut.

# Les noms de fichiers qui seront utiles
# Attention à ce que le fichier à signer existe bien (modifier le nom du fichier si besoin)
type_de_courbe = "prime256v1"
public_key = type_de_courbe + "-pubkey"
private_key = type_de_courbe + "-privkey"
fichier = "../dev/fichier.txt"
signature = "sign.bin"

# Les commandes à effectuer pour générer la signature (et observer les paramètres, cf exo1)
commands = [
    f"openssl ecparam -name {type_de_courbe} -out {type_de_courbe}.pem",
    f"openssl ecparam -in {type_de_courbe}.pem -genkey -noout -out {private_key}.pem",
    f"openssl ec -in {private_key}.pem -pubout > {public_key}.pem",
    f"openssl ec -in {private_key}.pem -text -param_enc explicit -noout",
    f"openssl dgst -sha256 -sign {private_key}.pem -out {signature} {fichier}",
    f"openssl dgst -sha256 -verify {public_key}.pem -signature {signature} {fichier}",
    ]

# On exécute les commandes
for cmd in commands[:-1]:
    # print(cmd)
    os.system(cmd)

# On vérifie la signature par openssl
print("Vérification par openssl de la signature de openssl :")
os.system(commands[-1])


# On parse les clés et la signature pour les rentre dans nos formats
pk = read_public_key(public_key + ".pem")
sk = read_private_key(private_key + ".pem")
r, s = read_signature("sign.bin")

# On lit le fichier et on vérifie la signature
mmm = open(fichier, "r").read()
print("Vérification par notre fonction de la signature de openssl :")
print(verif(P256_group, mmm, (r, s), pk))

Private-Key: (256 bit)
priv:
    ff:6c:da:40:2b:f9:ff:c1:72:37:f2:05:d2:35:b3:
    68:d3:2e:b2:3d:34:cf:d6:46:ba:76:25:46:b8:5c:
    3d:24
pub:
    04:bd:0e:e4:c7:e6:cc:03:41:97:95:4a:ef:a3:9f:
    20:0c:47:4d:8e:a7:dd:f8:48:70:cb:e3:87:83:4b:
    df:11:b9:22:16:9c:5a:2f:6a:f3:53:07:c9:f6:cf:
    4a:b0:a2:cf:19:fc:4c:2e:a0:b3:d1:9f:cd:36:86:
    38:07:f8:cc:8f
Field Type: prime-field
Prime:
    00:ff:ff:ff:ff:00:00:00:01:00:00:00:00:00:00:
    00:00:00:00:00:00:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff
A:   
    00:ff:ff:ff:ff:00:00:00:01:00:00:00:00:00:00:
    00:00:00:00:00:00:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:fc
B:   
    5a:c6:35:d8:aa:3a:93:e7:b3:eb:bd:55:76:98:86:
    bc:65:1d:06:b0:cc:53:b0:f6:3b:ce:3c:3e:27:d2:
    60:4b
Generator (uncompressed):
    04:6b:17:d1:f2:e1:2c:42:47:f8:bc:e6:e5:63:a4:
    40:f2:77:03:7d:81:2d:eb:33:a0:f4:a1:39:45:d8:
    98:c2:96:4f:e3:42:e2:fe:1a:7f:9b:8e:e7:eb:4a:
    7c:0f:9e:16:2b:ce:33:57:6b:31:5e:ce:cb:b6:40:
    68:37:bf:51:f5
Order: 
    00:ff:ff:ff:ff:00:00:00:00:ff:ff:ff:ff:ff:ff:
    ff:ff:bc:e6:fa:ad:a7:17:9e:84:f3:b9:ca:c2:fc:
    63:25:51
Cofactor:  1 (0x1)
Seed:
    c4:9d:36:08:86:e7:04:93:6a:66:78:e1:13:9d:26:
    b7:81:9f:7e:90
Vérification par openssl de la signature de openssl :
Verified OK
Vérification par notre fonction de la signature de openssl :
True

read EC key
writing EC key
read EC key
Contenu