I might avoid telling anyone that my brain carries a superweapon, but I also might put three or so of the RSA challenge numbers in an anonymous letter to someone at the NSA and the chair of the Mathematics department at Harvard saying that I'd appreciate if they could spare a room for a potentially interesting lecture in 3 years.
Another option is pastebinning an innocuous message signed with private keys of an implausibly diverse collection of sites and then dropping a link to that in front of a large audience including at least one person who could understand what big of a deal it was.
Either of these is a multi-billion dollar firecracker, of course.
I'd call the NSA and ask for them to clear my name, a winnebago, a european (+ Tahiti) vacation, a uzi-carrying girl's phone number, and peace on earth and goodwill toward men.
I would send Bruce Schneier (or some other security expert) and encrypted message containing a good part of their private key, to convince them I was for real, then have them decide what to do.
Just because I've figured out the math of factoring large numbers, doesn't mean I'm qualified to make the non-mathematical decision of how to handle that information.
If you wanted to be really evil you would send the message and make it look like it came from your worst enemy. I would imagine that it would only be days before they became intimately familiar with the phrase “extraordinary rendition”.
Is the logic of this decision to protect yourself, or to preserve the status quo? If protection, wouldn't the logical decision be to make a full public disclosure and go out of one's way to make it clear that there is nothing more to disclose? In that way, you remove the reason for someone to attack you (unless they are vengeful), as you are no longer "part of the equation" (boom, boom).
How are you going to be able to prove you know nothing more if you publicly disclose this information?
There are plenty of powerful people who might think that if you can do this imagine what else you can do. Since you can’t prove that you don’t know anything more it is very risky to tell anyone. Best to keep your mouth shut and let the world know when you are dead.
Openly revealing how to factor large numbers without at least months of notice would definitely lead to many people getting stolen from. I'd bet it would also lead to people being killed, but possibly would save more lives than it cost; too complicated to resolve. So even if the responsibility is indirect, it's there.
Yes, I'd publish either right away or after a short delay to allow especially important websites to revoke RSA certificates. (I'd ask some better-informed cryptographers which is best.)
Perhaps you're thinking that you could make huge $$$ breaking into computers with it. Not really. There are already ways of breaking into many webservers and stealing info and crooks already do this, so we know how profitable / risky it is: not very / very.
I'm not so sure, unlike other vulnerabilities we talk about here as being nearly worthless (things against facebook, etc) this would take a serious amount of effort to protect the internet against and have a very long tail of patching. I would bet that you could get a pretty penny selling it. To either a state agency or a large criminal enterprise.
There's a movie called Travelling Salesman about a group of computer scientists who successfully prove P=NP for the NSA or whoever and the whole movie is them debating what to do with their discovery. It's not great, not bad, but it's worth watching if that kind of thing interests you.
IMHO, Traveling Salesman was awful enough to poison a really interesting and underexplored cinematic well. :( It left me wanting both my mental and IP bandwidth back.
All I could think about was how great it would be if someone like Shane Carruth (Primer, Upstream Color) had written/directed it instead.
Yep, being open and sharing this information via a paper or papers, slide decks and videos would help the science, engineering and technology fields advance faster than anyone thought possible.
Though, the full details would more then likely need to be delayed until higher end security improvements could be created. Maybe having the top in mathematics, especially cryptography, quantum mechanics work on creating more secure algorithms to be used.
I'd put the factors of all outstanding RSA numbers in an arXiv paper, cc'd to my lawyer and several trusted friends, and announce the release of the algorithm on Github in a week. If the solution was a device, then blueprints/quantum circuits/etc.
What I'd do next -- and whether I'd release it -- depends on the public reaction. My first priority would be to light a fire under as many asses as possible, but without hurting anyone.
There was once a man called John Titor, who turned up on bulletin boards claiming to be a time traveller. He presented elaborate documentation to back his case, including photographs of his time machine, his uniform, detailed operations manual and tools for maintaining the machine. He even showed light bending around the singularity used to power the machine. He even gave a convincing explanation of how the machine worked. He fooled a lot of people, but most people never heard of him and most of those who did believed it was a hoax.
Convincing a bunch of people you can factor large numbers isn't that hard. And there have been many claimants. But there are security researchers out there that publish lists of numbers to factor of various sizes, including ones (only) they know the factors of, and ones no one knows the factors of.
However, consider what happens if you convince a small number of people you really did it. Most people will either disbelieve it until their bank accounts are emptied, or they will believe it to be no more important than any other security breach.
There are three main groups of people who would understand what it meant. The first are mathematicians who would want to understand the factoring method to push forward their research. The second are Governments and large corporations who depend on factoring for security. The third group are hackers who would want to use it to steal secrets and money.
The second and third group probably wouldn't have your best interests at heart. And many of the first group are working for the second group. So pretty much you should boast about it on conspiracy forums and the like and tell people who don't necessarily understand your accomplishment. At least you'll get a Wikipedia page and people will remember you after you disappear.
Yes, I would tell everybody because I'm a computational number theorist and (1) such an algorithm would also be very useful for many other algorithms in algebraic number theory, e.g., computation of rings of integers of number fields which requires factoring discriminants, and (2) whatever amazing insight led to the algorithm would probably also open up many new research directions in computational number theory, just as past progress on integer factorization has done (my thesis advisor Hendrik Lenstra introduced the groundbreaking elliptic curve factorization technique, telling the world in research papers and beautiful lectures). That said, sadly I'm not optimistic that there exists a fast non-quantum algorithm to factor large composite integers. It may simply be a hard problem.
But you could at least give advance warning. Let people in the right places know things are fundamentally broken, have them, as someone else said, revoke certificates, and other similar ways to prevent it from being absurdly catastrophic while we try to replace it.
If you found out, someone else almost certainly will as well.
Most cryptographic methods rely on factoring being computationally difficult. The outcome of this would be the near-total compromise of modern cryptographic methods, i.e. the backbone of the internet would fall out.
No, RSA depends on factoring. Virtually nothing else does, although the conventional discrete logarithm might be related to factoring.
If RSA was broken, we'd deprecate RSA and move to elliptic curve. Continual advances in factoring and index calculus are in fact the reason we deploy elliptic curve in the first place. Almost every mainstream browser handles it fine.
No matter what happens with factoring, we should all be transitioning away from RSA anyways.
RSA is in wide use, but alternatives to RSA are also widely deployed --- bordering on ubiquitous. A total break of RSA probably wouldn't be that much more traumatic than, say, Heartbleed was.
Multiple times over the last 15 years, we've had for all intents and purposes comparable breaks --- BERserk and the original rump session Bleichenbacher e=3 breaks, for instance --- which broke TLS, to the point where you could stand up an evil server and DNS-MITM people to it, and compromise pretty much everyone running (say) Firefox. It wasn't the end of the world. The patch for "integer factorization is solvable in polynomial time" would be slightly more dramatic than the e=3 bug, but not much more: everyone would just deprecate RSA and use ECC.
You wouldn't want to use a browser so old it doesn't support ECDSA with P-256 (e.g. Android < 4.0). There would be a lot of scary stories in the media, but servers can switch to ECDSA (e.g. let's encrypt supports it). Devices which cannot be updated (e.g. credit card terminals) would need to be replaced.
Basically, yes. When we talk about how fast an algorithm is, we usually talk about how much longer it will take to run when you increase the length of the input.
Encryption works because you can double the size of the encryption key and make it take [very large number] times more operations to break the encryption (twice the work to encrypt+decrypt if you have the key, but tremendously harder to crack into without the key).
I don't think so, I would probably just try to make a lot of money from it, as unimaginative as that may be. Telling would almost certainly invite a large amount of unwanted attention.
Oh, and maybe keep using it to factor the keys of whoever I really don't like, and publish them, just to make their life a little more difficult.
This is similar to discussing what one would do if you invented an efficient quantum computer, which is something many private companies and governments are chasing. If one government had this ability they'd have no incentive to disclose it, they'd just crack every encrypted communication out there.
I would send Mr. Obama a mail signed by Mr. Putin's private key. The message would just be: "All your mail are belong to us, sucka". After which, I will send Mr. putin the same message but signed by Mr. Obama. :)
Another option is pastebinning an innocuous message signed with private keys of an implausibly diverse collection of sites and then dropping a link to that in front of a large audience including at least one person who could understand what big of a deal it was.
Either of these is a multi-billion dollar firecracker, of course.