# Tag Info

16

First we may want RSA primes to be something like a safe prime, ie a prime $p$ where $(p-1)/2$ is prime as well. Back in 1974 Pollard found an algorithm to factor moduli whereby you can factor $N=pq$ if $p-1$ or $q-1$ are smooth, that is all prime-factors of $p-1$ or $q-1$ are smaller than a bound $B$. The algorithm will then factor $N$ in time $\mathcal O(... 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$. 12 There is no more efficient way of generating a safe prime. Even in OpenSSL's optimized code, it can take a long time to generate a safe prime (30 seconds, a minute, 2 minutes). Run "openssl gendh 1024" on your computer to see (on my 2015 MacBook pro it can take a long time, but the variance is really high so try a few times). The comments talk about safe ... 8 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. ... 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 Here's a very simple method: Find the largest number below$2^n$that is a safe prime. Use standard primality tests for$p$and$q = (p - 1)/2$. For example,$2^{2048} - 1942289$is the largest safe prime below$2^{2048}$. But you didn't specify what you want this for. If you want to use this with Diffie–Hellman to resist discrete logarithms, then that ... 7 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$...

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

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

You can speed up the generation of safe primes by sieving for $p$ and $(p-1)/2$ simultanously. According to Safe prime generation with a combined sieve by Michael J. Wiener sieving small primes up to $2^{16}$ this way is about 15x faster than the naive algorithm. Be aware that the running time for finding a prime has a huge variation, so just measuring once ...

6

$\{p \in \mathbb Z \mid \text{$p$is prime and$(p - 1)/2$is prime}\} = \{2q + 1 \in \mathbb Z \mid \text{$q$is prime and$2q + 1$is prime}\}$ With your intervals suitably adjusted, the algorithm considers the same candidates with the same probability whether you check $p$ or $q$ for primality first.

5

What's that group? Algebraically, it is isomorphic to the group $\mathbb{Z}_{p-1} \times \mathbb{Z}_{q-1} = \mathbb{Z}_{p'} \times \mathbb{Z}_{q'} \times \mathbb{Z}_2 \times \mathbb{Z}_2$. Does $\mathbb{Z}_N^*$ guarantee computing discrete logarithm is hard? It can be shown that it is at least as hard as factoring $N$ (as if you can compute discrete ...

5

There is numerical evidence that for the vast majority of primes $p$, there exists $k$ making $q=2^k\,p+1$ prime. See first exceptions in A137715. The only practical way I see to find which $(p,k)$ make $q=2^k\,p+1$ prime in the question's context is testing $q$ for primality using a fast test. As noted in the other answer, sieving for small primes can be ...

5

In order for Diffie-Hellman to be extra secure we must use a safe prime which is (p – 1) / 2 will also be a prime. We don't have to; there are other options which achieve the same effect. However, it works. so my question is what extra benefit of using such a prime, what's new does it bring to the table. Well, a lot of the security of DH depends on the ...

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$ ...

4

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

In this post, I found that choosing RSA modulus $N$ to be product of safe primes avoids Willam's $p + 1$ factoring attack. But how can we guarantee that $p+1$ and $q+1$ are also not smooth? Why are they guaranteed to have large prime factors? Actually, you're tripping over the various notions of "safe primes" vs "strong primes". "Safe primes" are ...

4

First some definitions: A safe prime is a prime $p$ of the form $p = 2q + 1$ where $q$ is also prime. This is important as the Pohlig-Hellman algorithm runs faster as the largest factor of $p - 1$ becomes smaller. A safe prime is optimal in this sense as $p - 1 = 2q$ and $q$ is therefore the largest possible factor of $p - 1$. Strong primes are defined ...

4

Quoting CodesInChaos: P256 is secure, it just lacks some nice-to-have features that make writing a fast and secure implementation easier.

4

Is it safe to use Diffie-Hellman with Schnorr group primes, or DSA with safe primes? Safe, yes; efficient, no. For DSA, that signature algorithm includes a clever trick that reduces the size of the signature to twice the size of the subgroup (the size of $q$). Because of this, we want to reduce the size of the subgroup as much as possible (without cutting ...

3

Sorry, but I think this definition of “n-prime” number is just nonsense. Mathematicians defined prime numbers the way they did, because it provides a set of numbers with interesting mathematical properties. A simple example is that any positive integer is the product of prime numbers. With that definition of “n-prime” numbers, 4 would be 3-prime and 8 ...

3

I don't know of any industry standards, however it's obvious that your code is fairly suboptimal. The initial randomPrime() will effectively pick a candidate number $q$, and then spend a lot of time ensuring that number is prime. Now, half the time it'll pick a $q \equiv 1 \pmod 3$; if so, p will be a multiple of 3, and so you've just wasted all that time ...

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 ...

3

How is the 3072-bit modulus derived? Find the smallest $c$ such that $$p = 2^n - 2^{n - 64} - 1 + 2^{64} (\lfloor 2^{n - 130} \pi\rfloor + c)$$ and $q = (p - 1)/2$ are prime, and $p \equiv 7 \pmod 8$. In this case, $n = 3072$ and so $c = 1690314$. Use $g = 2$ as the generator. (Here $\pi = \int_{-1}^1 dx/\sqrt{1 - x^2} = 4/[1 + \mathrm K_{i=1}^\infty i^2/... 3 In cryptography, strong primes have been used (with various definitions of that) for RSA, in order to defeat the factorization of the public modulus by Pollard's p-1 and p+1 algorithms, and various other attacks. For this reason, there is no list of standard large strong primes, for that would defeat the purpose in RSA, where the prime factors of the public ... 3 This problem has been studied already; see this Wikipedia article. Does there a exist a prime$q$such that$p = 2^kq + 1$is also prime? A number$q$such that$p$is never prime is called a Sierpiński number; such numbers do exist, and some of them are prime. The smallest known such prime is$q = 271129$; the next known ones are$322523, 327739, ...

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…

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,...

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