Re: elgamal encryption - "k" size

From: Tom St Denis (tomstdenis_at_iahu.ca)
Date: 07/22/04 

Date: Thu, 22 Jul 2004 11:20:15 GMT

Atom 'Smasher' wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
> my understanding of elgamal encryption is that it's typically used to
> encrypt a session key after choosing a random and unique "k".

Random "blinding" values are used in both encryption and signatures....

> is the size of "k" fixed? does it depend on the implementation? is it
> related to the size of the public/private key pair?

It depends on the order of the group and the modulus. Generally speaking k
should be as long as your group. That is, if your blinding value is r then
and is in the range [2, 2^k] there is a sqrt(2^k) time attack to find r.

> i was just wondering... if it uses a fixed size "k", then it would seem
> that elgamal keys larger than a certain size would be, to a certain
> extent, a waste of bits.
>
> any thoughts on this?

Make k the same size as your group.

So for example, with a 1024 bit modulus you need [roughly] a 170 bit group
[to keep things equal] so use a 170 bit k.

Tom