Low Exponent Attack sur le RSA

Sommaire :

Rappel des bases :

Supposons qu’on ai deux personnes, Alice et Bob. Alice veut chiffrer un message afin de l’envoyer à Bob via du RSA.

Pour transmettre ce message, Alice et Bob vont avoir besoin de deux clés, Alice doit avoir la clé publique de Bob et Bob doit posséder sa propre clé privée afin d’être capable de déchiffrer le message.

Soient,

Lors du chiffrement, Alice va effectuer l’opération suivante :

c = m ^ e % n

Pour déchiffrer le message, Bob utilisera l’opération suivante :

m = c ^ d % n

La faille :

Selon les recommendations actuelles, le modulus n doit être d’une longueur de 2048 bits, pour ce qui est de l’exposant public e, en pratique il est généralement choisi à 65537.

Maintenant admettons que lors du choix de l’exposant public e Bob choisisse que celui-ci vaille 3.

Alice, qui veut chiffrer le message Hello World !, va le chiffrer grâce à l’opération : c = m ^ 3 % n avec n long de 2048 bits.

sera inférieur à n, par conséquence, c = m³ % n = m³.

Un attaquant sera donc capable de retrouver le message de Alice en faisant simplement une racine cubique.

Comment l’exploiter ?

Soit le code suivant générant la clé public et chiffrant le message avec :

# coding : utf-8
from Crypto.PublicKey import RSA
from binascii import hexlify

# Génération de la clé
key = RSA.generate(2048)

# On défini l'exposant à 3
key.e = 3

# Chiffrement du message d'Alice
message = b"Hello World !"

# On va transformer le message en entier afin de pouvoir le chiffrer
message = int(hexlify(message),16)

# Maintenant on va chiffrer le message
cipher = pow(message,key.e,key.n)

print("Message initial : " + str(message))
print("Message chiffré : " + str(cipher))

# On enregistre maintenant notre message dans un fichier
fichier = open("cipher.txt","w")
fichier.write(str(cipher))
fichier.close()

Maintenant le code permettant de retrouver le message initial sans connaître la clé privée.

# coding: utf-8
from binascii import unhexlify
import libnum

# On récupère le message depuis le fichier
fichier = open("cipher.txt","r")
cipher = int(fichier.readline())
fichier.close()

# On fait maintenant la racine cubique
message = libnum.nroot(cipher, 3)
message = libnum.n2s(message)
# On converti enfin le message en texte et on l'affiche
print("Message initial =" + message)

Conclusion

Au vu des recommendations actuelles, il est impossible d’utiliser un exposant public faible. Le problème d’un exposant faible est que le modulo ne s’effectue pas sur le message et qu’une racine n-ième permet de retrouver le message initial.

Actuellement la valeur de l’exposant recommandée est 65537