-2
$\begingroup$

If someone had a very efficient RSA factoring algorithm, would a company or government entity be willing to purchase it? What factoring time would be considered fast, months, days, hours, minutes? After they factor it, what do they do with the 2 primes numbers?

$\endgroup$

3 Answers 3

2
$\begingroup$

Yes, almost any improvement on state of the art factoring is monitizeable.

Small improvements will probably not be worth a lot of money. But an algorithm which can factor commonly used 2048 bit keys practically would be worth a ton of money. Even if it takes a month using 1 million dollars worth of hardware there will still be those interested in paying.

If the solution is faster and scaleable it is even more valuable. The better solutions are so valuable you need to be careful about your security and keeping it safe while trying to sell. Selling quickly to your country is a safe option. An open bidding war may not be safe.

A working implementation and breaking a public challenge will easily prove credability.

Many would argue the moral thing to do is to publicly publish a broken challenge and let the world know RSA is broken. claiming fame in the process.

$\endgroup$
3
  • $\begingroup$ Historically, the Enigma code could usually be cracked within 24 hours, and it had the bonus that cracking the daily code allowed you to decipher all messages sent on that day, not just one. One problem today is that for example there might be 1000 messages be sent every day from A to B, each with its own RSA code, and if you know that one of these 1000 is very valuable but not which one then suddenly the cost is 1000 times higher. $\endgroup$
    – gnasher729
    Commented Jan 9 at 18:17
  • 1
    $\begingroup$ If you break a single message you will want it to be cheap, but there are plenty of RSA keys used for signing, if you could factor those, it could be very significant. $\endgroup$
    – Meir Maor
    Commented Jan 11 at 8:18
  • $\begingroup$ Didn’t think about that. Yes, if I sign one completely irrelevant message with my private key, give you the public key so you can check it, and then you crack my private key then you can send any number of messages that look as if they were signed by me. A clever attacker could create a lot of damage. $\endgroup$
    – gnasher729
    Commented Jan 11 at 19:44
1
$\begingroup$

To add to the perfectly fine other answer:

  1. Your question "how long must it take" depends on the computing power you have, and can only be answered in the context of specific hardware and how much your budget is. If the breakthrough method is enough of an improvement it will be worth it to implement it and optimize the method for repeated use.
  2. "What do they do with the two prime numbers?": In a typical case, if the primes $p,q$ came from an RSA modulus $N=pq,$ which is in use as a certificate in a PKI, then that means the attacker can compute the private key, and efficiently impersonate the legitimate entity posessing that RSA certificate. They can sign documents pretending to be the legitimate entity, or break into communications which are performed using that certificate as an authentication mechanism.
$\endgroup$
1
$\begingroup$

There may be secrets protected by RSA that would be worth a million dollars to uncover. But there’s a problem: If I sent out ten encrypted messages, and you don’t know which one contains the valuable secret, you might have to crack all ten.

And you would have to keep this all absolutely secret: Otherwise people will stop using RSA for very valuable secrets. Or everyone just doubles the RSA bits. How does your algorithm handle it?

$\endgroup$
3
  • $\begingroup$ How does my algorithm handle it? I made a post on math stack exchange a while back, so it'll be something like this: math.stackexchange.com/questions/4785947/… My workstation only has 14 cores so I'm working on a supper efficient and fast algorithm. If successful, I plan on cracking all of the 31 remaining RSA challenges on the Wikipedia page in a weekend... to draw attention. I would never publish it. Hoping to get a few bucks for it. $\endgroup$
    – steveK
    Commented Jan 8 at 3:03
  • $\begingroup$ Good luck. Followed that link. What is the largest semi prime you have factored? $\endgroup$
    – gnasher729
    Commented Jan 8 at 21:21
  • $\begingroup$ Nothing significant (up to 32 digits) because I'm designing a new algorithm not based on root finding or sieves. Mine is a modified genetic algorithm containing a cost function that allows me to know which direction I'm moving on the real number line. No integers here until I hit the solution. It has the capability to know when it's getting closer or farther away from $P$. The size of $N$ dictates various parameters so it's scalable, as I want the Big-O runtime complexity to be flat and independent of the size of $N$. I want it to run on a single desktop Workstation PC. $\endgroup$
    – steveK
    Commented Jan 9 at 5:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.