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


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

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

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


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

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$ such that $x^e \equiv 1 \pmod{N}$ a nontrivial fraction of the time (and practically it would be sufficient if it holds with probability $2^{-30}$ for random $x$)...


1

$P[s(g^{ab}) = i] = \frac{q-1}{q^2}$ if $i \neq 1$ and $\frac{2q-1}{q^2}$ if $i = 1$. We assume that $g$ is a generator of $\mathbb{QR}_p = \mathbb Z_q$. Then, as you said, in order to study the probability that $g^{ab} = i = g^c$ for a fixed $c$, we can calculate the probability that $ab = c\bmod q$. In general, the probability that a random pair $(a,b)\...


1

Beyond the existing answers, any clever selection of $p$ is problematic. If we use a special $p$ and it is reused widely, an attacker can attack all of them together. Most of the work in calculating Dlog only depends on the public paramaters and not on the individual value we are trying to get the discrete logartithm of. We even have reason to believe the ...


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