# Is K=1 a valid random integer in ElGamal signature?

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.

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.
• $K=2$ is in fact invalid because 2 is not co-prime to $p-1$, but anyway, you can get the idea. – Changyu Dong Jun 29 '18 at 14:21
• @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$. – fgrieu Jun 29 '18 at 14:54
• 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. – Changyu Dong Jun 29 '18 at 14:56
• 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. – Changyu Dong Jun 29 '18 at 15:32