9 ms·
Ask HN: If you found an easy way to factor large numbers, would you tell anyone?
- jamesrom 10y ago"I'd sell it to the NSA for some bitcoin"
- nso95 10y agoNo. My safety is more important than my ego.
- rjbwork 10y agoBut 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.
- techjuice 10y agoYep, 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.
- tlb 10y agoYes, 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.
- foota 10y agoI'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.
- macphisto178 10y agofor the ignorant (i.e. me) among us, what are the implications of factoring large numbers?
- dripton 10y agoA lot of widely-used cryptography relies on factoring large numbers being difficult.
- _greim_ 10y agoAre we using "difficult" to mean "takes longer than the universe"? Since presumably that would be why we trust it for cryptography?
- khedoros 10y agoBasically, 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).
- johnloeber 10y agoMost 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.
- tptacek 10y agoNo, 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.
- agf 10y agoI 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.
- hartator 10y agoI think I disagree. You should be allowed to do anything you want of you aren't stealing or murdering anyone.
- agf 10y agoOpenly 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.
- deleted 10y ago[deleted]
- danieltillett 10y agoIf 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”. More seriously I would say nothing.
- femto 10y ago> More seriously I would say nothing. 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).
- a3n 10y agoOf course. If I figured it out, then someone else has. People should know that their encrypted comms are not as secure as they thought.
- patio11 10y agoI 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.
- tootie 10y agoThere'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. https://en.wikipedia.org/wiki/Travelling_Salesman_(2012_film) https://en.wikipedia.org/wiki/Travelling_Salesman_(2012_film...
- CamperBob2 10y agoIMHO, 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.
- habosa 10y agoThis 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.
- flukus 10y agoI'd tell everyone right away. If I've figured it out then so have other people and security doesn't exist.
- bcrescimanno 10y agoI'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. (see: http://www.imdb.com/title/tt0105435/?ref_=nv_sr_1 http://www.imdb.com/title/tt0105435/?ref_=nv_sr_1)
- ljoshua 10y agoOh, I'd be fine!
- 27182818284 10y agoBefore I even saw your post I was thinking about references to this movie. That's great.
- ramparrt 10y agoThey're the NSA, they don't do that sort of thing
- aaron695 10y agoSure, I would find it hard to monetize, it'd be easier to ask the Chinese for help cash it in.
- scythe 10y agoI'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.
- TempleOSV409 10y agoNIST has a log of logins. Check for hacking the login. It's not hacked. You think I found a login and got a password?
- wbhart 10y agoThere 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.
- taneq 10y ago> He fooled a lot of people, but most people never heard of him and most of those who did believed it was a hoax. Implying John Titor wasn't real! :P
- walrus01 10y agoSETEC ASTRONOMY
- draw_down 10y agoI 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.
- williamstein 10y agoYes, 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.
- DeathArrow 10y agoI 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. :)
- DeathArrow 10y agoOhh, and I would found an business to provide psychological counseling for ex-NSA employees. :D
- szc 10y agoI can show this and more, alas this CSS margin is too small to write my proof! (apologies to a real mathematician. who. was. also. correct :-))