Grupos Diffie Hellman

Question

Eu vi que inteiros não negativos com a operação de adição não podem ser o grupo Diffie Hellman. Estou tendo problemas para entender por que não pode ser o grupo DHKE. Para ser o grupo DHKE, existem cinco propriedades a serem realizadas,

1. A operadora está fechada
2. associatividade
3. elemento de identidade existe
4. elemento inverso existe
5. comutatividade

Tentei com o grupo de {0,1,2,3,4,5,6} e p = 7, e todas as propriedades acima foram mantidas. Não consegui encontrar nenhum exemplo adequado para mostrar que as propriedades acima não são realizadas. Que outros exemplos podem mostrar que os inteiros não negativos com operador de adição não são um dos grupos de chaves de Diffie Hellman?

Answer 1

Para ser o grupo DHKE, existem cinco propriedades a serem realizadas,

Isso é verdade; no entanto, para ser um grupo DHKE seguro , deve haver uma propriedade adicional:

• O "problema de log discreto" precisa ser difícil; isto é, dado um valor público$xG$ (Onde $G$ é o identificador do grupo público, $x$ é o seu valor privado, e $xG$ é o gerador agindo sobre si mesmo $x$ vezes), é difícil recuperar $x$.

No caso adicional, temos $xG = \underbrace{G + G + … + G}_{x \text{ times}} = x \times G$., Onde $\times$ é a multiplicação de inteiros.

Se nós sabemos $x \times G$ e nós sabemos $G$, então é fácil recuperar $x$ fazendo uma divisão simples (divisão modular se estivermos fazendo o módulo de adição $p$, o que não é muito mais difícil) e, portanto, o Diffie-Hellman seria trivialmente inseguro.

Na verdade, apenas ter um problema de log discreto seguro não é suficiente; o problema "Diffie-Hellman" também precisa ser difícil, isto é, dado$G$, $xG$ e $yG$, deve ser difícil recuperar $xyG$ (isso é conhecido como o problema computacional Diffie Hellman), ou dado $G$, $xG$, $yG$, $zG$, deve ser difícil determinar se $xy = z$(isso é conhecido como o problema de decisão Diffie Hellman). Qualquer um desses problemas pode ser mais fácil do que o "problema de log discreto" para qualquer grupo; no entanto, para adição, nenhum desses problemas é difícil.