Per RSA, come posso calcolare l'esponente segreto?

Question

Per RSA, come posso calcolare l'esponente segreto?

Dati p e q i due numeri primi e phi=(p-1)(q-1) e l'esponente pubblico (0x10001), come posso ottenere l'esponente segreto 'd'?

Ho letto che devo fare: d = e^-1 mod phi utilizzando inversione modulare e il equazione euclidea ma non riesco a capire come la formula sopra corrisponda a entrambi UN^-1 ≡ x mod m formula nella pagina wiki dell'inversione modulare o come si associa all'equazione GCD euclidea.

Qualcuno può aiutarmi per favore, saluti

Answer 1

Puoi usare il Algoritmo euclideo esteso per risolvere d nella congruenza

de = 1 mod phi(m)

Per la crittografia RSA, e è la chiave di crittografia, d è la chiave di decrittografia e la crittografia e la decrittografia sono entrambi eseguiti da esponenziale mod m.Se crittografi un messaggio acon chiave e, quindi decrittografarlo utilizzando la chiave d, si calcola (a^e)^D = un^de mod m.Ma da allora de = 1 mod phi(m), Teorema totiente di Eulero ci dice che a^de è congruente a a¹ mod m - in altre parole, ottieni l'originale a.

Non esistono modi efficaci conosciuti per ottenere la chiave di decrittazione d Conoscere solo la chiave di crittografia e e il modulo m, senza conoscere la fattorizzazione m = pq, quindi si ritiene che la crittografia RSA sia sicura.