Re: El Gamal modulus question
From: Thomas Pornin (pornin_at_nerim.net)
Date: 02/02/04
- Next message: n3tdiver_at_yahoo.com: "Re: Help with cypher"
- Previous message: Joe Peschel: "Re: PING: Gregory"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Mon, 2 Feb 2004 08:18:24 +0000 (UTC)
According to Peter Fairbrother <zenadsl6186@zen.co.uk>:
> Is there a reason why you can't use a generator of order p-1 * instead of
> order q?
>
> Why do you need a large prime q to divide p-1?
There are some attacks on discrete log which retrieve the exponent
modulo small factors of p-1. For such a factor f, the attack works in
O(sqrt(f)). If you use a group whose order is a multiple of q, big prime
such that O(sqrt(q)) is big, then you are safe -- and you know it (as
far as practical security is concerned, knowing that you are safe is at
least as important than being effectively safe).
This also means that if f is a small factor of p-1, and you work
with a generator of order p-1, then, knowing g^x mod p, you can
compute x modulo f. This leaks some data on x. In a typical El-Gamal
encryption, that's not a problem: x has been chosen randomly with a
uniform probability. But, in some more complex protocols, this can be
troublesome. Hence having g of order exactly q is good.
> (and aren't we abusing the word generator here? I thought it meant an
> element whose powers generated the entire set of residues. Or at least it
> did when I learned group theory)
"g" is the generator for the subgroup of Z(p-1)* on which computations
are performed. It needs not be a generator for the whole Z(p-1)* group.
--Thomas Pornin
- Next message: n3tdiver_at_yahoo.com: "Re: Help with cypher"
- Previous message: Joe Peschel: "Re: PING: Gregory"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
