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
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]

Logarithms proved to be a useful tool when it came to performing calculations in astronomy. Why not use them to decrypt RSA? I have some example code available at https://github.com/Dwhite2468/PrimeFactorization 74.96.36.175 (talk) 18:54, 19 November 2024 (UTC)[reply]

^^^^ An improved version of the above source code is available at https://github.com/ArunAsur/Washerman. I removed the references to logarithms, which can be computationally expensive, and replaced them with algebraic formulas to speed up the multiplication process. 2600:4040:228D:6800:513B:51A5:1EF8:C6F6 (talk) 22:47, 24 August 2025 (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]

Algorithm for Public Download

Here is an algorithm for factoring a prime number in O(Nlog(N)) time:

Methods for Factoring Integers Commercially-available cryptosystems such as RSA rely on the fact that factoring a product of two prime numbers is computationally intensive unless one uses a quantum computer. The purpose of this paper is to demonstrate that the process of factoring a large semiprime number can be sped up by using algebra to reduce computation times. A program resulting from the findings of this paper is available for public download on Github (http://www.github.com/ArunAsur/Washerman). It is distributed under the GNU Public License, which means users can modify it as they please. An example of a semiprime number is 2077, which is the product of the prime numbers 31 and 67. Its binary representation is 1000 0001 1101. Whereas decimal arithmetic provides a number of different rules for determining whether a number is divisible by another (such as adding up the digits to see if the sum is a multiple of 3 for divisibility by 3, or checking to see if the last digit is even for divisibility by 2), similar rules do not appear to exist for larger numbers. Therefore, finding the prime factors of a number would require checking several prime numbers one at a time to see if one divides evenly into the product. One way to improve upon this method would be to rewrite the product of primes as a sum of several geometric series:

S = 1000 0001 1101 = 2^11 + 2^4 + 2^3 + 2^2 + 2^0 = 2^11 + Σn=2,4(2^n) + 2^0 = 2^11 + 2^2(1-2^3)/(1-2)+ 2^0 = 2^11 + 2^2(2^3 – 1) + 2^0

Note: In the Github program, gaps betweens the sums that are 1 bit in width are ignored, so S would be represented as two geometric series instead of three (2^11 + 2^0(2^5 – 1)). The process of finding the prime factors of S still involves dividing it by each prime number to see if the resulting remainder is 0. However, the division step can be sped up by multiplying the series sums instead of the individual bits. This is represented in the Github program by the class BinaryPrime, which contains a list of BinaryRegion objects that represent each continguous region of “1” bits in the binary representation. For example, the prime number 31 is represented in binary as 11111. Dividing by 31 would be the equivalent of multiplying by 1/31, which in binary is represented as 0.00010000100001.... The improved division process will therefore multiply the dividend by the repeating sequence of bits in the divisor. As stated previously, the multiplication is performed using geometric series sums to represent the binary regions:

S/31 = (2^11 + 2^2(2^3 – 1) + 2^0) * 2^-5 = 2^6 + 2^-3(2^3 – 1) + 2^-5

After performing the division, one gets a new binary prime with the individual series sums shifted right by 5 bits. Converting this value back to its original form gets the number 0100 0000.1110 1000, which is equivalent to the decimal number 64.90625. This value does not equal the actual division result, which should be 67. This is because the remaining bits of the binary reciprocal (0.00000000100001...) were left out of the division. They can be factored back into the division process by representing them as an infinite geometric series:

R = 2^-10 + 2^-15 + 2^-20 + … = 2^-10/(1 – 2^-5) SR = 2077(2^-10/(1 – 2^-5)) = 2077(0.001008) = 2.09375

By adding the remainder term back into the quotient, one gets the second prime factor, 67. The above improvements to the division algorithm can allow programmers to check for divisibility in less time than if they used conventional division methods. 2600:4040:228D:6800:558E:776F:C273:3A66 (talk) 15:45, 30 August 2025 (UTC)[reply]