# Tag Info

14

If $p=2q+1$ is a safe prime (that is, $q$ is a prime as well), then $p-1=2q$ has exactly two prime factors: $2$ and $q=(p-1)/2$.

8

In RSA as usually practiced (encryption or signature per PKCS#1, signature per X9.31, ISO/IEC 9796-2, FIPS 186), it is NOT necessary, or even common, to require $n=p⋅q$ with $p=2⋅p′+1$ and $q=2⋅q′+1$ with $p'$ and $q'$ huge primes, as stated in the question. IF that's done, it ensures that: any small odd $e>2$ (including the common $e=3$ and $e=65537$) ...

7

Safe primes (that are two times a prime plus one) and strong primes were at some point in time considered sensible. One reason was that safe primes ensures that Pollard's $p-1$ factoring algorithm stops working. However, safe primes are not enough. There are other related factoring algorithms, such as the $p+1$ method, and strong primes also stop them. The ...

6

Actually, there are also other reasons why one wants to use safe primes in the RSA setting (when working with hidden order groups in cryptographic protocols). When choosing the RSA modulus $n=pq$ to be the product of safe primes $p=2p'+1$ and $q=2q'+1$, then we also have the following: The subgroup of $Z_n^*$ of qadratic residues is cyclic and has order $... 6 A Sophie Germain prime is a prime$p$such that$2p+1$is prime (that later prime is deemed a safe prime). For small examples, see A005384 in the OEIS. A random integer$n$has odds commensurate to$1/\log(n)^2$to be a Sophie Germain prime. Therefore, there's in the order of$2^{495}$Sophie Germain primes of 511 bits, way too much to enumerate them, much ... 6 All the properties discussed in the question are for strong primes$p$in the context of using$p$as a secret factor of a large composite$n$which factorization should be intractable; these properties are given in the landmark RSA paper (1978), without justification. Properties thought for (often public) primes used in other cryptosystems can be different. ... 5 I'm sorry to say that your code is likely to have essentially zero use. Primes used for cryptography (e.g., RSA), are on the order of 2,048 and 4,096 bits of length, or respectively roughly 616 and 1,233 digits long. Algorithms already exist to rapidly find (random) primes of this size, and unless you've broken new ground in number theory, your approach is ... 4 The smallest safe prime you got from OpenSSL was 3221226167 = 0xC00002B7. The largest was 4294967087 = 0xFFFFFF2F. This makes me hypothesize that OpenSSL is setting the two high bits to one, and choosing the rest of the bits randomly. If that is accurate, that would explain the range of primes you did. As far as why you found many more safe primes in the ... 4 Well, the obvious answer to 'how to find a Safe prime that is also a Nothing-Up-My-Sleeve' number would be to take one of the primes listed in RFC 3526. These primes (which come in several sizes) are all of the form$p = 2^n - 2^{n-64} - 1 + 2^{64} \cdot ( \lfloor 2^{n-130} \pi \rfloor + i )$, where$i$is the smallest nonnegative integer such that both$p$... 3 According to PKCS, a strong prime p is a prime with the following properties: Factorisation of (p-1) contains a large prime$p_1$, Factorisation of (p+1) contains a large prime$p_2$. This is equivalent to: $$p=2\times a_1 \times p_1+1=2\times a_2\times p_2-1$$ the integer$a_i$are suffisently small compared to$p_i$. Choosing$a_i$= 1 leads to bad ... 3 This is another way of expressing the decisional Diffie-Hellman problem. This problem is more typically written as 'given$g,\ g^a, g^b, g^c$, does$g^{ab} = g^c$?'. As for the difficulty of this problem, it is believed to be difficult as long as you stay within a large prime subgroup; in this case (because you specify a strong prime), you means that you ... 2 DLP and factorization are very different problems (which cryptocipher gurus consider of same complexity). You can't really compare the choice of using a safe prime p in order to prevent the factorization of n=p*q (recommended for RSA) with the choice of using a prime p where (p-1)/2 has a large factor (recommended for DSA). Since you are interested with DH ... 2 Well , I think DrLecter's great answer in here can be used to answer this question indirectly. But as you want to prove so I will give a proof. To prove$QR_N$is a cyclic group, first, you have to know the order of it. In fact, the order of$QR_N$is$pq=\phi(N)/4$($\phi$is Euler function ).Actually, we can show this with the help of this map:$$x\to (x_P,... 2 The$p = 2p' + 1$refers to safe primes as related to strong primes and enhances the difficulty of the discrete-log problem. This makes for a more secure system since they are more difficult to factor. It's like a prime on top of a prime, etc… 1 You are probably getting confused with the meaning of "generator" here. You are correct that a generator for the entire multiplicative group modulo$p$cannot satisfy$g^q \equiv 1$by definition. However - assuming$k = 2$here - what you probably read is that$g$is the generator of the quadratic residues modulo$p$, and this group has order$(p - 1)/2$. ... 1 In ssh-keygen.c of the OpenSSH source code, there is the following call: if (prime_test(in, out, rounds == 0 ? 100 : rounds, generator_wanted, checkpoint, start_lineno, lines_to_process) != 0) ...and a comment for the function prime_test says: * perform a Miller-Rabin primality test Therefore, it does indeed use a ... 1 The problem you want to make hard in Diffie-Hellman type groups is taking discrete logarithms, whereas you want exponentiation to be easy. Now when you pick a subgroup$G$of$\mathbb Z^*_n$, the cost of exponentiation will be roughly proportional to$n$whereas the cost of taking discrete logs will be proportional to$\sqrt{k}$where$k$is the order of the ... 1 Note the obvious: for Elgamal signature generation you must share parameters between users. If I (re-)read Elgamal encryption then it seems to me that parameter$p$or$q\$ (the safe prime) need to be shared in advance as well. Even though the generation of safe primes may be time consuming, you don't need to do this for each signature generation or ...

Only top voted, non community-wiki answers of a minimum length are eligible