Ci sono funzioni unidirezionali nell'informatica (non dimostrate matematicamente, ma sarai ricco e famoso se dimostrerai il contrario). Queste funzioni sono facili da risolvere in un modo ma difficili da invertire, ad es. è facile calcolare 569 * 757 * 911 = 392397763 in un minuto o due su un pezzo di carta. Dall'altro, se ti dessi 392397763 e ti chiedessi di trovare i fattori primi, avresti un momento molto difficile. Ora, se questi numeri sono davvero grandi, anche il computer più veloce del mondo non sarà in grado di invertire la fattorizzazione in tempi ragionevoli.

Nella crittografia a chiave pubblica queste funzioni unidirezionali sono utilizzate in modo intelligente per consentire a qualcuno di utilizzare la chiave pubblica per crittografare qualcosa, ma rendendo molto difficile decrittografare il messaggio risultante. Dovresti leggere l'articolo Wiki RSA cryptosystem.

La tua domanda è un po 'come questa (con scuse a Tom Stoppard): "perché posso mescolare la marmellata nel mio budino di riso, ma non mescolarla di nuovo?"

Alcune operazioni matematiche sono facili da eseguire sia all'indietro che in avanti. Ad esempio, puoi aggiungere 100 a un numero con la stessa facilità con cui sottrai 100. Tuttavia, alcuni sono più difficili da invertire. Ad esempio, se prendo x e trovo g (x) = a (x ^ 5) + b (x ^ 4) + c (x ^ 3) + d (x ^ 2 ) + ex + f , devo fare semplicemente moltiplicazioni e addizioni semplici. Ma tornare da g (x) a x è difficile (in modo algebrico) poiché non esiste una soluzione algebrica generale per un'equazione quintica. Non è immediatamente ovvio perché dovrebbe essere così (al contrario di un'equazione quadratica), ma lo è. Per un esempio più appropriato, se ti dicessi che 34129 e 105319 erano entrambi primi (cosa che sono) potresti scoprire rapidamente che il loro prodotto era 3594432151. Tuttavia, se ti chiedessi di trovare i due fattori primi di 3594432151 , probabilmente lo troverai piuttosto difficile.

La crittografia a chiave pubblica richiede un paio di chiavi. In generale, la chiave privata fornisce i parametri di un algoritmo difficile da invertire che va in una direzione (ad es. Testo semplice in testo cifrato), e la chiave pubblica fornisce parametri per un algoritmo difficile da invertire che va nell'altra.

Quindi, il motivo per cui non puoi lavorare all'indietro è semplicemente perché l'algoritmo è progettato per renderlo difficile.

Giocoleria è facile: basta lanciare le palline al momento giusto, in modo da avere la mano libera quando cadono. Con una o due palline, questo è banale. Con tre, è abbastanza facile. Con più palle, (sorprendentemente) diventa più difficile. Anche sostanzialmente più difficile.

In generale, la crittografia "inversa" eseguita utilizzando una chiave n bit è come giocoleria con 2 ⁿ palline. Con una chiave a 2048 bit è come 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656 palle. O così.

(Ovviamente, poiché gli algoritmi a chiave pubblica utilizzano molta struttura matematica, le menti intelligenti hanno sfruttato la matematica per ridurre quel numero di palline a 162259276829213363391578010288128, che è notevolmente inferiore, ma ancora ben oltre l'aggregato potenza di tutti i computer esistenti sulla Terra.)

Max, il miglior strumento mai creato per pensare alla crittografia è il cubo di Rubik. Se presumi un mondo in cui risolverli è un problema irrisolto, ci sono analoghi diretti per DiffieHellmanKeyExchange, firma RSA, crittografia RSA, ecc. Puoi giocare brutti scherzi annotando le mosse ed eseguendole sui cubi e scambiandole; e le equazioni della teoria dei gruppi sono le stesse per la crittografia e per i cubi di rubik.

Ma la cosa fondamentale da tenere a mente, che penso sia ciò che deve disturbarti: hai ragione. È "possibile" invertire tutte queste operazioni. Tecnicamente, abbiamo f (x) e f_inverse (x), dove f (x) viene eseguito in tempo polinomiale (ovvero: puoi crittografare rapidamente grandi numeri), mentre f_inverse (x, s) viene eseguito in tempo esponenziale (ad esempio: anche medio i numeri non sono fattibili) - a meno che tu non abbia i segreti giusti da inserire in f_inverse. Tali coppie di funzioni sono chiamate botole. Le trappole comuni sono problemi di teoria dei numeri come la scomposizione in fattori primi e i logaritmi discreti.

Quello che devi fare è leggere la crittografia a chiave pubblica. La risposta breve è che si basa su un algoritmo che consente a una chiave di crittografare e all'altra chiave di eseguire la decrittografia, motivo per cui non è possibile lavorare all'indietro.

Questa è una spiegazione semplificata di ciò che sta accadendo, se vuoi arrivare al cuore del problema puoi guardare a fonti come le seguenti, ma tieni presente che precipita rapidamente in un po 'di matematica questo potrebbe essere o meno facile da seguire: http://nrich.maths.org/2200

In questa crittografia a chiave pubblica (o codifica asimmetrica), per crittografare qualcosa, fai quanto segue:

Prendi il tuo messaggio da trasmettere (come un numero): diciamo che è 5.

Calcola 3 ^ 5 (3 elevato al "segreto") = 243

Calcola il modulo, diviso per un altro numero: diciamo 143. Quindi, 243/143 = 100.

Ecco fatto. Il tuo segreto crittografato è 100.

Per trovare il segreto, senza la chiave privata, devi solo trovare un numero che quando diviso per 143 lascia 100 come risultato, e poi trovare la radice cubica di esso.

In genere non puoi lavorare all'indietro, in modo ovvio, perché non hai abbastanza informazioni.

RSA dipende dalla difficoltà di fattorizzare grandi numeri. Generi il tuo modulo RSA n moltiplicando due grandi numeri primi, p e q. Moltiplicare p per q è facile. Puoi anche invertire l'operazione calcolando q = n / p (o p = n / q ). Quello che non puoi fare facilmente è buttare via sia p che q, quindi calcolarli da n. Questo è un problema diverso, non un'inversione di un processo che hai già utilizzato.

Allo stesso modo, la crittografia RSA di un messaggio m utilizzando la chiave di crittografia e implica l'elaborazione di (m ^ e) mod n codice>. In teoria potresti invertire m ^ e usando i log, ma senza l'operazione modulo, questo numero sarebbe troppo grande per lavorare. In ogni caso, l'operazione modulo scarta parte del numero, quindi ancora una volta non hai tutte le informazioni di cui avresti bisogno per lavorare a ritroso in modo banale.