# In the Diffie Hellman Key exchange, why is a value of $a=\frac{p-1}{2}$ a bad choice?

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?

• hint : what is $g^{p-1} \equiv$ ? – kelalaka Oct 29 '18 at 22:48
• hint 2: $p$ is often chosen such that $p = 2q + 1$ where $q$ is also prime. – puzzlepalace Oct 29 '18 at 23:51
• 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. – Ken Goss Oct 30 '18 at 14:43

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.

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}$$