Skip to main content
Cryptography

Questions tagged [safe-prime]

Ask Question

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

53 questions
Newest Active Bountied Unanswered
1 vote
2 answers
383 views

My algorithm's latest run found 5 (4096-bit, 1233-digit) safe or Sophie Germain primes in 6 hours and 59 minutes, after 11,190,811 attempts. It doesn't use any libraries, public or otherwise—just a ...
Arkady's user avatar
  • 17
1 vote
0 answers
113 views

Consider we have a large integer $n=pq$ with both $p$ and $q$ safe primes(i.e. $p=2p'+1$ $q=2q'+1$), we also select and element $w \in Z^*_{n}$ such that $|w|=\varphi(n)/4=p'q'=n'$, we also select a ...
Satoshi's user avatar
  • 121
1 vote
1 answer
90 views

Let's create an example with safe primes, suppose we have a group Zp* (operation is multiplication), and where p=23, q=11 and g=2. Then group elements are {1 2 4 8 16 9 18 13 3 6 12}, so there are ...
Azii's user avatar
  • 129
2 votes
3 answers
397 views

There are some very large safe primes listed here: https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes Would using any of them result in a secure DH construction? Generator is 2. The exponent ...
user avatar
0 votes
2 answers
551 views

Do Safe and Sophie Germain primes maintain a relatively stable distribution as numbers get larger, or do they become rarified beyond a predictable value? This is important in one area of triangular ...
Zekchelovek's user avatar
  • 7
1 vote
1 answer
496 views

I come from the question here: Safe primes subgroup in Diffie–Hellman key exchange Where the accepted answer states that there are only 4 possible outcomes for the order of a subgroup when using a ...
Ymi's user avatar
  • 175
0 votes
1 answer
287 views

I'm trying to understand how the safe primes numbers are used in Diffie–Hellman key exchange. According to wiki: The order of G should have a large prime factor to prevent use of the Pohlig–Hellman ...
pacman's user avatar
  • 491
4 votes
2 answers
1k views

I am trying to implement the Schnorr’s identification protocol in C. I need a safe prime in order to be able to find a generator of the cyclic group efficiently. The problem is that my program takes ...
Prankster2k's user avatar
  • 41
5 votes
2 answers
464 views

DDH is believed hard for subgroup of $ℤ^*_p$ with order $q=(p-1)/2$ when $p$ is a safe prime chosen randomly. What if $p$ isn't random: When parameters are shared, $p$ mightn't have been chosen ...
bs-'s user avatar
  • 83
2 votes
1 answer
121 views

Consider the following case, given x(private key) and y(public key), how to determine whether this key pair is generated by a pre-defined Safe Prime Group(Say FFDHE, RFC 7919)? In context of SP800 ...
gx16's user avatar
  • 45
1 vote
0 answers
48 views

In the paper describing a protocol for distributed RSA modulus generation, Diogenes, "[they] employ a special-purpose $\Sigma$-protocol based on [Sho00] for proving correctness of exponentiations ...
Nic's user avatar
  • 518
6 votes
1 answer
370 views

Call a prime $p$ devious if $(p-1)/2$ is a Carmichael number. They are called devious since they superficially look like safe primes but are not. In particular, Diffie-Hellman using such a prime could ...
John Coleman's user avatar
  • 362
2 votes
2 answers
318 views

In lattice cryptography, people often work with q-ary lattices so that we can use the hardness of short integer solution (SIS) and learning with errors (LWE). I saw in some notes that sometimes we ...
Karim's user avatar
  • 155
2 votes
1 answer
348 views

Ok so the inverse function of RSA encryption (that is decryption) is $ m \gets c^{d}\bmod N$ where $d$ is the secret exponent As I understand the hardness of RSA depends on two things: the Integer ...
Adeel Malik's user avatar
  • 23
1 vote
2 answers
1k views

For a DH parameter prime, if the generator $g$ is 2, how do I get the order $q$?
obvionaoe's user avatar
  • 13

15 30 50 per page
1
2 3 4