La tua è un'osservazione molto acuta e merita una spiegazione degna
Cercherò di essere chiaro ma senza entrare troppo nei dettagli.
tra tutte le operazioni matematiche che si possono calcolare, ce ne sono alcune che richiedono pochi passi elementari (ad esempio la moltiplicazione) ed altri che invece richiedono un tempo di calcolo molto superiore (ad esempio la scomposizione in fattori primi).
Sfruttando questa caratteristica è possibile definire algoritmi che sono "facili" da calcolare in una direzione, ma molto difficili nella direzione opposta:
Es: 13 x 17 = 221
Per calcolare la moltiplicazione basta effettuare alcune semplici operazioni, tra le quali una ricerca in una tabella (la famosa tavola pitagorica) e la somma finale dei risultati parziali. A sua volta la somma finale può essere vista come una ricerca in una tabella di somme a singola cifra.
Tutte queste operazioni sono semplici e soprattutto il loro numero è moderato. Si dimostra che il calcolo della moltiplicazione richieda un numero elementare di operazioni che è direttamente proporzionale al numero totale delle cifre dei fattori calcolati.
Direttamente proporzionale significa che se raddoppio le cifre, raddoppio il tempo di calcolo; se moltiplico per 10 il numero di cifre, moltiplico per 10 il tempo di calcolo; ecc...
Procedimento inverso:
dato 221, trovare i suoi fattori primi.
Per questo compito sono noti molti algoritmi, alcuni dei quali molto sofisticati. Un esempio banale sarebbe quello di "provare" a dividere 221 per ogni numero a partire da 2, e verificare il resto della divisione.
221 : 2 = 110 resto 1
221 : 3 = 73 resto 2
221 : 4 = 55 resto 1
221 : 5 = 44 resto 1
...
..
221 : 13 = 17 resto 0 --- Trovato!
quindi prendere i due numeri, 13 e 17, e ripetere su di loro lo stesso procedimento, per verificare che siano effettivamente primi, oppure se possono essere scomposti ulteriormente.
Esistono algoritmi che effettuano meno operazioni rispetto a questo molto elementare, ma tutti gli algoritmi noti hanno comunque una complessità esponenziale rispetto al numero di cifre dell'input. Ciò significa che se aggiungo una cifra, moltiplico per 10 il numero di operazioni da fare; se aggiungo 2 cifre, moltiplico per 100; in generale, se aggiungo N cifre, moltiplico per 10 elevato N il numero di operazioni necessarie.
Ecco perchè la crittografia funziona! Alla base ci sono operazioni come questa, che possono essere eseguite in senso diretto con pochi calcoli, ma per essere eseguite in senso inverso (senza avere la "chiave") richiedono un numero di operazioni elementari talmente elevato (quando le cifre sono a centinaia o migliaia), da risultare "praticamente incalcolabili". Si calcola che, per decrittare un messaggio crittato con ElGamal, con chiavi da 4096 bit, usando in parallelo tutti i computer e supercomputer del mondo, occorra un tempo miliardi di miliardi di volte maggiore a quello della vita stimata dell'universo.
Alcuni problemi matematici usati in crittografia sono:
Scomposizione in fattori primi (RSA)
Calcolo del logaritmo discreto (ElGamal, DSA, Diffie-Hellman)
Interpolazione di curve ellittiche su campi discreti (Elliptic DSA, Elliptic Diffie-Hellman)
Ovviamente, se un giorno un brillante matematico dovesse scoprire un algoritmo "veloce" (cioè con tempo polinomiale rispetto al numero di cifre, anzichè esponenziale) per risolvere questi problemi, tutti gli attuali sistemi crittografici diverrebbero inutilizzabili, e si dovrà ricorrere ad altri metodi.
Spero di averti chiarito un po' le idee... per approfondimenti leggi su wikipedia (possibilmente quella inglese) o procurati qualche dispensa universitaria sulla crittografia e sull'algebra dei gruppi (si trovano gratuitamente sui siti delle varie università)
Ciao
