Grupy Diffiego Hellmana

Question

Widziałem, że nieujemne liczby całkowite z operacją dodawania nie mogą być grupą Diffiego Hellmana. Mam problem ze zrozumieniem, dlaczego nie może to być grupa DHKE. Aby być grupą DHKE, należy posiadać pięć nieruchomości,

1. Operator jest zamknięty
2. asocjatywność
3. element tożsamości istnieje
4. element odwrotny istnieje
5. przemienność

Próbowałem z grupą {0,1,2,3,4,5,6} ip = 7 i wszystkie powyższe właściwości zostały zachowane. Nie mogłem znaleźć żadnego odpowiedniego przykładu pokazującego, że powyższe właściwości nie są przechowywane. Jakie inne przykłady mogą pokazać, że nieujemne liczby całkowite z operatorem dodawania nie są jedną z grup kluczy Diffiego Hellmana?

Answer 1

Aby być grupą DHKE, należy posiadać pięć nieruchomości,

To prawda; jednak, aby była bezpieczna grupa DHKE, musi istnieć dodatkowa właściwość:

• „Problem dotyczący dyskretnego dziennika” musi być trudny; to znaczy mając wartość publiczną$xG$ (gdzie $G$ to publiczny identyfikator grupy, $x$ to twoja prywatna wartość, i $xG$ to generator działający na siebie $x$ razy), jest trudny do odzyskania $x$.

W dodatkowym przypadku mamy $xG = \underbrace{G + G + … + G}_{x \text{ times}} = x \times G$., gdzie $\times$ to mnożenie liczb całkowitych.

Jeśli wiemy $x \times G$ i wiemy $G$, wtedy łatwo jest odzyskać $x$ wykonując prosty podział (podział modułowy, jeśli robimy dodawanie modulo $p$, co nie jest dużo trudniejsze), a zatem Diffie-Hellman byłby trywialnie niepewny.

Właściwie samo posiadanie problemu z bezpiecznym logiem dyskretnym nie jest wystarczające; problem „Diffiego-Hellmana” również musi być trudny, to znaczy dany$G$, $xG$ i $yG$, powinno być trudne do odzyskania $xyG$ (jest to znane jako obliczeniowy problem Diffiego Hellmana) lub dane $G$, $xG$, $yG$, $zG$, powinno być trudne do ustalenia, czy $xy = z$(jest to znane jako decyzyjny problem Diffiego Hellmana). Każdy z tych problemów może być łatwiejszy niż „problem dotyczący dziennika dyskretnego” dla dowolnej grupy; jednakże, na dodatek, żaden z tych problemów nie jest trudny.