Qual è l'algoritmo per generare un modulo e una base per un'app di scambio di chiavi Diffie-Hellman?

0

Ho un progetto scolastico in cui devo scrivere un'applicazione console java che può essere utilizzata per lo scambio di chiavi tra due persone. Tutto va bene e bene, ma trovare una buona base e un modulo sembra essere un compito difficile, soprattutto per qualcuno con un background non molto matematico, come me.

So che i due numeri devono essere primi, ma non riesco a trovare alcun algoritmo per generarli automaticamente. Apparentemente, Java ha una classe per questo (DHParameterSpec), ma dovrei implementarlo da solo. Ho letto altri thread sull'argomento, ma non ne ho trovato nessuno che io possa capire bene.

Grazie in anticipo per le risposte.

    
posta Vlad Adrian Moglan 28.10.2015 - 14:24
fonte

1 risposta

2

Il metodo più semplice per generare il modulo DH e la base (chiamati collettivamente "parametri DH") è utilizzare i valori che sono già stati generati. Ciò non implica problemi di sicurezza: molte persone possono condividere gli stessi parametri DH senza fidarsi l'un l'altro.

Tecnicamente, hai bisogno di tre valori: il modulo p , la base g e l'ordine del sottogruppo q . Idealmente, q dovrebbe essere un numero primo e g q = 1 mod p .

Ci sono dei bei valori pre-generati in RFC 3526 e RFC 5114 .

Se vuoi crearne uno tuo, allora l'algoritmo di base è "prova i valori casuali fino a quando non ottieni un primo", ma ci sono dei dettagli. Hai fondamentalmente due scelte:

  1. Genera valori q casuali e calcola p = 2 q +1; fallo finché entrambi q e p sono primi. Quando hai trovato q e p con queste caratteristiche, puoi usare g = 4 come base; è garantito che g avrà ordine esattamente q .

  2. Genera valori q casuali della "dimensione giusta" per un ordine di sottogruppo (ad esempio, 256 bit) finché non trovi un primo q . Quindi genera valori casuali r e calcola p = qr +1 per ogni r ; fallo finché non trovi un primo p . A quel punto, genera un valore casuale h e calcola g = h r mod p . Quel valore g avrà ordine q (è teoricamente possibile ma in pratica altamente improbabile che tu abbia g = 1; in quel caso, generi un nuovo h casuale

  3. casuale

Il primo metodo consente l'uso di un g molto piccolo, che offre un leggero vantaggio in termini di prestazioni quando si utilizza Diffie-Hellman (non un grosso vantaggio nella pratica, qualcosa come una velocità del + 15% al massimo quando sono state applicate le opportune ottimizzazioni). Tuttavia, generare il modulo p con quel metodo è piuttosto costoso, perché devi provare alcuni milioni di valori q finché non ne trovi uno tale che entrambi p e q sono primi.

Con il secondo metodo, la generazione dei parametri è molto più veloce, poiché si svolge in due fasi: prima trovare un primo q (alcune centinaia di tentativi), quindi un primo p (poche migliaia di tentativi). Ti dà anche un ordine di sottogruppo relativamente piccolo, che può essere anche bello. Tuttavia, si finisce con una "enorme" base g . Questo metodo è in realtà ciò che viene fatto in DSS, come specificato in FIPS 186-4 , quindi se si desidera una specifica formale con tutti i dettagli disposti, leggere l'appendice A di tale standard ("Generazione e convalida dei parametri del dominio FFC").

In ogni caso, avrai bisogno di calcoli su interi grandi, inclusi esponenziamenti modulari e test di primalità. Java fornisce sia in java.math.BigInteger .

    
risposta data 28.10.2015 - 14:50
fonte

Leggi altre domande sui tag