Talk:Safe prime

Sorry, I withdraw my comments. Peter Luschny

On the usefulness of safe primes in cryptography.

The security of some public key systems depend on the use of safe primes. One known example is the secure remote password protocol. Attacks would exist if primes other than safe primes were allowed there. But not all public key systems require safe primes. For example, the primes chosen for the RSA cryptosystem need not have a special form.

Thanks for clarifying that. But I'm still wondering if the size of the safe primes matter. For instance, if I chose 23 and 47 for my N and q, could the encryption be bypassed more easily than if I chose 650183 and 1300367? PrimeFan 22:40, 12 July 2005 (UTC)

Yes the size matters in cryptographic applications. E.g., the SRP protocol requires primes that are at least 512 bits long, because that protocol would not be secure if the discrete logarithm were computable. Therefore, I also added the best known (to me) result on discrete logarithm to the article. But it seems better not to include a size requirement into the definition of the term safe prime. What size should that be? Cryptographers just have to specify in their papers things like "Let n be a sufficently large safe prime." 16 July 2005

Sounds good. PrimeFan 22:33, 21 July 2005 (UTC)

ANSI X9-31 puts several requirements on primes, but not the requirement of using a safe prime. When ANSI X9-31:1988 allows (but does not require) safe primes in its informative appendix C.9, that is for another definition of safe prime, introduced by a Crypto 1997 rump session presentation by Marc Gysin, "Some New Pollard Rho's and Attacks for RSA" <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.5196> which does not appear to ever have made it to a peer-reviewed paper. That alternate use of "safe prime" to designate a stronger form of strong prime seems very rare or/and faulty.Fgrieu (talk) 08:56, 24 August 2010 (UTC)

Infinitely many

Can anyone add a proof that there are infinitely many safe primes? 147.188.192.41 14:53, 4 November 2005 (UTC)

If you can prove that there are infinitely many Sophie Germain primes, then you've automatically proved that there are also infinitely many safe primes. PrimeFan 19:20, 4 November 2005 (UTC)

Possible Error?

When I was writing a program to calculate safe primes, and when I used the test (2p + 1) in my program, it generated a different list than when I used ((n - 1)/2). And the ((n - 1)/2) were correct ones. Is this the correct test of safe primality? The list of primes page uses the ((n-1)/2) form. So which is it? Thanks. P337 22:29, 1 October 2007 (UTC)

Safe prime says: A safe prime is a prime number of the form 2p + 1, where p is also a prime. List of prime numbers#Safe primes says: p and (p-1) / 2 are both prime (it's implied that p is the safe prime). The two definitions are equivalent and the two prime lists are equal. It's different what the variable name p is used for but the defined safe primes are the same (the larger of the two primes in the definitions). Sources also agree on this definition. PrimeHunter 00:24, 2 October 2007 (UTC)