Perché il bruto forzare la chiave privata DH è più difficile del calcolo della chiave pubblica?

1

Assumendo parametri condivisi: primo p base g

La chiave privata di Alice è a e la sua chiave pubblica è A , che è g ^ a mod p

Calcolare A richiede g * g * g ... a volte. Il modulo viene applicato ogni volta che è necessario.

Se un utente malintenzionato conosce A , p e g , perché è difficile calcolare a ? Non si limiterebbe a moltiplicare su g e a vedere se ha raggiunto A ?

Non vedo ciò che è fondamentalmente diverso tra il calcolo di Alice per creare A da a e da Eve calcolo alla forza bruta a conoscendo A . Qualcuno può fornire qualche informazione qui?

    
posta ztpsec 04.08.2015 - 18:58
fonte

1 risposta

3

Il calcolo della chiave pubblica è un problema di esponenziazione modulare , che può essere eseguito in O (log (e)) passaggi tramite esponenziazione al quadrato .

D'altra parte, trovare la chiave privata è il problema logaritmo discreto , per il quale non esiste un algoritmo altrettanto efficiente. Devi solo esaminare tutti i valori possibili e provarli tutti. Ci sono alcuni algoritmi migliori, come Pollig-Hellman e Big Step-Little Step, ma generalmente non sono applicabili per il caso generale (il primo è efficace solo per i numeri che si decompongono in piccoli numeri primi, per esempio)

Ciò significa che il calcolo di un esponente modulare è molto più rapido di un logaritmo discreto. Per un esponente molto grande, questo rende efficacemente l'esponenziazione una funzione unidirezionale.

... a meno che, naturalmente, tu non abbia un computer quantistico !

    
risposta data 04.08.2015 - 19:16
fonte

Leggi altre domande sui tag