Gruppi Diffie Hellman

Question

Ho visto che i numeri interi non negativi con l'operazione di addizione non possono essere il gruppo Diffie Hellman. Non riesco a capire perché non può essere il gruppo DHKE. Per essere il gruppo DHKE, ci sono cinque proprietà da tenere,

1. L'operatore è chiuso
2. associatività
3. l'elemento identità esiste
4. esiste l'elemento inverso
5. commutatività

Ho provato con il gruppo di {0,1,2,3,4,5,6} ep = 7 e tutte le proprietà di cui sopra sono state mantenute. Non sono riuscito a trovare alcun esempio appropriato per mostrare che le proprietà di cui sopra non sono mantenute. Quali altri esempi possono mostrare che gli interi non negativi con l'operatore di addizione non sono uno dei gruppi di chiavi Diffie Hellman?

Answer 1

Per essere il gruppo DHKE, ci sono cinque proprietà da tenere,

Questo è vero; tuttavia, per essere un gruppo DHKE sicuro , deve esserci una proprietà aggiuntiva:

• Il "problema del registro discreto" deve essere difficile; vale a dire, dato un valore pubblico$xG$ (dove $G$ è l'identificatore del gruppo pubblico, $x$ è il tuo valore privato, e $xG$ il generatore ha agito su se stesso $x$ volte), è difficile recuperare $x$.

Nel caso aggiuntivo, abbiamo $xG = \underbrace{G + G + … + G}_{x \text{ times}} = x \times G$., dove $\times$ è la moltiplicazione di numeri interi.

Se lo sappiamo $x \times G$ e lo sappiamo $G$, quindi è facile recuperare $x$ facendo una divisione semplice (divisione modulare se stiamo facendo l'addizione modulo $p$, che non è molto più difficile), e quindi Diffie-Hellman sarebbe banalmente insicuro.

In realtà, avere solo un problema di registro discreto sicuro non è sufficiente; anche il problema "Diffie-Hellman" deve essere difficile, cioè dato$G$, $xG$ e $yG$, dovrebbe essere difficile recuperare $xyG$ (questo è noto come problema di Diffie Hellman computazionale), o dato $G$, $xG$, $yG$, $zG$, dovrebbe essere difficile determinare se $xy = z$(questo è noto come problema decisionale Diffie Hellman). Uno di questi problemi può essere più semplice del "problema di registro discreto" per qualsiasi gruppo; tuttavia, per di più, nessuno di questi problemi è difficile.