RSA Decryption Problem equivalence [closed]

Per creare un ambiente di crittografia RSA, è necessario scegliere i numeri primi grandi p. q.
Moltiplicando p e q ottieni n. Quindi è necessario utilizzare la funzione phi per la scelta della chiave di cifratura e (che non ha divisori comuni con phi (n)).
e e n saranno pubblici.

Per calcolare d (la chiave di decrittazione privata) da e, è necessario conoscere l'inverso moltiplicativo modulare del modulo e phi (n). È facile da calcolare con l'algoritmo Euclidean esteso ( link )
MA... non sai phi (n). E per calcolare phi (n) è necessario conoscere il suo fattore di primi (p e q)

Quindi il problema della decifrazione RSA dovrebbe essere equivalente alla fattorizzazione di un numero elevato ... ma nessuno lo dimostra mai.
Se sei interessato al motivo: link .
In effetti, il calcolo da e è (per quanto sappiamo attualmente ma non possiamo escludere che esista un modo più rapido) così difficile come il problema di fattorizzazione. MA, trovare d non è strettamente obbligatorio per invertire il messaggio chiaro originale M da C (C = M ^ e mod n). Questo è solo il modo attuale più veloce che conosciamo.
L'attacco più diretto dovrebbe essere quello di recuperare M solo da een. Non possiamo farlo per ora, ma non ci sono prove che non sia fattibile. Inoltre, molti attacchi "side channel" possono rompere RSA: cattiva scelta per p e q (quando p è vicino a q per esempio), bad padding, ecc. Tutto questo modo può semplificare la decifrazione RSA rispetto alla fattorizzazione.

E sulla tua domanda iniziale:
il calcolo della funzione phi è una complessità molto bassa (abbastanza istantanea).
Anche il calcolo delle chiavi RSA (se vuoi dire trovare d da e e phi (n)) è facile. Devi usare l'algoritmo euclideo esteso che è semplice.
La decifrazione di Rabin è più difficile o uguale al problema della decifrazione RSA, indipendentemente dal fatto che qualcuno, un giorno, dimostri che RSA è effettivamente difficile come un problema di fattorizzazione.