Come suggerisce il titolo, sono curioso di sapere perché non puoi lavorare all'indietro usando un messaggio, una chiave pubblica e un messaggio crittografato per capire come decodificare il messaggio!
Non capisco come un messaggio possa essere crittografato usando una chiave e quindi come non si può lavorare all'indietro per "annullare" la crittografia?
Ci sono funzioni unidirezionali in informatica (non matematicamente provate, 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 foglio di carta. Dall'altro se ti ho dato 392397763 e ti ho chiesto di trovare i fattori primi, avresti avuto 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 a senso unico vengono utilizzate in modo intelligente per consentire a qualcuno di utilizzare la chiave pubblica per crittografare qualcosa, ma rendendo molto difficile la decodifica del messaggio risultante. Dovresti leggere l'articolo del 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 mescolarlo di nuovo? "
Alcune operazioni matematiche sono facili da fare all'indietro come in avanti. Ad esempio è possibile aggiungere 100 a un numero con la stessa facilità con cui sottrarre 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 semplicemente moltiplicare e aggiungere semplicemente. Ma tornare da g(x) a x è difficile (in maniera algebrica) come non esiste una soluzione algebrica generale a un quintic equazione . 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 (quali sono), potresti rapidamente scoprire 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 prende una coppia di chiavi. In generale, la chiave privata fornisce ai parametri un algoritmo difficile da decifrare che va in una direzione (ad esempio testo semplice in testo cifrato), e la chiave pubblica fornisce i parametri per un algoritmo difficile da decifrare nell'altro.
Quindi, la ragione per cui non si può lavorare all'indietro è semplicemente perché l'algoritmo è stato progettato per renderlo difficile.
La giocoleria è facile: basta lanciare le palline al momento giusto, in modo da avere una mano libera quando cadono. Con una palla o due palle, questo è banale. Con tre, è abbastanza facile. Con più palle, (sorprendentemente) diventa più difficile. Anche sostanzialmente più difficile.
In generale, la crittografia "inversa" fatta usando una chiave di n è come la giocoleria con 2 palle n . Con una chiave a 2048 bit è come 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656 palle. O così.
(Naturalmente, dato che gli algoritmi a chiave pubblica utilizzano molta struttura matematica, le menti intelligenti hanno sfruttato la matematica per ridurre quel numero di palle a 162259276829213363391578010288128, che è considerevolmente inferiore, ma comunque ben al di là della potenza aggregata di tutti i computer esistenti sulla Terra .)
Max, il miglior strumento mai creato per pensare alla crittografia è il cubo di Rubik. Se si presume un mondo in cui risolverli è un problema irrisolto, esistono degli analoghi diretti per DiffieHellmanKeyExchange, la firma RSA, la crittografia RSA, ecc. È possibile giocare a trucchi con trascrizioni di movimenti ed eseguendoli su cubi e scambiandoli; e le equazioni della teoria dei gruppi sono le stesse per i cubi crypto e rubiks.
Ma la cosa fondamentale da tenere a mente, che penso sia ciò che deve darti fastidio: hai ragione. È "possibile" invertire tutte queste operazioni. Tecnicamente, abbiamo f (x) e f_inverse (x), dove f (x) gira in tempo polinomiale (es .: puoi cifrare velocemente grandi numeri), mentre f_inverse (x, s) gira in tempo esponenziale (es .: anche medio i numeri sono irrealizzabili) - a meno che non si disponga del segreto giusto per eseguire il plugin su f_inverse. Tali coppie di funzioni sono chiamate botole. Le trapdoor comuni sono problemi di teoria dei numeri come la fattorizzazione primaria e i logaritmi discreti.
Quello che devi fare è leggere su Crittografia a chiave pubblica. La risposta breve è che si basa su un algoritmo che consente a una chiave di crittografare e l'altra chiave per eseguire la decrittografia, motivo per cui non è possibile lavorare all'indietro.
Questa è una spiegazione semplificata di ciò che sta accadendo, se vuoi arrivare al nocciolo del problema puoi guardare le fonti come la seguente, ma ti avverto che si allontana rapidamente dalla scogliera in qualche matematica che può o potrebbe non essere facile da seguire: link
In questa crittografia a chiave pubblica (o enciclopedia asimmetrica), per crittografare qualcosa, fai quanto segue:
Porta il tuo messaggio per essere trasmesso (come numero): diciamo che è 5.
Calcola 3 ^ 5 (3 elevato al "segreto") = 243
Calcola il modulo di esso, diviso per un altro numero: diciamo 143. Quindi, 243/143 = 100.
Ecco qua. Il tuo segreto crittografato è 100.
Per trovare il segreto, senza la chiave privata, devi solo trovare un numero che quando viene diviso per 143 ne lascia 100 come risultato, quindi trova la sua radice cubica.
Generalmente non puoi lavorare all'indietro, in modo ovvio, perché non hai abbastanza informazioni.
L'RSA dipende dalla difficoltà di fattorizzazione di grandi numeri. Si genera il modulo RSA n moltiplicando due numeri primi grandi, peq. 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 pe q, quindi calcolarli da n. Questo è un problema diverso, non un'inversione di alcuni processi che hai già utilizzato.
Allo stesso modo, la crittografia RSA di un messaggio m utilizzando la chiave di crittografia e comporta il calcolo di (m ^ e) mod n . Potresti in teoria capovolgere m ^ e usando i log, ma senza l'operazione modulo, questo numero sarebbe troppo grande per funzionare. In ogni caso, l'operazione modulo scarta parte del numero, quindi di nuovo non hai tutte le informazioni di cui avresti bisogno per lavorare all'indietro in modo triviale.
Leggi altre domande sui tag encryption public-key-infrastructure