Chiffrement asymétrique RSA

# RSA simplifié - version pédagogique import random import math def is_prime(n, k=5): """Test de primalité de Miller-Rabin""" if n <= 1: return False elif n <= 3: return True elif n % 2 == 0: return False # Écrire n-1 comme d*2^s d = n - 1 s = 0 while d % 2 == 0: d //= 2 s += 1 for _ in range(k): a = random.randint(2, n-2) x = pow(a, d, n) if x == 1 or x == n-1: continue for __ in range(s-1): x = pow(x, 2, n) if x == n-1: break else: return False return True def generate_prime(bits): """Génère un nombre premier de taille donnée""" while True: p = random.getrandbits(bits) p |= (1 << bits-1) | 1 # Assure que le nombre a la bonne taille et est impair if is_prime(p): return p def extended_gcd(a, b): """Algorithme d'Euclide étendu""" if a == 0: return (b, 0, 1) else: g, y, x = extended_gcd(b % a, a) return (g, x - (b // a) * y, y) def modinv(a, m): """Calcul de l'inverse modulaire""" g, x, y = extended_gcd(a, m) if g != 1: raise Exception('Pas d\'inverse modulaire') else: return x % m def generate_keys(bits=32): """Génère une paire de clés RSA""" p = generate_prime(bits//2) q = generate_prime(bits//2) while q == p: q = generate_prime(bits//2) n = p * q phi = (p-1)*(q-1) # Choix de e premier avec phi e = 65537 while math.gcd(e, phi) != 1: e = random.randint(2, phi-1) d = modinv(e, phi) return ((n, e), (n, d)) def encrypt(public_key, plaintext): """Chiffrement RSA""" n, e = public_key m = int.from_bytes(plaintext.encode(), 'big') if m >= n: raise ValueError("Message trop long pour la taille de la clé") c = pow(m, e, n) return c def decrypt(private_key, ciphertext): """Déchiffrement RSA""" n, d = private_key m = pow(ciphertext, d, n) plaintext = m.to_bytes((m.bit_length() + 7) // 8, 'big').decode() return plaintext # Exemple d'utilisation if __name__ == "__main__": print("Génération des clés RSA...") public_key, private_key = generate_keys(32) # 32 bits pour la démo (trop faible en pratique) message = "Hello RSA" print(f"Message original: {message}") # Chiffrement ciphertext = encrypt(public_key, message) print(f"Message chiffré: {ciphertext}") # Déchiffrement decrypted = decrypt(private_key, ciphertext) print(f"Message déchiffré: {decrypted}") # Vérification if decrypted == message: print("✅ Succès : le déchiffrement a bien retrouvé le message d'origine !") else: print("❌ Échec du déchiffrement.")

# Attaque par factorisation sur RSA faible from math import gcd, isqrt import random def pollards_rho(n): """Algorithme de Pollard's Rho pour la factorisation""" if n % 2 == 0: return 2 if n % 3 == 0: return 3 if n % 5 == 0: return 5 while True: c = random.randint(1, n-1) f = lambda x: (pow(x, 2, n) + c) % n x, y, d = 2, 2, 1 while d == 1: x = f(x) y = f(f(y)) d = gcd((x - y) % n, n) if d != n: return d def factor(n): """Factorisation d'un nombre n (méthode naïve + Pollard's Rho)""" factors = [] # Test des petits facteurs premiers for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]: while n % p == 0: factors.append(p) n = n // p if n == 1: return factors # Algorithme plus sophistiqué pour les grands nombres if n > 1: d = pollards_rho(n) factors += factor(d) factors += factor(n // d) return factors def crack_rsa(public_key): """Tente de casser RSA en factorisant n""" n, e = public_key print(f"Tentative de factorisation de n = {n}...") factors = factor(n) if len(factors) != 2: raise ValueError("n n'est pas le produit de deux nombres premiers") p, q = factors[0], factors[1] print(f"Facteurs trouvés: p = {p}, q = {q}") phi = (p-1)*(q-1) d = modinv(e, phi) return (n, d) # Exemple d'utilisation if __name__ == "__main__": # Génération d'une clé faible pour la démo public_key, private_key = generate_keys(32) # 32 bits seulement! print(f"Clé publique: (n={public_key[0]}, e={public_key[1]})") # Attaque cracked_private_key = crack_rsa(public_key) print(f"Clé privée trouvée: (n={cracked_private_key[0]}, d={cracked_private_key[1]})") # Vérification if cracked_private_key == private_key: print("✅ Attaque réussie! La clé privée a été retrouvée.") else: print("❌ Échec de l'attaque.")

# RSA sécurisé avec PyCryptodome from Crypto.PublicKey import RSA from Crypto.Cipher import PKCS1_OAEP from Crypto.Hash import SHA256 from Crypto import Random def generate_secure_keys(bits=2048): """Génère une paire de clés RSA sécurisée""" key = RSA.generate(bits) private_key = key.export_key() public_key = key.publickey().export_key() return public_key, private_key def encrypt_message(public_key, message): """Chiffrement RSA avec OAEP padding""" rsa_key = RSA.import_key(public_key) cipher = PKCS1_OAEP.new(rsa_key, hashAlgo=SHA256) ciphertext = cipher.encrypt(message.encode()) return ciphertext def decrypt_message(private_key, ciphertext): """Déchiffrement RSA avec OAEP padding""" rsa_key = RSA.import_key(private_key) cipher = PKCS1_OAEP.new(rsa_key, hashAlgo=SHA256) try: plaintext = cipher.decrypt(ciphertext).decode() return plaintext except ValueError as e: raise ValueError("Échec du déchiffrement - clé invalide ou message corrompu") from e # Exemple d'utilisation if __name__ == "__main__": print("Génération de clés RSA 2048 bits...") public_key, private_key = generate_secure_keys() message = "Message secret à protéger" print(f"Message original: {message}") # Chiffrement ciphertext = encrypt_message(public_key, message) print(f"Message chiffré (hex): {ciphertext.hex()}") # Déchiffrement decrypted = decrypt_message(private_key, ciphertext) print(f"Message déchiffré: {decrypted}") # Vérification if decrypted == message: print("✅ Succès : le déchiffrement a bien retrouvé le message d'origine !") else: console.log("❌ Échec du déchiffrement.")

# Signature numérique avec RSA from Crypto.PublicKey import RSA from Crypto.Signature import pkcs1_15 from Crypto.Hash import SHA256 from Crypto import Random def generate_key_pair(): """Génère une paire de clés RSA""" key = RSA.generate(2048) return key def sign_message(private_key, message): """Signe un message avec la clé privée""" h = SHA256.new(message.encode()) signature = pkcs1_15.new(private_key).sign(h) return signature def verify_signature(public_key, message, signature): """Vérifie une signature avec la clé publique""" h = SHA256.new(message.encode()) try: pkcs1_15.new(public_key).verify(h, signature) return True except (ValueError, TypeError): return False # Exemple d'utilisation if __name__ == "__main__": # Génération des clés key = generate_key_pair() # Message à signer message = "Ceci est un message important à signer" print(f"Message original: {message}") # Signature signature = sign_message(key, message) print(f"Signature (hex): {signature.hex()}") # Vérification (cas valide) is_valid = verify_signature(key.publickey(), message, signature) print(f"Signature valide? {is_valid}") # Vérification (cas invalide - message altéré) is_valid = verify_signature(key.publickey(), message + "!", signature) print(f"Signature valide après altération? {is_valid}")