Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Tag Info

17

Short answer: Yes. The discrete logarithm can be attacked in a multitude of ways: Baby-step giant-step (BSGS), Pollard's Rho, Pohlig-Hellman, and the several variants of Index Calculus, the best of which currently is the Number Field Sieve. Let $n$ be the order of the generator of our field $\mathbb{F}_p$; it is $n = p-1$. We are trying to find $x$ given $... 17 I have asked a similar question to Arjen Lenstra a few years ago: I was investigating three 2048-bit primes of low Hamming weight:$p_1 = 2^{2048} - 2^{1056} + 2^{736} - 2^{320} + 2^{128} + 1p_2 = 2^{2048} - 2^{1376} + 2^{992} + 2^{896} + 2^{640} - 1p_3 = 2^{2048} - 2^{2016} + 2^{1984} - 2^{1856} - 2^{1824} + 2^{1792} - 2^{1760} + 2^{1696} + 2^{1664} +...

14

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

7

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

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

$\{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

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

5

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

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

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

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

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

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

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

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/... 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 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 ... 2 Given an oracle that tells you for any$h\in\mathbb{Z}_{p-1}^\times$if the discrete logarithm$\log_g(h)$is$\ge\frac{p}2$or not, allows you to find$x := \log_g(h_0)$for fixed$h_0$with about$\log_2 p$queries: The query$\log_g(h_0)\stackrel{?}\ge\frac {p-1}2$gives you one bit of information$z_0 := \lfloor\frac{2x}{p-1}\rfloor\in\{0, 1\}$, and you ... 2 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 Miller-... 2 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 ...

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