Skip to main content
17 votes

Safe primes in RSA

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$ ...
SEJPM's user avatar
  • 46k
14 votes
Accepted

How to efficiently generate a random safe prime of given length?

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"...
Yehuda Lindell's user avatar
7 votes
Accepted

why to use a safe-prime in Diffie-Hellman key exchange?

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 ...
poncho's user avatar
  • 147k
7 votes

DDH hardness with shared public parameters

For a given size of $p$, random $p$ are believed safer than $p$ chosen by an adversary, at least w.r.t. the state of the art in computing Discrete Logarithms (which is enough to break DDH). This is ...
fgrieu's user avatar
  • 141k
7 votes

How to generate safe primes in a verifiable way?

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 ...
Squeamish Ossifrage's user avatar
6 votes
Accepted

Complexity of solving the discrete logarithm problem for the group formed from product of 2 safe primes

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 $\...
poncho's user avatar
  • 147k
6 votes

How to efficiently generate a random safe prime of given length?

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 $...
j.p.'s user avatar
  • 1,568
6 votes
Accepted

When to use safe prime or Schnorr group

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 ...
poncho's user avatar
  • 147k
6 votes
Accepted

Distribution of safe primes generated using different techniques

$\{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 ...
Squeamish Ossifrage's user avatar
6 votes

DDH hardness with shared public parameters

Even if we have no adversary picking the prime, a fixed public prime used often can be an issue. The time to break DH can be mostly shared across multiple instances of the problem with the same public ...
Meir Maor's user avatar
  • 11.8k
6 votes

Optimize the speed of a safe prime finder in C

The first obvious thing to do is quickly reject those values where either $q$ or $2q+1$ are obviously not prime. For example, suppose you code sends the time to pick a prime $q$, where $q \equiv 1 \...
poncho's user avatar
  • 147k
5 votes
Accepted

Finding large devious primes

The issue with using Chernick's expression $(6k+1)(12k+1)(18k+1)$ and its generalisations is that the number is always congruent to 1 mod 3 so that twice the number plus one is divisible by and hence ...
Daniel S's user avatar
  • 23.9k
5 votes
Accepted

Prime numbers of the form $(2^k)p+1$, for a given prime $p$

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)$ ...
fgrieu's user avatar
  • 141k
4 votes

Unsafe prime in DH key exchange

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$ ...
E. Postlethwaite's user avatar
4 votes
Accepted

Does choosing N to be product of safe primes avoid William's p+1 factoring attack on RSA?

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 ...
poncho's user avatar
  • 147k
4 votes
Accepted

List of big strong primes

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 ...
fgrieu's user avatar
  • 141k
4 votes

Optimize the speed of a safe prime finder in C

Preliminary note: in practice it's often used one of the safe primes given in RFC 3526. Or/and it's often wanted some additional criteria (e.g. $2^{(p-1)/2}\bmod p=p-1$, some number of high or/and low ...
fgrieu's user avatar
  • 141k
3 votes

Prime numbers of the form $(2^k)p+1$, for a given prime $p$

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 ...
poncho's user avatar
  • 147k
3 votes

Inverse function of RSA and safe prime requirement of DH Key exchange

One possible statement of the Discrete Logarithm Problem modulo prime $p$ (the one used in practice in DSA, and more generally when working in a Schnorr group) goes: given large random prime $q$, ...
fgrieu's user avatar
  • 141k
3 votes

How to get the order of a group generator in DH?

To extend kelalaka's answer, if $p$ is a safe prime (that is, if $p = 2q+1$ with $q$ prime), then: If $p \equiv 7 \pmod 8$, then the order of $g=2$ will be $q$ If $p \equiv 3 \pmod 8$, then the ...
poncho's user avatar
  • 147k
3 votes

What is the best strategy to avoid getting even orders in Shor's algorithm?

I do understand Shor's algorithm wants the order of an element to be even so that it can use the factoring identity and find a non-trivial factor. Not really; to factor, all you need is a value $e$ ...
poncho's user avatar
  • 147k
3 votes
Accepted

How is the recommended NIST modulus for DLP chosen/calculated?

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$. ...
Squeamish Ossifrage's user avatar
3 votes
Accepted

Are there stenography benefits to a "n-prime"?

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 ...
user2233709's user avatar
3 votes
Accepted

Efficient algorithm for finding Sophie Germain primes

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 ...
poncho's user avatar
  • 147k
3 votes
Accepted

DHKE: Why using safe prime gives us "safe" subgroups?

An element $x$ has order 1 or 2 if and only if it satisfies the equation $x^2=1$. In a field (which $\mathbb{Z}/p\mathbb{Z}$ is when $p$ is prime), an equation of degree $d$ has at most $d$ solutions; ...
Mehdi Tibouchi's user avatar
2 votes

Checking if discrete logarithm is $\geq\frac{\varphi(p)}2$ in polynomial time?

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 $\...
j.p.'s user avatar
  • 1,568
2 votes

How to interpret the article claiming NIST P-256 curve to be unsafe?

Quoting CodesInChaos: P256 is secure, it just lacks some nice-to-have features that make writing a fast and secure implementation easier.
e-sushi's user avatar
  • 17.9k
2 votes
Accepted

Safe primes and subgroups

The Decisional Diffie-Hellman assumption, on which the key-exchange would be based on does not hold in $\mathbb{Z}_q^*$. The reason is that the Jacobi symbol "leaks" information about the ...
ckamath's user avatar
  • 5,208
2 votes
Accepted

Constraints on q for q-ary lattices?

As Hilder mentions, via the technique of "modulus switching" the particular choice of $q$ does not matter much for the security of LWE. Therefore, the particular form of $q$ is mostly to ...
Mark Schultz-Wu's user avatar
2 votes

Constraints on q for q-ary lattices?

Not a complete answer, but may already be useful... It is known that only the bit length but not the form of $q$ is important for the security of the LWE (and the RLWE) problem. Moreover, if we can ...
Hilder Vitor Lima Pereira's user avatar

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