Re: [HM] Germain and Safe primes
Boaz Tsaban (tsaban@macs.biu.ac.il)
Mon, 26 Jul 1999 16:25:30 +0300 (IDT)
John Bibby wrote:
> As I understand it, if p and 2p+1 are both primes, then p is a Germain prime
> and 2p+1 is a "Safe" prime. (Clearly both must equal -1 mod 6, except p=2)
> [...]
> 3. How are these primes used in present-day cryptography, or elsewhere?
I know Cryptography only as a hobby, but I know that primes of the
form q=2p+1 are useful in security protocols related to the discrete-logarithm
problem of solving the equation
x
g = a (mod q)
where g,q, and a are known, and q is prime.
The reason is that the order of
the underlying group Z_q^*={1,2,..,q-1} is q-1=2p, which has the largest
possible prime factor, and no small prime factors (except 2).
The sizes of the prime factors of q-1 are strogly related
to the complexity of solving the discrete-log problem.
[The divisor 2 can be made irrelevent
if one chooses a generator g of Z_q^*, and uses its square (g*g)
as the protocol's base.]
Boaz