AIUI (non sono un crittografo)
Misuriamo la sicurezza della crittografia chiedendo "dato l'attacco più noto quanta potenza di calcolo ci vorrebbe per rompere questo". Questa è chiaramente una misura imperfetta, potrebbe esserci un attacco migliore che i matematici non hanno ancora capito, ma purtroppo è il migliore che abbiamo nella maggior parte dei casi.
DH lavora in un "gruppo finito". Tale gruppo consiste in un insieme finito di valori possibili insieme a un operatore che lavora su due valori dall'insieme e restituisce un altro elemento dall'insieme. L'operatore deve anche soddisfare una serie di assiomi che non entrerò qui. Il numero di elementi nel set è noto come "ordine" del gruppo.
Confusamente ci sono due modi per scrivere gruppi. Alcuni gruppi sono scritti "come addizione" con l'operatore rappresentato da "+" e l'elemento identità rappresentato da "0". Altri sono scritti "come la moltiplicazione" con l'operatore rappresentato da un operatore di moltiplicazione (".", "*", "×" o niente del tutto) e l'elemento di identità rappresentato da "1".
Possiamo applicare l'operatore ripetutamente. Se pensiamo al gruppo per analogia all'aggiunta, l'applicazione ripetuta dell'operatore è analoga alla moltiplicazione. Se pensiamo al gruppo per analogia alla moltiplicazione, l'applicazione ripetuta dell'operatore è analoga a quella dell'esponenziazione. Da qui in poi mi riferirò a questa ripetuta applicazione dell'operatore di gruppo come esponenziazione discreta. Grazie all'associatività, l'esponenziazione discreta può essere calcolata in tempo proporzionale al log dell'esponente.
La DH si basa su un'esponenziazione discreta che è invalicabile dal punto di vista computazionale. Specificamente per "A = g a " dovrebbe essere impossibile trovare "a" dati "A" e "g". Il problema di invertire l'esponenziazione discreta è noto come problema del registro discreto.
La differenza tra DH tradizionale e ECDH è il tipo di gruppo utilizzato. DH tradizionale usa gli interi non nulli modulo p sotto la moltiplicazione. ECDH usa una curva ellittica.
La difficoltà di risolvere il problema del registro discreto dipende strongmente dal particolare gruppo scelto.
Afaict per curva ellittica gli algoritmi più noti hanno una complessità di circa √n dove n è l'ordine del gruppo. Quindi per 128 bit di sicurezza abbiamo bisogno di un gruppo con circa 2 voci 256 e le nostre chiavi avranno una lunghezza di circa 256 bit.
Per il tradizionale (modulo p) è possibile utilizzare il setaccio di campo del numero generale per risolvere il problema del registro discreto. Questo algoritmo ha una complessità molto inferiore per una data dimensione di gruppo. Quindi è necessaria una chiave molto più grande per spingerlo nel regno dell'inputabilità computazionale.