Esponenziazione Modulare: Come Gestire Numeri Giganti in Crittografia

-

Bentornati su izytech.dev! Nel precedente articolo abbiamo scoperto come simulare la divisione in aritmetica modulare utilizzando l'Inverso Moltiplicativo e l'antico Algoritmo di Euclide. Ora che sappiamo sommare, moltiplicare e "dividere" i numeri in modo sicuro, ci troviamo di fronte all'ostacolo più grande di tutti: le potenze.

Nella crittografia moderna, cifrare e decifrare un messaggio significa prendere un numero (il messaggio) ed elevarlo a una potenza colossale (la chiave) all'interno di un mondo modulare. Ma come fanno i computer a gestire numeri così incredibilmente grandi senza andare in crash?

Il problema dei numeri giganteschi

Se lavoriamo con numeri piccoli, l'esponenziazione è semplice. Calcolare 3 elevato alla 5a potenza (35) in un mondo "modulo 143" si può fare anche a mente o con una normale calcolatrice, riducendo semplicemente il risultato finale.

Ma cosa succede se dobbiamo calcolare 12.345 elevato alla 6.789, sempre modulo 143? Stiamo parlando di un numero con decine di migliaia di cifre! I normali linguaggi di programmazione e le calcolatrici non riescono a gestirlo: esaurirebbero la memoria o produrrebbero errori di arrotondamento letali. E in crittografia, se si sbaglia anche solo l'ultima cifra, l'intero messaggio va perduto.

Perché non riduciamo semplicemente l'esponente?

Potremmo pensare di usare un trucco: ridurre la base e l'esponente per il modulo 143 prima di fare i calcoli. Purtroppo, non funziona.

Come abbiamo accennato in precedenza, gli esponenti vivono in un mondo modulare completamente diverso da quello in cui vive la loro base. Non possiamo applicare un semplice modulo N all'esponente. (Scopriremo le vere regole di questo "mondo parallelo" nella prossima lezione, parlando della Funzione Totiente di Eulero!). Dobbiamo quindi trovare un algoritmo che risolva il problema senza toccare l'esponente.

La Soluzione: l'algoritmo "Square and Multiply"

Il trucco per non far "esplodere" la memoria dei computer si chiama algoritmo Square and Multiply (Eleva al quadrato e Moltiplica). Invece di moltiplicare il numero per sé stesso migliaia di volte, sfruttiamo il linguaggio naturale dei computer: il codice binario.

