1
$\begingroup$

In the ElGamal signature scheme, in addition to the public/private keypair, a random integer $K$ such that $\operatorname{gcd}(K,p-1)=1$ is chosen in the range $[1,p-1]$.

This clearly excludes $K=p-1$, because $\operatorname{gcd}(x,x)=1$ for any $x$, but not $K=1$.

However, if $K=1$, the first part of the signature is $S_1 \equiv g^1 \bmod p\equiv g \bmod p\equiv g$, and the attacker knows it. Even worse, the attacker can use $S_2$ to obtain the private key.

Why is $K=1$ a valid choice? No source that I know of mentions this. Is it something considered so trivial that is not worth mentioning, or did I miss some mistake in my reasoning?

I understand that the probability to choose $K=1$, for a large prime, is vanishingly small, but in my opinion one shouldn't leave these things to chance.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Why $K=1$ is not excluded? You can also ask why $K=2$ is not excluded. It always possible to calculate $g^2$ and by keeping $(g^2,2)$ in a lookup table, you can also recover the secret key if you see $S_1 = g^2$, in which case $K$ happen to be 2. So as $K =3$, $K= 4$ and so on so forth. As you can see, 1 is not that special.

The reason why they are not excluded is because that $K$ is chosen at uniformly random from the range. For an adversary who has only limited computational capacity, it can only guess polynomial number of $K$ and does the computation, but if the signer picks his $K$ at uniformly random, the probability of the adversary guessing the right $K$ is negligible. So as long as the signer does his job properly, we don't need to worry about $K$ being a specific value.

Improve this answer
$\endgroup$
9
  • $\begingroup$ $K=2$ is in fact invalid because 2 is not co-prime to $p-1$, but anyway, you can get the idea. $\endgroup$
    – Changyu Dong
    Commented Jun 29, 2018 at 14:21
  • $\begingroup$ To be honest, I'm not convinced by the first part of your answer. Take K=3. S1=g^3 mod p. To get 3, the attacker would have to compute DLOG(g^3) in base g, modulo p, which is hard if p is large. On the other hand, when K=1, S1=g. The attacker knows g, S1, and knows that 1 is the only possible value of K s.t. g^K=g, without having to solve the DLOG problem. $\endgroup$
    – A. Darwin
    Commented Jun 29, 2018 at 14:33
  • $\begingroup$ @A. Darwin: to verify a guess of $K=3$, the adversary only has to verify that $S_1 \equiv g^3 \bmod p$, which is negligible work compared to computing the $\operatorname{DLOG}(g^3)$ not knowing $3$. More precisely, the cost of computing $\operatorname{DLOG}(x)$ for random unkown $x$ to the cost of verifying that $S_1 \equiv g^3 \bmod p$ is much larger than the ratio of the cost of verifying that $S_1 \equiv g^3 \bmod p$ to the cost of verifying that $S_1=g$. $\endgroup$
    – fgrieu ♦
    Commented Jun 29, 2018 at 14:54
  • $\begingroup$ Isn't DLOG($g^3$)=3? The idea is that the adversary can build a lookup table $(g^x,x)$ so that for the chosen ones the discrete log can be computed easily from the table. $\endgroup$
    – Changyu Dong
    Commented Jun 29, 2018 at 14:56
  • 1
    $\begingroup$ Think again why $K =3$ Is valid. If $K=3$, using your algorithm, the adversary can get the key by no more than 3 attempts. Then why it is valid? It is valid because you know if $K$ Is randomly chosen, it is won’t be $3$ except for a negligible probability. This applies to all other possible values, including 1. $\endgroup$
    – Changyu Dong
    Commented Jun 29, 2018 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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