Tag Info

Hot answers tagged

7

In RSA as usually practiced (encryption or signature per PKCS#1, signature per X9.31, ISO/IEC 9796-2, FIPS 186), it is NOT necessary, or even common, to require $n=p⋅q$ with $p=2⋅p′+1$ and $q=2⋅q′+1$ with $p'$ and $q'$ huge primes, as stated in the question. IF that's done, it ensures that: any small odd $e>2$ (including the common $e=3$ and $e=65537$) ...


6

Safe primes (that are two times a prime plus one) and strong primes were at some point in time considered sensible. One reason was that safe primes ensures that Pollard's $p-1$ factoring algorithm stops working. However, safe primes are not enough. There are other related factoring algorithms, such as the $p+1$ method, and strong primes also stop them. The ...


5

Actually, there are also other reasons why one wants to use safe primes in the RSA setting (when working with hidden order groups in cryptographic protocols). When choosing the RSA modulus $n=pq$ to be the product of safe primes $p=2p'+1$ and $q=2q'+1$, then we also have the following: The subgroup of $Z_n^*$ of qadratic residues is cyclic and has order ...


3

The smallest safe prime you got from OpenSSL was 3221226167 = 0xC00002B7. The largest was 4294967087 = 0xFFFFFF2F. This makes me hypothesize that OpenSSL is setting the two high bits to one, and choosing the rest of the bits randomly. If that is accurate, that would explain the range of primes you did. As far as why you found many more safe primes in the ...


3

Well, the obvious answer to 'how to find a Safe prime that is also a Nothing-Up-My-Sleeve' number would be to take one of the primes listed in RFC 3526. These primes (which come in several sizes) are all of the form $p = 2^n - 2^{n-64} - 1 + 2^{64} \cdot ( \lfloor 2^{n-130} \pi \rfloor + i )$, where $i$ is the smallest nonnegative integer such that both $p$ ...


3

This is another way of expressing the decisional Diffie-Hellman problem. This problem is more typically written as 'given $g,\ g^a, g^b, g^c$, does $g^{ab} = g^c$?'. As for the difficulty of this problem, it is believed to be difficult as long as you stay within a large prime subgroup; in this case (because you specify a strong prime), you means that you ...


2

Well , I think DrLecter's great answer in here can be used to answer this question indirectly. But as you want to prove so I will give a proof. To prove $QR_N$ is a cyclic group, first, you have to know the order of it. In fact, the order of $QR_N$ is $pq=\phi(N)/4$($\phi$ is Euler function ).Actually, we can show this with the help of this map:$$x\to ...


2

The $p = 2p' + 1$ refers to safe primes as related to strong primes and enhances the difficulty of the discrete-log problem. This makes for a more secure system since they are more difficult to factor. It's like a prime on top of a prime, etc…



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