# compatibile Windows 11 # compatibile Ubuntu 24.10 # compatibile python 3.12.7 import random import math import sys import os from typing import Tuple def is_prime(n: int, k: int = 20) -> bool: """ Test di primalità di Miller-Rabin. Più `k` è alto, più è accurato. Args: n: Il numero da testare. k: Il numero di iterazioni (maggiore = più precisione). Returns: True se `n` è probabilmente primo, False altrimenti. """ if n <= 1: return False if n <= 3: return True if n % 2 == 0: return False # Trova r e d tali che n-1 = 2^r * d con d dispari r, d = 0, n - 1 while d % 2 == 0: r += 1 d //= 2 # Esegui k iterazioni del test 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(r - 1): x = pow(x, 2, n) if x == n - 1: break else: # Il ciclo non è stato interrotto, quindi n è composto return False # Tutte le iterazioni hanno superato il test, n è probabilmente primo return True def generate_prime(bits: int) -> int: """ Genera un numero primo di `bits` bit. Args: bits: Il numero di bit del numero primo. Returns: Un numero primo. """ while True: # Genera un numero casuale con il numero corretto di bit candidate = random.getrandbits(bits) # Assicurati che il bit più significativo e quello meno significativo siano 1 # (per garantire la lunghezza corretta e che non sia pari) candidate |= (1 << bits - 1) | 1 if is_prime(candidate): return candidate def gcd(a: int, b: int) -> int: """ Calcola il massimo comun divisore (MCD) di a e b usando l'algoritmo di Euclide. Args: a: Primo numero. b: Secondo numero. Returns: Il massimo comun divisore di a e b. """ while b: a, b = b, a % b return a def extended_gcd(a: int, b: int) -> Tuple[int, int, int]: """ Algoritmo di Euclide esteso (versione ITERATIVA). Trova x e y tali che ax + by = gcd(a, b). Args: a: Primo numero. b: Secondo numero. Returns: Una tupla (gcd, x, y) dove gcd è il MCD di a e b, e x e y sono i coefficienti di Bezout. """ x0, x1, y0, y1 = 1, 0, 0, 1 while b != 0: q, a, b = a // b, b, a % b x0, x1 = x1, x0 - q * x1 y0, y1 = y1, y0 - q * y1 return a, x0, y0 def modinv(a: int, m: int) -> int: """ Calcola l'inverso moltiplicativo di `a` modulo `m`. Args: a: Il numero di cui trovare l'inverso. m: Il modulo. Returns: L'inverso moltiplicativo di a modulo m, o -1 se non esiste. """ g, x, _ = extended_gcd(a, m) if g != 1: return -1 # L'inverso non esiste else: return x % m def generate_keypair(bits: int) -> Tuple[Tuple[int, int], Tuple[int, int]]: """ Genera una coppia di chiavi RSA (pubblica, privata). Args: bits: Il numero di bit del modulo `n`. Deve essere >= 16 per ragioni di sicurezza. Returns: Una tupla contenente la chiave pubblica e la chiave privata. Chiave pubblica: (n, e) Chiave privata: (n, d) """ if bits < 16: raise ValueError("La dimensione delle chiavi deve essere di almeno 16 bit (per scopi didattici, altrimenti molto di più)") p = generate_prime(bits // 2) # Due primi di circa metà della dimensione q = generate_prime(bits // 2) # dei bit desiderati per n #Assicura che p e q siano diversi, condizione importante in RSA while p == q: q = generate_prime(bits//2) n = p * q phi = (p - 1) * (q - 1) # Trova e (esponente pubblico) e = random.randrange(2, phi) while gcd(e, phi) != 1: e = random.randrange(2, phi) # Trova d (esponente privato) d = modinv(e, phi) if d == -1: raise ValueError("Errore nella generazione delle chiavi: l'inverso moltiplicativo non esiste.") return ((n, e), (n, d)) def encrypt(message: int, public_key: Tuple[int, int]) -> int: """ Cifra un messaggio (intero) usando la chiave pubblica RSA. Args: message: Il messaggio da cifrare (come intero). public_key: La chiave pubblica (n, e). Returns: Il crittogramma (come intero). """ n, e = public_key if message >= n: raise ValueError(f"Il messaggio deve essere minore di n ({n}).") return pow(message, e, n) def decrypt(ciphertext: int, private_key: Tuple[int, int]) -> int: """ Decifra un crittogramma (intero) usando la chiave privata RSA. Args: ciphertext: Il crittogramma da decifrare. private_key: La chiave privata (n, d). Returns: Il messaggio originale (come intero). """ n, d = private_key return pow(ciphertext, d, n) def bytes_to_int(b: bytes) -> int: """ Converte una sequenza di byte in un intero (big-endian). Args: b: La sequenza di byte. Returns: L'intero corrispondente. """ return int.from_bytes(b, byteorder='big') def int_to_bytes(i: int) -> bytes: """ Converte un intero in una sequenza di byte (big-endian). Args: i: L'intero da convertire. Returns: La sequenza di byte corrispondente """ num_bytes = (i.bit_length() + 7) // 8 # Calcola il numero minimo di byte necessari return i.to_bytes(num_bytes, byteorder='big') def clear_screen(): """Pulisce lo schermo della console (sia Windows che Unix-like).""" os.system('cls' if os.name == 'nt' else 'clear') def main(): """Funzione principale del programma dimostrativo.""" clear_screen() print("=" * 50) print(" Dimostrazione dell'algoritmo RSA") print("=" * 50) # 1. Generazione delle chiavi print("\n1. Generazione delle chiavi...") bits = 0 while bits < 16: try: bits = int(input(" Inserisci la dimensione delle chiavi in bit (>= 16, es. 2048): ")) if bits < 16: print(" Errore: la dimensione deve essere di almeno 16 bit.") except ValueError: print(" Errore: inserisci un numero intero.") try: public_key, private_key = generate_keypair(bits) print(f" Chiave pubblica (n, e): {public_key}") print(f" Chiave privata (n, d): {private_key}") print(" p, q e d devono rimanere segreti!") except ValueError as e: print(f" Errore durante la generazione delle chiavi: {e}") sys.exit(1) # 2. Cifratura print("\n2. Cifratura...") message_str = input(" Inserisci il messaggio da cifrare (testo): ") message_bytes = message_str.encode('utf-8') # Da stringa a bytes message_int = bytes_to_int(message_bytes) # Da bytes a intero try: ciphertext = encrypt(message_int, public_key) print(f" Messaggio come intero: {message_int}") print(f" Crittogramma: {ciphertext}") except ValueError as e: print(f" Errore durante la cifratura: {e}") sys.exit(1) # 3. Decifratura print("\n3. Decifratura...") try: decrypted_int = decrypt(ciphertext, private_key) decrypted_bytes = int_to_bytes(decrypted_int) # Da intero a bytes decrypted_str = decrypted_bytes.decode('utf-8') # Da bytes a stringa print(f" Crittogramma: {ciphertext}") print(f" Messaggio decifrato (come intero): {decrypted_int}") print(f" Messaggio decifrato (testo): {decrypted_str}") if message_str == decrypted_str: print("\n [SUCCESS] Il messaggio decifrato corrisponde all'originale!") else: print("\n [ERRORE] Il messaggio decifrato NON corrisponde all'originale!") except ValueError as e: print(f" Errore durante la decifratura: {e}") sys.exit(1) print("=" * 50) if __name__ == "__main__": main()