Re: Parameters for Diffie-Hellman-Merkle

From: Gregory G Rose (ggr_at_qualcomm.com)
Date: 06/09/03 

Date: 9 Jun 2003 09:01:43 -0700

(answering two messages in one, because I never
got the one in the middle from Paul...)

In article <bc1ak7$1hc$5@titan.btinternet.com>,
Richard Heathfield <binary@eton.powernet.co.uk> wrote:
>Paul Crowley wrote:
>
>> ggr@qualcomm.com (Gregory G Rose) writes:
>>
><snip>
>>
>>> There's no reason at all for Y to be large.
>>
>> 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.

>In fact, what do you actually /mean/ by "order-q subgroup"?

Well, you know what a group is, right? CAIN and
ABEL: Closure, Associative, Identity, iNverse,
and Abelian (Commutative). So, within the big
group (the Multiplicative Group modulo P), there
is a set of Q elements which also obey the group
laws, and by Fermat's Little Theorem, they can all
be expressed as g^k, k = 0..Q-1, where g is any
one of them except 1, the identity. Since there
are Q of them, this is called the order-Q
subgroup.

Greg. 

-- 
Greg Rose                                       INTERNET: ggr@qualcomm.com
Qualcomm Australia          VOICE:  +61-2-9817 4188   FAX: +61-2-9817 5199
Level 3, 230 Victoria Road,                http://people.qualcomm.com/ggr/ 
Gladesville NSW 2111    232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C

Relevant Pages

  • Re: generators be bound
    ... >> definition a generator of that subgroup. ... According to the folk here that's not a generator. ... Generator of a proper subgroup. ... "the multiplicative group of maximal order" is ...
    (sci.crypt)
  • Re: Using /dev/random or /dev/urandom in C code
    ... > Richard Heathfield wrote: ... >>>I would like to seed my C random function (an implementation of the ... > goes) /dev/urandom itself could compete with the Mersenne Twister? ... any random number generator can in theory be reverse-engineered, ...
    (comp.programming)
  • Re: normalizer of Q8 in SL(2,q)
    ... Edwin Clark wrote: ... This commutes with the first generator, ... automorphism group by the inner automorphisms is isomorphic to S_3. ... Hence N/Q_8 is isomorphic to a subgroup of S_3. ...
    (sci.math)
  • Re: generators be bound
    ... > Tom St Denis wrote: ... if you have a subgroup of a cyclic ... According to the folk here that's not a generator. ... be a sub-group of it as well. ...
    (sci.crypt)
  • Re: Easy question in algebra
    ... >I suppose this is an easy question in algebra: ... Is the reason for that, that g^q =1 and 1 is not a generator of G? ... In this subgroup, since q is prime and since the order of an element ...
    (sci.math)