Re: Parameters for Diffie-Hellman-Merkle

From: Michael Amling (nospam_at_nospam.com)
Date: 06/09/03 

Date: Mon, 09 Jun 2003 18:12:29 GMT

Gregory G Rose wrote:
> (answering two messages in one, because I never
> got the one in the middle from Paul...)
>
>> [Not sure who wrote this question. --maa]
>>>How do you go about finding a small generator of the order-q subgroup?
>>
>
> In the case where P=2*Q+1, just try g=2, 3, 4, ...
> until you find one such that g^Q == 1 mod P. It
> won't take long, because it is true for about half
> the elements.
>
> In the case where you chose a 160-bit (or other
> size) Q, I'm not aware of any way to come up with
> a small generator, but if there is one, it would
> work fine. So I wasn't actually trying to say that
> it *should* be small, merely that this is one case
> where size doesn't matter. As for finding one,
> choose a random element "a" (may as well start with
> 2), and calculate g = a^((P-1)/Q) mod P. If g != 1
> then it's a generator of the order Q subgroup. If
> it is, try again with a different a.

   CMIIW, but this method also works for the earlier case, where
P=2*Q+1, in which it becomes "if g=a**2 is not 1". For any 2<=a<sqrt(P),
a**2 is a generator, so you could just pick one of 4, 9, 16, 25, ...
without calculating g**Q. Note: In practice, one would of course test
that g**Q==1, but it would be a test that the software is correctly
written, and that P and Q are indeed prime, not that 4 or 9 or ... is a
generator.

--Mike Amling

Relevant Pages

  • Re: Generator of a group
    ... > Gregory G Rose wrote: ... I suppose to find x^2 as a generator ... Phil ...
    (sci.crypt)
  • Re: Strange cryptanalysis results using bad RNGs
    ... Gregory G Rose wrote: ... > random number generator has been questioned. ... If you use a 32 bit congruential PRNG it will start repeating itself ...
    (sci.crypt)
  • Re: Generator of a group
    ... Gregory G Rose wrote: ... >>Can you help me with a complete algorithm? ... I suppose to find x^2 as a generator ...
    (sci.crypt)
  • Re: Advantages of stream ciphers over block ciphers in CTR mode?
    ... Rose already explained the issue expertly. ... The attack on Pukall's feedback variant of RC4 ... Rose's point that having feedback to a key stream generator ...
    (sci.crypt)
  • Re: Generator of a group
    ... >I search the generator of the group of quadratic residues for a prime p ... >value and it's hard to find the factorization for such a big ... Except with small probability, ... Greg Rose ...
    (sci.crypt)