In discrete log cryptosystems like ElGamal it is noted that the "private key" $k$ should be chosen as any element of the group $G$ i.e. $k < p-1$. Does the integrity of the cryptosystem rely on $k$ being an element of the group or can it be larger as well (always assuming that $g^k \bmod{p}$ will be published in the public key)? If yes, can it be any arbitrarily selected number larger than the group?

  • 2
    $\begingroup$ If $k>p-1$ then it is functionally and security-wise fully equivalent to $k\bmod (p-1)$ $\endgroup$ – SEJPM Oct 12 '19 at 17:00

Assume that you have chosen a large $k > p$, then one can show that $k'$ with

$$k = \ell \cdot (p-1)+ k' $$ can also be your equivalent key.

From Euler's Totient Theorem, we know that $$a^{\phi(n)} \equiv 1 \bmod n$$ for all $a$ relatively prime to $n$.

If your key $k> p-1$ then we can write it like below with division algorithm - division by $p-1$;

$$k = \ell\cdot (p-1)+ k' = \ell \cdot \phi(n)+ k'$$ Now place this into $a$'s power and use the Euler's Toitent Theorem:

$$a^k \equiv a^{\ell \cdot \phi(n)+ k'} \equiv a^{\ell \cdot \phi(n)} a^{k'} \equiv \underbrace{a^{(\phi(n))\ell}}_{\equiv 1 \bmod p} a^{k'} \equiv a^{k'} \bmod p$$

Therefore we have

$$a^{k'} \equiv a^k \bmod p$$ and by using $k$ you will not achieve any higher security, contrary you will calculate unnecessarily steps in modular powering.

If you want to achieve more security, you should use a larger modulus.

| improve this answer | |

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.