Appendice culturale - aritmetica modulare e crittografia RSA

Un’appendice culturale, fuori programma di Quinta, che mostra come l’aritmetica elementare (mcd, divisori, congruenze) sia diventata — a partire dagli anni ‘70 — la base della sicurezza digitale moderna. Si introducono le congruenze modulo $n$, il piccolo teorema di Fermat e il teorema di Eulero, fino all’algoritmo RSA: un esempio splendido di matematica “pura” che si rivela imprevedibilmente applicata.

• Congruenze modulo n
• Aritmetica modulare - somma, prodotto, potenza
• Piccolo teorema di Fermat e teorema di Eulero
• L’algoritmo RSA
• RSA giocattolo - p=11, q=13

A cultural appendix, outside the Year 5 syllabus, showing how elementary arithmetic (gcd, divisors, congruences) became — from the 1970s onwards — the basis of modern digital security. We introduce congruences modulo $n$, Fermat’s little theorem and Euler’s theorem, up to the RSA algorithm: a splendid example of “pure” mathematics that turns out to be unexpectedly applied.

• Congruences modulo n
• Modular arithmetic - sum, product, power
• Fermat’s little theorem and Euler’s theorem
• The RSA algorithm
• Toy RSA - p=11, q=13

Questa appendice è fuori programma di Quinta scientifico, ma mostra come l’aritmetica elementare (mcd, divisori, congruenze) sia diventata — a partire dagli anni ‘70 — la base della sicurezza digitale moderna. È un esempio splendido di matematica “pura” che si rivela imprevedibilmente applicata. Il punto di partenza è la relazione di congruenza.

Definizione — Congruenza modulo $n$

Dati $a,b\in\mathbb{Z}$ e $n\in\mathbb{N}$ con $n\ge 2$, si dice che $a$ è congruo a $b$ modulo $n$, e si scrive $a \equiv b \pmod n,$ se $n$ divide $a-b$. Equivalentemente: $a$ e $b$ danno lo stesso resto nella divisione per $n$.

Esempi: $17\equiv 2\pmod 5$ (poiché $17-2=15$ è divisibile per $5$); $-3\equiv 4\pmod 7$. L’aritmetica modulare è quella dell’orologio: $14$ ore $+ 13$ ore $= 27\equiv 3\pmod{24}$ (le $3$ di mattina del giorno dopo).

Collegamenti

Argomenti: Distribuzioni probabilita
Concetti: Aritmetica modulare · Congruenza
Competenze: Usare formule

This appendix is outside the Fifth-year scientific syllabus, but it shows how elementary arithmetic (gcd, divisors, congruences) became — starting from the 1970s — the basis of modern digital security. It is a splendid example of “pure” mathematics that turns out to be unpredictably applied. The starting point is the congruence relation.

Definition — Congruence modulo $n$

Given $a,b\in\mathbb{Z}$ and $n\in\mathbb{N}$ with $n\ge 2$, we say that $a$ is congruent to $b$ modulo $n$, and we write $a \equiv b \pmod n,$ if $n$ divides $a-b$. Equivalently: $a$ and $b$ give the same remainder in the division by $n$.

Examples: $17\equiv 2\pmod 5$ (since $17-2=15$ is divisible by $5$); $-3\equiv 4\pmod 7$. Modular arithmetic is that of the clock: $14$ hours $+ 13$ hours $= 27\equiv 3\pmod{24}$ (3 o’clock the next morning).

Links

Topics: Distribuzioni probabilita
Concepts: Aritmetica modulare · Congruenza
Skills: Usare formule

La congruenza si comporta bene rispetto alle operazioni: si può “ridurre modulo $n$” in qualsiasi momento del calcolo, il che rende praticabili anche potenze altrimenti enormi.

Proprietà — Compatibilità con le operazioni

