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$ ...
- 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"...
- 27.8k
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 ...
- 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 ...
- 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 ...
- 48.4k
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 $\...
- 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 $...
- 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 ...
- 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 ...
- 48.4k
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 ...
- 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 \...
- 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 ...
- 23.8k
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)$ ...
- 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$ ...
- 155
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 ...
- 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 ...
- 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 ...
- 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 ...
- 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$,
...
- 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 ...
- 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$ ...
- 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$. ...
- 48.4k
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 ...
- 216
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 ...
- 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; ...
- 2,112
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 $\...
- 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.
- 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 ...
- 5,188
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 ...
- 13k
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible