Tag Info

Hot answers tagged

9

Actually, that was proposed here back in 1998 (sorry, an electronic version of the paper does not appear to be on the web) -- the author claimed a modest speedup in the private operations. However, that speed up would appear to be about the same if you just did "multiprime RSA", that is, selected an RSA modulus of the form $pqr$ for three distinct primes ...


8

There's no real difference between $p$ and $q$ in RSA. It looks like OpenSSL just has the agreement "$p$ has to be bigger than $q$" for conveniences. One of the numbers has to be bigger than the other (otherwise they would be the same number, and $p = q$ is very bad in RSA). Just use two examples: $p = 13$ and $q = 11$. $p$ is bigger than $q$, all right. ...


6

A possible RSA variant uses: some odd exponent $e>2$ (that can be $e=3$ or $e=2^{16}+1$ as customary in standard RSA); $p$ and $q$ distinct large random primes, with $\gcd(e,p)=\gcd(e,p-1)=\gcd(e,q-1)=1$; $N=p^2\cdot q$; some $d$ computed such that $d\cdot e\equiv 1\pmod{\operatorname{lcm}(p,p-1,q-1)}$; public-key function $x\to x^e\bmod N$; private-key ...


6

To make it easier for humans to read.


5

The only reason you are seeing this is because you are dealing with such small primes. With primes like we would use in practice (1024 bits), the probability of this happening is very, very small. And, it can only happen when $e>\sqrt{\lambda(n)}$. Since we typically use $e=65537$ in practice, it is guaranteed to not happen. Anyways, there is no mistake ...


5

Yes, what you have is enough to recover p in both cases. In the first case you just need to write the proper equation to be then solved thanks to Coppersmith method to find small roots of univariate polynomial. As explained by Alexander May in pages 40 and 41 of his thesis what you ask is always doable if the unknown bits are consecutive (and you have at ...


4

Adi Shamir's secret database of all primes is to cryptography venues what the Dahu is to French summer camps. For why, see the answers to this related question. The three other future work items in the quoted presentation are in the same vein (Breaking RSA-1024 with Fermat factoring; Breaking RSA-1024 using $1024 = 2*2*2*2*2*2*2*2*2*2$; Breaking RSA-1024 ...


2

What happens if I choose $e=3$? Can I retrieve the message by simply calculating $\sqrt[3]{c}$? Yes, if the plaintext message is smaller than $\sqrt[3]{N}$, then yes, a simple computation of $\sqrt[3]{C}$ will recover the original message. Why can't I do that with bigger $e$'s? Actually, you could... as long as the plaintext message is smaller ...


2

Well, hope that it's not late for this answer. Because it was yesterday that I encountered this problem and I'm new to this wonderful website. According to your description, and as far as I know, this protocol meets your demands very well. First, it works with RSA as you have mentioned in the second paragraph. The original version of this protocol is ...


1

I do not know why the OpenSSL implementation specifically does this. However, a branch-less (constant time) implementation of the RSA private key operation, might be slightly more efficient if the parameter $c = q^{-1} \bmod p$ is calculated for $p$ being the greatest prime of the two. Otherwise the value of $J_q = I^{d \bmod q-1} \bmod q$ has to be taken ...


1

In practice, one can use openssl to extract the information: $ cat pubkey.txt -----BEGIN PUBLIC KEY----- MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0 FPqri0cb2JZfXJ/DgYSF6vUpwmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/ 3j+skZ6UtW+5u09lHNsj6tQ51s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQAB -----END PUBLIC KEY----- $ openssl ...


1

RSA key formats are defined in at least RFC 3447 and RFC 5280. The format is based on ASN.1 and includes more than just the raw modulus and exponent. If you decode the base 64 encoded ASN.1, you will find some wrapping (like an object identifier) as well as an internal ASN.1 bitstring, which decodes as: ( ...


1

It would probably work: RSA with composite numbers But it would be better to just choose 2 larger primes instead of reusing the same prime twice.



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