Se $a\equiv a'\pmod n$ e $b\equiv b'\pmod n$, allora $a+b \equiv a'+b'\pmod n, \quad a\cdot b\equiv a'\cdot b'\pmod n, \quad a^k\equiv (a')^k\pmod n.$ L’aritmetica modulare “rispetta” le operazioni di somma, prodotto e potenza. Non sempre la divisione: $2x\equiv 4\pmod 6$ non implica $x\equiv 2$ (anche $x=5$ funziona). La divisione modulare richiede che $\mathrm{mcd}(a,n)=1$.

Esempio — Calcolo veloce di potenze modulari

$7^{100}\pmod{13}$. Per Fermat $7^{12}\equiv 1\pmod{13}$. Allora $7^{100} = 7^{96}\cdot 7^4 = (7^{12})^8\cdot 7^4\equiv 7^4 = 2401 = 13\cdot 184 + 9\equiv 9\pmod{13}.$

Collegamenti

Argomenti: Distribuzioni probabilita
Concetti: Aritmetica modulare · Congruenza
Metodi: Aritmetica modulare
Competenze: Calcolare · Usare formule

Congruence behaves well with respect to operations: you can “reduce modulo $n$” at any moment of the computation, which makes even otherwise enormous powers feasible.

Property — Compatibility with operations

If $a\equiv a'\pmod n$ and $b\equiv b'\pmod n$, then $a+b \equiv a'+b'\pmod n, \quad a\cdot b\equiv a'\cdot b'\pmod n, \quad a^k\equiv (a')^k\pmod n.$ Modular arithmetic “respects” the operations of sum, product and power. Not always division: $2x\equiv 4\pmod 6$ does not imply $x\equiv 2$ (also $x=5$ works). Modular division requires $\mathrm{mcd}(a,n)=1$.

Example — Fast computation of modular powers

$7^{100}\pmod{13}$. By Fermat $7^{12}\equiv 1\pmod{13}$. Then $7^{100} = 7^{96}\cdot 7^4 = (7^{12})^8\cdot 7^4\equiv 7^4 = 2401 = 13\cdot 184 + 9\equiv 9\pmod{13}.$

Links

Topics: Distribuzioni probabilita
Concepts: Aritmetica modulare · Congruenza
Methods: Aritmetica modulare
Skills: Calcolare · Usare formule

Due teoremi classici sono il cuore aritmetico di RSA: quello di Fermat per i moduli primi e la sua generalizzazione dovuta a Eulero per moduli qualsiasi.

Teorema — Piccolo teorema di Fermat

Se $p$ è primo e $\mathrm{mcd}(a,p)=1$, allora $a^{p-1} \equiv 1\pmod p.$

Teorema — Eulero

Sia $\varphi(n)$ il numero di interi in $\{1,2,\ldots,n\}$ coprimi con $n$ (funzione di Eulero). Se $\mathrm{mcd}(a,n)=1$, allora $a^{\varphi(n)} \equiv 1\pmod n.$

Per una rilettura storica di Fermat ed Eulero sui residui modulari si veda Stillwell (cap. 3).

Calcolo di $\varphi(n)$. Se $n = p\cdot q$ con $p,q$ primi distinti, $\varphi(n) = (p-1)(q-1)$. Esempio: $\varphi(11\cdot 13) = 10\cdot 12 = 120$.

Collegamenti

Argomenti: Distribuzioni probabilita
Concetti: Aritmetica modulare · Funzione di eulero
Competenze: Usare formule
Persone: Leonhard Euler (Eulero) · Pierre de Fermat

Two classical theorems are the arithmetic heart of RSA: Fermat’s one for prime moduli and its generalisation due to Euler for arbitrary moduli.

Theorem — Fermat's little theorem

If $p$ is prime and $\mathrm{mcd}(a,p)=1$, then $a^{p-1} \equiv 1\pmod p.$

Theorem — Euler

Let $\varphi(n)$ be the number of integers in $\{1,2,\ldots,n\}$ coprime with $n$ (Euler’s totient function). If $\mathrm{mcd}(a,n)=1$, then $a^{\varphi(n)} \equiv 1\pmod n.$

For a historical re-reading of Fermat and Euler on modular residues see Stillwell (ch. 3).

Computing $\varphi(n)$. If $n = p\cdot q$ with $p,q$ distinct primes, $\varphi(n) = (p-1)(q-1)$. Example: $\varphi(11\cdot 13) = 10\cdot 12 = 120$.

Links

Topics: Distribuzioni probabilita
Concepts: Aritmetica modulare · Funzione di eulero
Skills: Usare formule
People: Leonhard Euler (Eulero) · Pierre de Fermat

RSA (Rivest, Shamir, Adleman, 1977; pubblicato nel 1978) basa la propria sicurezza su due fatti:

• È facile moltiplicare due primi grandi e ottenere un numero $n$;
• È difficilissimo (con i computer attuali, impraticabile per primi di $300$ cifre) fattorizzare $n$ ritrovando $p$ e $q$.

Schema operativo.

1. Alice sceglie due primi $p,q$ grandi e calcola $n=pq$ e $\varphi(n) = (p-1)(q-1)$.
2. Sceglie $e$ coprimo con $\varphi(n)$ (chiave pubblica di codifica).
3. Calcola $d$ tale che $ed\equiv 1\pmod{\varphi(n)}$ (chiave privata di decodifica). $d$ è l’inverso modulare di $e$.
4. Pubblica $(n,e)$. Tiene segreti $d$, $p$, $q$.
5. Bob, per inviare il messaggio $m\in\{0,\ldots,n-1\}$, calcola $c = m^e\bmod n$ e invia $c$.
6. Alice decodifica: $m = c^d\bmod n$, grazie a Eulero $c^d \equiv m^{ed} \equiv m^{1+k\varphi(n)} \equiv m\cdot 1 \equiv m\pmod n$.

Osservazione — Perché funziona in pratica

Tutte le operazioni di codifica/decodifica si fanno in tempo polinomiale ($O(\log^3 n)$ con esponenziazione veloce). L’unico passo che richiederebbe tempo esponenziale è fattorizzare $n$: con primi $p,q$ di $1024$ bit ciascuno ($\approx 300$ cifre decimali) nessun calcolatore conosciuto può farlo in tempi ragionevoli. La sicurezza di RSA poggia su questa asimmetria. Lo scenario cambierà se e quando il calcolo quantistico renderà praticabile l’algoritmo di Shor: è una delle ragioni dello sviluppo della crittografia post-quantistica.

Collegamenti

Argomenti: Distribuzioni probabilita
Concetti: Aritmetica modulare · Crittografia rsa · Funzione di eulero
Competenze: Modellizzare
Persone: Adleman · Rivest · Shamir

RSA (Rivest, Shamir, Adleman, 1977; published in 1978) bases its security on two facts:

• It is easy to multiply two large primes and obtain a number $n$;
• It is extremely hard (with current computers, impractical for primes of $300$ digits) to factorise $n$ recovering $p$ and $q$.

Operating scheme.

1. Alice chooses two large primes $p,q$ and computes $n=pq$ and $\varphi(n) = (p-1)(q-1)$.
2. She chooses $e$ coprime with $\varphi(n)$ (public encoding key).
3. She computes $d$ such that $ed\equiv 1\pmod{\varphi(n)}$ (private decoding key). $d$ is the modular inverse of $e$.
4. She publishes $(n,e)$. She keeps secret $d$, $p$, $q$.
5. Bob, to send the message $m\in\{0,\ldots,n-1\}$, computes $c = m^e\bmod n$ and sends $c$.
6. Alice decodes: $m = c^d\bmod n$, thanks to Euler $c^d \equiv m^{ed} \equiv m^{1+k\varphi(n)} \equiv m\cdot 1 \equiv m\pmod n$.

Remark — Why it works in practice

All the encoding/decoding operations are done in polynomial time ($O(\log^3 n)$ with fast exponentiation). The only step that would require exponential time is factorising $n$: with primes $p,q$ of $1024$ bits each ($\approx 300$ decimal digits) no known computer can do it in reasonable time. RSA’s security rests on this asymmetry. The scenario will change if and when quantum computing makes Shor’s algorithm feasible: it is one of the reasons for the development of post-quantum cryptography.

Links

Topics: Distribuzioni probabilita
Concepts: Aritmetica modulare · Crittografia rsa · Funzione di eulero
Skills: Modellizzare
People: Adleman · Rivest · Shamir

Un esempio numerico minuscolo mostra tutti i passi di RSA con conti eseguibili a mano.

Esempio — RSA giocattolo $p=11$, $q=13$

$n = 143$, $\varphi(n) = 10\cdot 12 = 120$. Scegliamo $e=7$ (coprimo con $120$). L’inverso di $7$ modulo $120$ si trova con l’algoritmo di Euclide esteso: $7\cdot 103 = 721 = 6\cdot 120 + 1$, quindi $d=103$.

Codifica del messaggio $m=9$: $c = 9^7\bmod 143$. Calcolo: $9^2 = 81$, $9^4 = 81^2 = 6561 = 45\cdot 143 + 126\equiv 126$, quindi $9^7 = 9^4\cdot 9^2\cdot 9 = 126\cdot 81\cdot 9 \pmod{143}.$ Si trova $c \equiv 48\pmod{143}$.

Decodifica: $48^{103}\bmod 143$. Si verifica numericamente (esponenziazione veloce) che restituisce $9$. ✓

Il messaggio $\boxed{m=9}$ viene cifrato in $c=48$ con la chiave pubblica $(n,e)=(143,7)$ e recuperato con la chiave privata $d=103$: è l’intero meccanismo di RSA in scala di giocattolo.

Collegamenti

Argomenti: Distribuzioni probabilita
Concetti: Aritmetica modulare · Crittografia rsa
Metodi: Rsa cifratura
Competenze: Calcolare · Usare formule

A tiny numerical example shows all the steps of RSA with computations you can do by hand.

Example — Toy RSA $p=11$, $q=13$

$n = 143$, $\varphi(n) = 10\cdot 12 = 120$. We choose $e=7$ (coprime with $120$). The inverse of $7$ modulo $120$ is found with the extended Euclidean algorithm: $7\cdot 103 = 721 = 6\cdot 120 + 1$, hence $d=103$.

Encoding the message $m=9$: $c = 9^7\bmod 143$. Computation: $9^2 = 81$, $9^4 = 81^2 = 6561 = 45\cdot 143 + 126\equiv 126$, hence $9^7 = 9^4\cdot 9^2\cdot 9 = 126\cdot 81\cdot 9 \pmod{143}.$ One finds $c \equiv 48\pmod{143}$.

Decoding: $48^{103}\bmod 143$. One verifies numerically (fast exponentiation) that it returns $9$. ✓

The message $\boxed{m=9}$ is encrypted into $c=48$ with the public key $(n,e)=(143,7)$ and recovered with the private key $d=103$: it is the whole mechanism of RSA on a toy scale.

Links

Topics: Distribuzioni probabilita
Concepts: Aritmetica modulare · Crittografia rsa
Methods: Rsa cifratura
Skills: Calcolare · Usare formule