Mardi 13/09

Rappel

Structure modulo en cercle

Échange de clefs de Diffie-Hellman

Exemple en python :

from random import randint

p = 23
g = 3

# Alice
a = randint(1, p - 1)
A = g ** a % p

# Bob
b = randint(1, p - 1)
B = g ** b % p

# Alice de son côté
K_alice = B ** a % p

# Bob de son côté
K_bob = A ** b % p

# On vérifie l'égalité
print(K_alice == K_bob) # True

En python, au lieu de faire x ** y % z on peut faire pow(x, y, z).

Version du protocole avec 3 participants :

from random import randint

p = 23
g = 3

"""
Ce que sait Alice est préfixé par un a_
Ce que sait Bob est préfixé par un b_
Ce que sait Charlotte est préfixé par un c_
"""

a_a = randint(1, p - 1)
a_A = pow(g, a_a, p)

b_b = randint(1, p - 1)
b_B = pow(g, b_b, p)

c_c = randint(1, p - 1)
c_C = pow(g, c_c, p)

b_A = a_A # Alice transmet à Bob
b_Ab = pow(b_A, b_b, p)

c_Ab = b_Ab
c_K = pow(c_Ab, c_c, p)

b_C = c_C # Charlotte transmet à Bob
b_Cb = pow(b_C, b_b, p)

a_Cb = b_Cb
a_K = pow(a_Cb, a_a, p)

# On vérifie l'égalité entre Alice et Charlotte
print(a_K == c_K) # True

a_C = c_C # Charlotte transmet à Alice
a_Ac = pow(a_C, a_a, p)

b_Ac = a_Ac
b_K = pow(b_Ac, b_b, p)

# On vérifie que tout est bon
print(a_K == b_K == c_K)

Pour générer un nombre de 2048 bits pour RSA on peut faire :

$ openssl prime -generate -bits 2048

SSSS

Il faut 3 personnes dans ce cas là, avec ces courbes, pour avoir les infos

Homomorphisme

Avec le RSA

Soit les paires RSA
(e, n) \text{ et } (d, n)

\begin{aligned} x\prime &= x^{e} \text{ \% } n \\\ y\prime &= y^{e} \text{ \% } n \end{aligned}
\begin{aligned} x\prime y\prime &= x^{e} y^{e} \text{ \% } n \\\ y\prime &= (xy)^{e} \text{ \% } n \end{aligned}
\begin{aligned} z'^{d} \text{ \% } n & \\\ &= ((xy)^{e})^{d} \text{ \% } n \\\ &= (xy)^{ed} \text{ \% } n \\\ &= xy \end{aligned}