Per RSA, come posso calcolare l'esponente segreto?
-
13-09-2020 - |
Domanda
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
Soluzione
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 a
con chiave e
, quindi decrittografarlo utilizzando la chiave d
, si calcola (ae)D = unde mod m
.Ma da allora de = 1 mod phi(m)
, Teorema totiente di Eulero ci dice che ade è congruente a a1 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.