# Tag Info

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

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

### 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.5k
Accepted

• 1,568
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
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.5k

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

• 1,568

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