Bonjour,
Je cherche actuellement à écrire un programme Python permettant de chiffrer un message utilisant le système RSA. Cependant je me heurte à un problème dont je n'arrive pas à déterminer l'origine.
Je détermine p et q premiers à l'aide du test de primalité de Miller-Rabin (certes non fiable à 100%, mais je vérifie tout de même ailleurs que mes nombres sont premiers, donc le problème semble ne pas être là), je calcule leur produit n = pq, puis [TEX]\phi = (p-1)(q-1)[/TEX], je trouve un entier [TEX]e < \phi[/TEX] avec [TEX]PGCD(e; \phi) = 1[/TEX], puis [TEX]d < \phi[/TEX] tel que [TEX]d imes e = 1 [n][/TEX].
Je cherche alors à coder le nombre m = 12, puis à le décoder, et le résultat n'est cependant pas 12.
J'ai de plus remarqué qu'en modifiant l'intervalle dans lequel je prends p et q, le programme fonctionne (valeurs relativement basses) ou non (valeurs relativement hautes). Je ne comprends donc pas l'origine du problème ...
Voici le code:
from random import randrange
def PGCD(a, b):
"""Retourne le PGCD de a et b."""
if b == 0:
return a
else:
return PGCD(b, a%b)
def modulo(a, b, m):
"""Retourne (a**b) % m"""
res = 1
while b > 0:
if b%2 == 1:
res = (res * a) % m
b -= 1
b /= 2
a = (a**2) % m
return res
def temoinMiller(a, n, s, d):
"""Retourne True si a est un témoin de Miller, False sinon."""
x = modulo(a, d, n)
if x == 1 or x == n-1:
return False
while s > 1:
x = modulo(x, 2, n)
if x == n-1:
return False
s -= 1
return True
def millerRabin(n, k = 25):
"""Retourne False si n est composé, True si n est probablement premier."""
s = 0
while (n-1)/2**(s+1) == int((n-1)/2**(s+1)):
s += 1
d = int(n/2**s)
for i in range(k):
a = randrange(2, n-1)
if temoinMiller(a, n, s, d):
return False
return True
def bezout(a, b):
"""Retourne [u, v] tels que au + bv = 1."""
coefficients = [[1, 0], [0, 1]]
while a%b != 0:
coefficients.append([coefficients[-2][0] - (a//b) * coefficients[-1][0], coefficients[-2][1] - (a//b) * coefficients[-1][1]])
a, b = b, a%b
return (coefficients[-1])
def inverse_modulaire(a, m):
"""Retourne x tel que ax % m = 1."""
return (bezout(a, m)[0] % m)
#Détermination de deux nombres premiers p et q.
premiers = []
while len(premiers) != 2:
a = randrange(10**9, 10**10)
if a%2 != 0 and millerRabin(a, 25):
premiers.append(a)
p, q = premiers[0], premiers[1]
print(p, q)
n = p * q
phi = (p-1) * (q-1)
#Détermination d'un entier e tel que PGCD(e, phi) = 1.
e = randrange(int(phi/10), phi)
while PGCD(e, phi) != 1:
e = randrange(int(phi/10), phi)
#Détermination de d tel que e*d % phi = 1.
d = inverse_modulaire(e, phi)
print("Clé publique: ({}, {})
Clé privée: ({}, {})".format(n, e, d, n))
#Message à coder.
m = 12
#c = (m**e) % n message codé.
c = modulo(m, e, n)
#m2 = (c**d) % n message décodé.
m2 = modulo(c, d, n)
print(m, m2)
Si vous pouviez m'aider à trouver l'origine du problème,
Merci d'avance,
Bonne journée :)