Python - Système de chiffrement RSA

[henryallen]

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 , je trouve un entier avec , puis tel que .

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: ({}, {}) \nClé 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
-----

[henryallen]

Re-bonjour,

Il s'avère qu'à force de tester différentes choses, j'ai trouvé l'origine du problème: ma fonction modulo. Plus précisément, le souci est que, pour les nombres assez grands, a>>1 et a/2 ne donnent pas les mêmes résultats.

Considérons le code suivant:

for b in [n for n in range(10**20, 10**20 + 50) if n%2 == 0]:
    print(b, b>>1, int(b/2), b/2)

Le b/2 vaudra toujours la même valeur, alors même que b varie ... C'est là le problème.

Du coup, je ne suis pas bien sûr de saisir ... Le problème viendrait de la façon dont Python gère les grands nombres ? Dans le cas de trop grands nombres, une division (par 2 en l'occurence) ne serait pas "correctement" faite ?

Merci d'avance,
Bonne journée.

[PA5CAL]

Bonjour

La différence de comportement vient du fait que l'opération de décalage est réalisée sur un nombre entier, tandis que l'opération de division est réalisée sur un nombre à virgule flottante.

La représentation des nombres en virgule flottante (qui est liée à la machine) consiste à traiter les valeurs sous la forme :

(-1)^s × 1,mmm...mm × 2^xxx...xx

où s est le signe, mmm...mm la mantisse et xxx...xx l'exposant, stockés sous forme binaire.

Pour un valeur stockée dans un espace mémoire de taille donnée (par exemple 64 bits), cette représentation procure moins de chiffres binaires significatifs (mantisse+1) que la représentation entière.

Par conséquent, à partir d'une valeur assez élevée, la division par deux du nombre en virgule flottante ne modifie plus la mantisse (elle décrémente juste l'exposant), tandis que la même valeur représentée par un entier peut encore être décalée d'un bit à droite pour donner le résultat attendu.

Mais il existe une limite au-delà de laquelle les valeurs traitées des deux manières donneront des résultats faux, faute de disposer d'un nombre suffisant de bits pour représenter le résultat.

[PA5CAL]

(... faute de disposer d'un nombre suffisant de bits pour représenter ces valeurs ou bien le résultat.)

[A voir en vidéo sur Futura]

[pm42]

Dans le cas de trop grands nombres, une division (par 2 en l'occurence) ne serait pas "correctement" faite ?

Si tu veux faire une division entière, met x // 2 au lieu de x/2 (en Python 3).

[PA5CAL]

Voici un petit programme pour illustrer la limite du format en virgule flottante sur 64 bits suivant la norme IEEE754 (1+mantisse=53 bits) :

for i in range(51,56) :
  for j in range(8) :
    a = 2**i+j
    div_ent = a//2
    div_flt = int(a/2)
    print("2**{0}+{1} = {2} {3} {4} {5}".format(i,j,a,div_ent,div_flt,div_ent==div_flt))
  print()

[henryallen]

Bonsoir,

@pm42: le fait est que je le sais, mais je n'ai pas l'habitude de le faire ... Merci !

@PA5CAL: merci pour ces explications !

Bonne soirée.