Chiffrement RSA avec SageMath
Cet article explique comment implémenter le chiffrement RSA avec SageMath. C’est un logiciel permettant de réaliser des opérations mathématiques, particulièrement intéressant pour faire de la cryptographie. De plus, il est possible d’importer des libraires python.
Il est possible d’éditer du code SageMath en utilisant jupyter. Pour cela il faut lancer en ligne de commande : sage -n ou sage -n jupyter
Plus d’informations est disponible sur la documentation d’installation de Sage : https://doc.sagemath.org/html/en/installation/launching.html
Rappel sur le chiffrement RSA
Module de chiffrement \(\begin{aligned} n = p * q \end{aligned}\)
Indicatrice d’Euler \(\begin{aligned} φ(n) = (p - 1)(q - 1) \end{aligned}\)
Chiffrement \(\begin{aligned} c = m^e \ mod \ n \end{aligned}\)
Déchiffrement \(\begin{aligned} m = c^d \ mod \ n \end{aligned}\)
SageMath
Fonctions proposées par la librairie
- Pour le déchiffrement, la fonction
inverse_modpermet de calculer d très facilement - En déclarant le groupe multiplicatif avec
Integers(n), tous les calculs vont se faire modulo n ce qui simplifie l’écriture.
Algorithme
L’objectif ici sera de chiffrer puis déchiffrer un message(ascii) avec RSA.
Chiffrement
-
Convertir en byte message à chiffrer
->Ce fait en ajout b avant la chaîne de caractère
-
Convertir en long les bytes obtenus
-> Ce fait avec la fonction
bytes_to_longde de la librairie Crypto.Util.number -
Appliquer le chiffrement RSA sur le message
Déchiffrement
On suppose le message chiffré sous forme d’un nombre
-
Appliquer le déchiffrement RSA sur ce nombre
-
Convertir le résultat (long) en byte
-> Ce fait avec la fonction
long_to_bytesde la librairie Crypto.Util.number -
Décoder en ascii le résultat obtenu
-> Ce fait avec la fonction python native
decode
Code
from Crypto.Util.number import long_to_bytes, bytes_to_long
def encrypt(m, e):
return m ^ e
def decrypt(c, d):
return c ^ d
def main():
#---
e = 65537
n = 228430203128652625114739053365339856393
c = 126721104148692049427127809839057445790
m = b'flag{68ab82df34}'
print("Initial message : ", m)
m = bytes_to_long(m)
print("Messsage in long : ", m)
p = 12546190522253739887
q = 18207136478875858439
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
#Create field group in n
F = Integers(n)
m = F(m)
c = encrypt(m , e)
print("Cipher : ", c)
m = decrypt(c, d)
m = long_to_bytes(m)
print("Decrypted message : ", m.decode('utf-8'))
main()
Sources
- Cours de Cryptographie (CRY) enseigné à la HEIG-VD en 2020.
- Ce code a été initialement écrit pour résoudre le challenge Baby lors du redpwnCTF 2021.
- Le message chiffré, n et e sont ceux du challenges.
- Documentation Sage : https://www.sagemath.org/fr/documentation.html.