1
$\begingroup$

In Diffie Hellman key exchange, we have a large prime $p$ and non zero residue class $g \in F_p^x$ with a large order. An $a$ and $b$ are chosen in secret, and those are used to compute $A \equiv g^a \mod p$ and $B \equiv g^b \mod p$.

Then the two communicating agree on value $g^{ab}$ via $A^b$ and $B^a$.

$a=p-1$ would be a bad choice (by Euler Fermat theorem). My question is why is the value of $a = \frac{p-1}{2}$ a bad choice?

$\endgroup$
  • 2
    $\begingroup$ hint : what is $g^{p-1} \equiv$ ? $\endgroup$ – kelalaka Oct 29 '18 at 22:48
  • 2
    $\begingroup$ hint 2: $p$ is often chosen such that $p = 2q + 1$ where $q$ is also prime. $\endgroup$ – puzzlepalace Oct 29 '18 at 23:51
  • $\begingroup$ I would strongly encourage studying the two hints of kelalaka and puzzlepalace from a finite field and number theoretic perspective as these properties/relationships are fundamental to understanding the correctness, security, and difficulty of the problem on which the security relies. A couple excellent resources giving this information are Pinter's Book of Abstract Algebra, and Menezes' Handbook of Applied Cryptography. $\endgroup$ – Ken Goss Oct 30 '18 at 14:43
-1
$\begingroup$

Short answer: yes bad choice since it is $-1$. Let see; why;


Lemma: If $p$ is prime and $g$ is a generator $\mathbb{Z}_p^*$ then $g^{(p-1)/2} \equiv -1$.

proof: by Little Fermat Theorem we know that $g^{(p-1)} \equiv 1$. Take the square root of both sides.

$$g^{(p-1)/2} \equiv 1^{1/2}$$

the square root of $1$ is either $-1$ or $1$. If $g^{(p-1)/2} \equiv 1$ implies that $g$ has a shorter order than $p-1$, this contradicts that $g$ is generator. Then $g^{(p-1)/2} \equiv -1 $


Now, in case of $p = 2 q +1$ than $\beta = g^q = q^{(p-1)/2} = -1$. Than an attacker may force the key aggreement as fallows;

replace the messages $g^x$ and $g^y$ by $(g^x)^q$ and $(g^y)^q$ then the key agreement will be as $g^{xyq} = \beta^{xy} \equiv \pm1$

To prevent this attack use digital signatures.

$\endgroup$
-1
$\begingroup$

In Diffie-Hellman besides $p$ being prime, if the factorization of $p-1$ comprises at least one big prime $k$ such that $p=2k+1$ (can be also $jk+1$, this is a safe prime). In the worst case if the factorization is composed of computable factors then we can compute $x$ using the direct product of cyclic groups (Pohlig-Hellman).

Normally, if $p$ is prime and $g$ a generator with order $p-1$ then $g^{\frac{(p-1)}{2}} \equiv p-1 \equiv -1 \pmod p$

If $g$ is a generator of the subgroup of prime order $k$, where $k$ is large enough then $g^{\frac{(p-1)}{2}} \equiv g^k \equiv 1 \pmod p$

Both congruences are deterministic as you can see.

Generally, two congruences are related by symmetry, since both have the same square root mod p:

$$g^a \equiv -(g^b) \pmod p \quad \iff b = x-d, \ d = \frac{p-1}{2}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.