Ecco i tre passaggi geniali di questo metodo:

  1. Convertire l'esponente in binario: Qualsiasi esponente può essere riscritto come una sequenza di 0 e 1. Ad esempio, l'esponente 69 diventa 1000101 in binario.
  2. Eleva al quadrato (Square): Partiamo dal nostro numero di base. Ad ogni passo (per ogni bit dell'esponente), calcoliamo il quadrato del numero precedente. E qui sta il trucco: subito dopo aver fatto il quadrato, riduciamo immediatamente il risultato col modulo. In questo modo il numero non diventa mai più grande del quadrato del nostro modulo!
  3. Moltiplica (Multiply): Se il bit corrispondente nell'esponente binario è un "1", moltiplichiamo il risultato parziale per il numero base (e riduciamo di nuovo). Se è "0", saltiamo semplicemente la moltiplicazione.

Efficienza estrema per la sicurezza di tutti i giorni

Perché questo algoritmo è così speciale? Se usassimo il metodo della "forza bruta" per calcolare un numero elevato alla 69, dovremmo eseguire 69 moltiplicazioni. Con il metodo Square and Multiply, ci basta guardare quanti bit compongono il numero 69. Essendo composto da soli 7 bit, l'algoritmo richiede appena 7 iterazioni!

La complessità scende drasticamente, passando dall'ordine del numero stesso all'ordine dei suoi bit (in termini matematici, da O(E) a O(log E)). Questo crollo drastico della difficoltà di calcolo è ciò che permette ai minuscoli chip inseriti nelle nostre carte di credito o nelle smart card di eseguire crittografie di livello militare in una frazione di secondo, sfruttando pochissima batteria e memoria.

Ricapitolando: l'algoritmo Square and Multiply ci permette di eseguire calcoli mastodontici riducendo i risultati intermedi passo dopo passo e usando la rappresentazione binaria dell'esponente. Ma resta una domanda in sospeso: in quale "mondo modulare" vive l'esponente, e come facciamo a sfruttarlo per decifrare i messaggi? Ne parleremo nel prossimo capitolo con il Teorema di Eulero. Restate sintonizzati!

Riferimenti Bibliografici e Materiale di Studio

  • Coursera: Mathematical Foundations of Cryptography (Lezione 5: Esponenziazione Modulare e Algoritmo Square and Multiply).
  • Daniele Venturi (2012). Crittografia nel Paese delle Meraviglie. Springer. (Per l'efficienza computazionale in crittografia e l'algoritmo FPA - Fast Powering Algorithm).
  • Thomas H. Cormen et al. (2022). Introduction to Algorithms. MIT Press. (Per l'analisi approfondita della complessità algoritmica e l'aritmetica dei grandi numeri).

Comments

Post a Comment

Popular posts from this blog

How to Install Ubuntu 24.04 WSL on Windows 10 and 11

-
Introduction This guide shows you step-by-step how to install Ubuntu 24.04 LTS using WSL (Windows Subsystem for Linux) on Windows 10 or Windows 11. It's a great solution to run Linux without dual boot or virtual machines. Requirements Windows 10 (version 2004 or later) or Windows 11 Internet connection Administrator access 1. Enable WSL Open PowerShell as administrator and run this command: wsl --install This command enables the necessary features, installs the WSL platform, and downloads Ubuntu (usually the latest stable version). 2. Install Ubuntu 24.04 Manually (if needed) If you want to install Ubuntu 24.04 specifically, you can do it manually: wsl --install -d Ubuntu-24.04 Or if WSL is already installed: wsl --list --online wsl --install -d Ubuntu-24.04 3. First Launch and Setup After installation, open Ubuntu from the Start Menu. The first time you launch it, y...
Read more

Introduction to Rust: Writing Your First "Hello, World!"

-
Getting Started with Rust: A Beginner’s Guide Getting Started with Rust: A Beginner’s Guide Published on July 20, 2025 Setting Up the Workspace First, we need to establish a directory to store our code. While Rust is indifferent to its location, it is good practice to keep your projects well-organized. Open a terminal (or command prompt) and create a directory for your project. For Linux, macOS, and PowerShell (on Windows): # Create a "projects" directory in your home directory mkdir ~/projects # Enter the newly created directory cd ~/projects # Create the directory for our specific project mkdir hello_world # Enter the project directory cd hello_world For the Windows Command Prompt (CMD): > mkdir "%USERPROFILE%\projects" > cd /d "%USERPROFILE%\projects" > mkdir hello_world > cd hello_world Writing and Executing the P...
Read more

Getting Started with Cargo in Rust: A Beginner-Friendly Guide

-
Getting Started with Cargo in Rust: A Beginner-Friendly Guide Cargo is the default build tool and package manager for Rust. It helps you build your code, download libraries (called dependencies ), and keep everything organized. 1. What Is Cargo? When you use Cargo, you don’t have to compile your code manually with rustc . Cargo makes everything easier, especially for bigger projects. You can: Build your code Add external libraries (dependencies) Run your program Check for compile-time errors 2. Check if Cargo is Installed If you installed Rust using the official method ( rustup ), Cargo is already installed. To check, run this command in your terminal: $ cargo --version If you see a version number, you're ready! 3. Create a New Project Now, let’s create a new Rust project using Cargo: $ cargo new hello_cargo $ cd hello_cargo This creates a folder named hello_cargo with two important things inside: Car...
Read more