Talk:RSA problem

Cryptography: Computer science Top‑importance

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
Top	This article has been rated as Top-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as High-importance).

Definition of the problem?

decrypting a message without knowing the recipient's private key, or of finding someone's private key.

Thanks for starting this article! Quick question: are both of the above the RSA problem? I thought the RSA problem was finding a plaintext corresponding to a ciphertext, given the public parameters; and that finding the private key from the public key is not (yet known to be...) an equivalent problem? I was under the impression that the second problem was known to be equivalent in difficulty to integer factorisation, but the first is still an open question? I'm not very au fait with RSA, though, so please put me right if necessary ;-) — Matt Crypto 19:26, 25 Feb 2005 (UTC)

OK, it turns out you're right. The Handbook of Applied Cryptography states the problem thus: "Given a positive integer n that is a product of two distinct odd primes p and q, a positive integer e such that gcd(e, (p − 1)(q − 1)) = 1, and an integer c, find an integer m such that m^e ≡ c (mod n)." So it's just decrypting a ciphertext. However, I wonder if we shouldn't keep in the information about finding private keys. It's relevant to breaking RSA. Also, I'm not sure if finding someone's private key is known to be equivalent in difficulty to integer factorization. The first question (decryption w/o the private key) is definitely an open question. It's not known if there isn't a way of doing it without factoring the modulus. That I'm sure of. Also, it might be worth mentioning that there are some variants of RSA that have been proven to be equivalent to factoring (it's in Schneier). Anyway, sorry about the mistake. Decrypt3 22:19, Feb 25, 2005 (UTC)

There are no such variants on RSA. Perhaps you're thinking of the Rabin cryptosystem. -- ciphergoth 19:07, 2005 Apr 12 (UTC)

uhh

What does RSA stand for?

Its the initials of the protocols authors, see http://en.wikipedia.org/wiki/RSA--Bah23 10:59, 26 January 2007 (UTC)[reply]

Total rewrite

Hope I'm not treading on anyone's toes, but what was there before was pretty much utterly wrong. I've rewritten it to give a more accurate description of what cryptographers mean when they say "RSA problem". -- ciphergoth 19:07, 2005 Apr 12 (UTC)

Once you've got the prime factors...

I know it's then "easy" to come up with the solution once you've got the prime factors of N. However it would be nice if this page stated the equation or method. 99of9 (talk) 05:01, 22 September 2009 (UTC)[reply]

Be our guest! P*Q is a dual prime composite, R*S is a smaller composite that may or may not have one even and one odd component integer (non-prime or prime makes no difference) If the ratio of R to S is very similar to the ratio of P to Q such as in a trivial prime composite 10057, (113 x 89) then the ratio 26:33 is almost the same. 113 x 26 = 2938 * 89 x 33 = 2937. the square root of P*Q*R*S^0.5 = 2937.499957..., THE SQUARE ROOT OF 4 X P*Q*R*S = 5874.99991489..., This is an artefact of one of the Sub-Ratio integers being even. We need to multiply by four, 2938 + 2937 = 5875.

So lets try another random generated trivial dual prime composite:- 448492986412087 A deterministic asymtotic protocol establishes that the Sub-Ratios 2:1, 19:10, 21:11, 223:117 approximates to a similar ratio. 448492986412087 x 223 x 117 = 11701630508477761917 and 11701630508477761917^0.5 = 3420764608.7501785186321174938593 call that 3420764609, 3420764609^2 = 11701630510186922881 and 11701630510186922881 - 11701630508477761917 = 1709160964 = 41342 x 41342, 3420764609 + 41342 = 3420805951 and 3420805951 / 223 = 15339937 3420764609 - 41342 = 3420723267 and 3420723267 / 117 = 29236951

FACTORED! P = 29236951 and Q = 15339937

BTW these two primes spell "BITCOIN'S SECURITY" ie. non existent! , (A = 1, B = 2, C = 3, J = 10 = 1, K = 11 = 2, S = 19 = 10 = 1, etc.)

The deterministic method involves analysis of the square roots of trial sub-ratios. The square roots that are closest to P*S + Q*R will reveal themselves very clearly. Some methods reach a perfect Sub-Ratio almost instantly. RSA-2048 can be factored in the blink of an eye! CAVEAT! — Preceding unsigned comment added by 81.159.184.78 (talk) 01:13, 1 June 2013 (UTC)[reply]

Of course the claims above are incorrect. A method like this has been proposed by Lehman (Fermat's_factorization_method#multiplier_improvement). The method has complexity O(N^(1/3)), and hence is not suitable to factor RSA moduli. (Btw, Bitcoin is based on hash chains and not RSA) 2A02:1205:34DB:D060:8C68:AF3A:FF26:947F (talk) 11:30, 1 June 2013 (UTC)[reply]

Database method

I imagine that for at least 40 years all major governments have secretly been compiling databases of the products of two primes. It would be very very very large, but surely not impossible? If my surmise is correct, finding the prime factors of N would be a 5 minute look-up task (for such a government, though not for you or me). Would that count as a solution of the RSA problem? Apuldram (talk) 10:15, 10 April 2012 (UTC)[reply]

Per the Prime number theorem, the number of 512 bit primes (you need two of them to make a 1024 bit RSA key) is more than 2^500 or 10^150, which is vastly more than the number of atoms in the universe. So what you are suggesting is very very very very very very impossible.--agr (talk) 15:30, 10 April 2012 (UTC)[reply]