Re: Parameters for Diffie-Hellman-Merkle

From: Richard Heathfield (dontmail_at_address.co.uk.invalid)
Date: 06/09/03 

Date: Mon, 9 Jun 2003 19:15:15 +0000 (UTC)

Gregory G Rose wrote:

>>> 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.

Okay. Thanks.

>>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).

Actually, no, I don't know what a group is, except in the rather limited
sense in which I've been exposed to it in pop math books (e.g. Gardner,
Stewart). Pretty lame, huh? I suspect it's actually not that big a deal,
but I have yet to come across a ***clear*** explanation of how groups are
used in a cryptographic context. (Note emphasis.)

Schneier did a fantastic job with AC2, but not quite fantastic enough. Singh
had a good go at the pop crypto end. Somewhere in between Singh and AC2,
there is scope for a decent book that fills in the necessary theoretical
gaps in an accessible way.

> 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.

I think I actually understand that. Perhaps you should write that book. :-) 

-- 
Richard Heathfield : binary@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

Relevant Pages

  • =?iso-8859-1?Q?Lata=92s?= tribute to the Gurus
    ... AMONG the treasured memories of my life is having heard Lata Mangeshkar ... Surinder Singh, who was there as Income Tax ... browsing over a shelf of books. ...
    (rec.music.indian.misc)
  • Re: BJP role in 1984 riots
    ... Padma Bhushan. ... Wow, you knew MRA? ... Narayan and Raja Rao's books stick in my mind. ... I know Khushwant Singh returned his PB after Operation Bluestar. ...
    (soc.culture.indian)
  • Re: UK bookshops that stock Bruce Schneier books?
    ... > store that actually has stocks of the aforementioned books and is ... I got my copy of AC2 from Waterstone's. ...
    (sci.crypt)