Re: questions on Diffie-Hellman prime selection on small generator cases
From: Feng Ye (f_ye_at_yahoo.com)
Date: 05/30/03
- Next message: 小葉南洋杉: "Re: Try to calculate"
- Previous message: Tom St Denis: "LTM book Progress"
- In reply to: Michael Scott: "Re: questions on Diffie-Hellman prime selection on small generator cases"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: 29 May 2003 20:08:17 -0700
"Michael Scott" <mscott@indigo.ie> wrote in message news:<XhtBa.15805$pK2.21726@news.indigo.ie>...
> "Feng Ye" <f_ye@yahoo.com> wrote in message
> news:a65ac9d8.0305290836.6055ba31@posting.google.com...
> > Hello,
> >
> > I have done weeks of search and study myself, but still I have couple
> > questions about picking the small generators (2, 3, or 5) in
> > Diffie-Hellman. Hope somebody out here can help me. I looked at
> > implementation by OpenSSL/ssleay (but I think theory-wise other
> > implementation will be the same).
> >
> > In OpenSSL there're such comments (copied from the code):
> > for 2, p mod 24 == 11
> > for 3, p mod 12 == 5 <<<<< does not work for safe primes.
> > for 5, p mod 10 == 3 or 7
> >
>
> This looks wrong to me. Ideally the generator should be a generator of the
> prime-order subgroup, not a primitive root. So 3 is always a good choice for
> a safe prime. So is 4. In fact you want the generator to be a QR for use
> with a safe prime.
>
> Mike Scott
>
I think u r right, openssl do have some more comments after those I
copied here which says the same thing. But I want to understand the
theoretical background, so can you take a look at my original post and
try to answer my original questions? (e.g. don't think about the prime
order subgroup for now, I will think about this later on) Thanks!
feng
> > My questions are about those comments.
> >
> > (1) g = 2 case:
> > I understand that when p = 3 mod 8, 2 will be the quadratic nonresidue
> > (QNR) modulo p(can get from Legendre symbol (2|p) ), so 2 will be the
> > primitive root of the whole group , and p is a safe prime which means
> > p = 2 mod 3, this can lead to p = 11 mod 24, as stated in the above
> > comments.
> > My question here is that Legendre symbol (2|p) actually shows 2 will
> > be the QNR when p = +3 or -3 mod 8. Now where is the -3 mod 8 (e.g. 5
> > mod 8) case? This case can lead to p = 5 mod 24 (satisfy both 5 mod 8,
> > and 2 mod 3) as another valid choice of p when g = 2. Is this p = 5
> > mod 24 correct?
> >
> > (2) g = 3 case:
> > Legendre symbol (3|p) shows when p = +1 or -1 mod 12, 3 is the QNR,
> > combine this with safe prime requirements (p = 2 mod 3), we get p = 11
> > mod 12 is the only case. Is this p = 11 mod 12 a valid case?
> >
> > (3)g = 5 case:
> > I don't know how to compute (5|p), can somebody show me? And, after
> > compute the (5|p) value, how to relate the QNR case with the primitive
> > root? (I found some such explanation in internet for g=2 and g=3
> > cases, but not g=5 case).
> >
> > I have did a lot of number theory study myself, still I have the above
> > questions, hope somebody can give me some clue.
> > Thanks a lot!
> >
> > Regards,
> > Feng
- Next message: 小葉南洋杉: "Re: Try to calculate"
- Previous message: Tom St Denis: "LTM book Progress"
- In reply to: Michael Scott: "Re: questions on Diffie-Hellman prime selection on small generator cases"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
|
