Questions tagged [safe-prime]

A safe prime is a prime number of the form 2p + 1, where p is also a prime.

Filter by
Sorted by
Tagged with
5
votes
0answers
68 views

What's the hardest composite for 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. But is there a relationship between safe primes and ...
2
votes
1answer
399 views

Distribution of safe primes generated using different techniques

Is there any difference in the distribution of safe primes generated by creating prime $q$ and testing $2q+1$ for primality, compared to generating a larger prime $p$ and testing $(p-1)/2$ instead? ...
1
vote
1answer
77 views

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

NIST recommends a 256-bit private key exponent for DLP with a 3072-bit modulus. From this answer it appears that the range of private key numbers is derived by calculating a prime modulus via $2⋅p$ ...
3
votes
1answer
127 views

Elgamal problem on $\mathbb{QR}_p$ with $p$ a safe prime

I need some orientation to solve the following problem: Let $p = 2q+1$ be a safe prime and $s(x)$ the smallest of the two square roots of $x$ modulo $p$. Then: Determine the distribution of $s(g^{ab}...
5
votes
2answers
556 views

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

A prime $p$ is said to be safe prime if $(p-1)/2$ is also a prime. How to efficiently generate a safe prime? I have written the following code in sagemath which generates a random safe prime of 1536 ...
4
votes
1answer
245 views

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

The complexity of solving the discrete logarithm problem depends on the choice of the group $G$. A popular choice is $Z_p^*$ where $p$ is a safe prime (${p=2p' +1}$ and $p'$ is also prime). In this ...
2
votes
1answer
216 views

Efficient algorithm for finding Sophie Germain primes

What's the industry standard for an efficient finding large Sophie Germain primes? As a part of request handling in my application, I need to generate Paillier key. My current approach is to ...
5
votes
1answer
91 views

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

Given $p$ a prime, $g$ generator of $\Bbb Z_p^*$, and $h\in\Bbb Z_p^*$, that uniquely defines some $z\in[0,\varphi(p)[$ such that $g^z\equiv h\pmod p$. Is it possible to determine in polynomial time ...
2
votes
1answer
727 views

How to generate safe primes in a verifiable way?

FIPS 186-3 (APPENDIX A: Generation and Validation of FFC Domain Parameters) specifies how to generate Finite Field Cryptography Domain parameters and how to perform an explicit domain parameter ...
-3
votes
1answer
84 views

Are there stenography benefits to a “n-prime”?

As mentioned in this StackOverflow CodeGolf question, prime numbers can be redefined: One of my favorite definitions of the prime numbers goes as follows: 2 is the smallest prime. ...
1
vote
1answer
344 views

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

Here: http://safecurves.cr.yp.to/ , I read that the NIST P-256 elliptic-curve is not safe. The article lists several aspects (off-curve point, side-channel, etc.) where implementing P256 can fail the ...
7
votes
1answer
690 views

When to use safe prime or Schnorr group

Protocols that use $\mathbb{Z}_{p}^*$ arithmetic often choose $p$ to be a safe prime ($p = 2q + 1$, for prime $q$) or to have the Schnorr group form ($p = rq + 1$, for prime $q$). I understand that ...
10
votes
1answer
1k views

Safe primes in RSA

It's my understanding that there's no longer a requisite of safe primes for $q$ and $p$ when choosing a RSA modulus. How is it that this does not change the hardness of factoring $N$?
3
votes
1answer
1k views

Unsafe prime in DH key exchange

How the use of unsafe prime in DH key exchange makes DH vulnerable to be broken? can anyone explain to me what is safe prime, and what is the difference between safe and strong prime? How the attacker ...
2
votes
1answer
201 views

How is it possible that $g^q \equiv 1 \pmod p$ for a generator g?

The context of this question is coming up with the parameters for the ElGamal encryption scheme. One of the requirements for the parameters for ElGamal is that we have primes $p$ and $q$ such that $p ...
1
vote
1answer
350 views

ssh-keygen DH Primality Testing

I'm pretty familiar with using ssh-keygen to create groups that go in the /etc/ssh/moduli file for the Diffie-Hellman Group Exchange in openssh. Reading over the man page, it says "By default, each ...
1
vote
0answers
245 views

Solving discrete logarithm when p is not a safe prime

If you have the cyclic group of integers modulo $p$, where $p$ is not a safe prime, as well as a generator $g$ with which for all factors $q$ of $(p-1)$, $g^{(p-1)/q} \ne 1$, This answer says that ...
2
votes
1answer
1k views

About Primitive roots mod n in Diffie-Hellman [duplicate]

I'm on the study of Diffie-Hellman and its related math (multiplicative group of integers $\mod n$). In some crypto papers and documents I've read that $g$ needs to be a primitive root mod $n$ ($g$ ...
0
votes
1answer
210 views

Of what use is my code for finding prime numbers of a certain size? [closed]

I've developed a bit of Mathematica code that can find primes within a range of numbers. For example, if I wanted all the primes between one million and two million, it could do that. Of what use is ...
1
vote
1answer
349 views

Why is factoring $p-1$ easy when $p$ is a safe prime?

A paper states: [...] $(p,g,y)$ is a correct ElGamal public key if $g^x=y\pmod p$. To verify this the order of $g$, and thus the factorization of $p-1$, is needed. This is easy for safe primes (i.e....
1
vote
1answer
692 views

ElGamal and Schnorr groups

As I gather, a normal practice for choosing a cyclic group for ElGamal key generation is to find a safe prime $p$ and use a multiplicative cyclic group with modulus $p$ and order $q = (p-1)/2$. ...
5
votes
3answers
2k views

Finding strong primes

Wikipedia lists the following conditions for a prime to be strong: $p-1$ has large prime factors. That is, $p = a_1 q_1 + 1$ for some integer $a_1$ and large prime $q_1$. $q_1-1$ has large prime ...
3
votes
2answers
2k views

Sophie Germain primes and safe primes

I am trying to find a list or table of safe prime numbers i.e. the ones that are based on the Sophie Germain primes i.e. $N = 2p + 1$ where $p$ is also prime. All I found till now is this database. ...
7
votes
1answer
325 views

Malicious DH groups

Can an attacker construct a DH group, large enough to be considered secure (say, a modulus of 2048-bits), such that the group appears safe, but the attacker is able to solve the DLP in the group ...
3
votes
1answer
610 views

Generator for Group $QR_{N}$

Let $N=PQ$, where $P=2p+1$ and $Q=2q+1$. $P,Q,p,q$ are prime numbers. $QR_{N}$ is the set of quadratic residues modulo $N$. Please help me to prove $QR_{N}$ is a cyclic group. Note: $QR_{P}$ and $...
4
votes
4answers
1k views

Why $n=pq$ with $p=2p'+1$ and $q=2q'+1$ instead of just $n=p'q'$ for RSA crypto?

For RSA cryptography, we know that the modulo $n$ is a product of two big prime numbers(say $p$ and $q$). However, in some documents I see an extension of $p=2p'+1$ and $q=2q'+1$ with $q'$ and $p'$ ...
3
votes
1answer
1k views

Why does openssl BN_generate_prime return only a fraction of the safe primes within the given bit range?

I went into prime generation issues the last week and eventually calculated 10^7 primes using erik tews safeprimegen python wrapper for openssl. (https://github.com/eriktews/gensafeprime) (System: ...
2
votes
1answer
261 views

Selecting a large NUMS Safe prime

Suppose I want to use the following simple hash function. For a mesage $m$, take some public $a$ and prime $p$ and raise $a^m \bmod p$ (never mind the computational expense of this operation). This ...
1
vote
1answer
195 views

Can one detect if two pairs of elements in Zp have the same exponential relation?

Suppose that $p$ is a safe prime of 2048 bits ($p = 2q + 1$, and $q$ is prime). Suppose that one is given two pairs $(x_1, y_1)$ and $(x_2, y_2)$ such that: $y_1 = x_1^{r_1} \pmod p$ $y_2 = x_2^{r_2}...