With a grain of salt > Of course, I have no real evidence for my views: [...]
Whoosh. The point is that NOBODY has any real evidence either way, so one shouldn't have a strong default prior of the problem being truly "hard."
Factoring may be easier than we think (2016)
21–30 of 174 posts
Re: Factoring may be easier than we think (2016)
#22Imagine what you would do if you discovered how to factor efficiently? Think carefully. You now how the power to decrypt much of the world's banking and internet traffic and spoof certificates. There are forces in this world that would kill you to have this power. Would you publish your findings for everlasting fame? Would you sell it to the NSA for money (remember you can prove your power without releasing your algo…
I don't think it would happen this way. First, other researchers would be looking for that algorithm too and therefore, institutions would have time to prepare. Second, leveraging a technical attack imply to have some operational support. The bigger the attack, the bigger the organization you need to implement it...
Re: Factoring may be easier than we think (2016)
#23Earlier quoted context omitted.
But if intelligence agencies broke factoring, would we know? Maybe they have.
If they have then they are using it exceedingly sparingly. I strongly suspect it would be impossible to use it to any moderate degree without being found out in one way or another. I know this is a very very poorly worded question :) but I wonder what the most amazing secret was that was held for the longest time?
Probably the most useful thing to do with this power if you had it would be and signing your exploits with all sorts of legit keys.
Maximal effective exposed area on all parts of the hardware and software stack of multiple potential opponents.
The real work would be using the information and trying to find other ways to discover the same thing. Classic intel problem.
Re: Factoring may be easier than we think (2016)
#24Earlier quoted context omitted.
But if intelligence agencies broke factoring, would we know? Maybe they have.
Unlikely, as they wouldn’t keep using methods that they’ve broken themselves
I doubt it, too; but using methods you've broken, but know others haven't, is a great way to convince people you haven't broken it either. And if you suspect they have, it's a great channel for misinformation.
Re: Factoring may be easier than we think (2016)
#25Earlier quoted context omitted.
I think that number (100) is a bit too low. There are students, graduates, post-grad fellows, and otherwise thousands of people living and breathing number theory. Sure, they might not directly stare at a blackboard with The Problem of Factoring staring back at them, but they are very much doing that indirectly. Just like the AKS primality testing algorithm depends on clever number theory, any progress, any new trick…
I think the core point of the OP you are missing is that he doesn't consider people indirectly, tangentially working on related things as doing "serious" work on factoring. I tend to agree. Look at Fermat's last theorem: it went over a century as one of mathematics hardest unsolved problems, and in reality all it took was one guy dedicating a couple of months of exclusive work to it. Factoring (and discrete log?) is…
> it went over a century as one of mathematics hardest unsolved problems, and in reality all it took was one guy dedicating a couple of months of exclusive work to it.
Six years, not a couple of months.
There were plenty of people who tackled this problem and who failed to make any headway. {Edit: I phrased this last sentence really clumsily, sorry.}
Re: Factoring may be easier than we think (2016)
#26Earlier quoted context omitted.
But if intelligence agencies broke factoring, would we know? Maybe they have.
If they have then they are using it exceedingly sparingly. I strongly suspect it would be impossible to use it to any moderate degree without being found out in one way or another. I know this is a very very poorly worded question :) but I wonder what the most amazing secret was that was held for the longest time?
We know they had public key crypto a few years before RSA.
Re: Factoring may be easier than we think (2016)
#27Imagine what you would do if you discovered how to factor efficiently? Think carefully. You now how the power to decrypt much of the world's banking and internet traffic and spoof certificates. There are forces in this world that would kill you to have this power. Would you publish your findings for everlasting fame? Would you sell it to the NSA for money (remember you can prove your power without releasing your algo…
I once asked this a cryptographer. His response was that he would do the following things (if I remember correctly): * Discuss the result with a few cryptographers he trusts, to check whether he didn't make a mistake and to make sure he's not the only one who knows about it. * Write a paper. Put in all kinds of silly things, because it will get published anyway. * Publish proof of having found the algorithm, together…
> Discuss the result with a few cryptographers he trusts, to check whether he didn't make a mistake
Well, what kinds of mistakes can you make? Either it works or it doesnt. You (and everyone else) can verify that easily.
(It might not work some numbers with special properties or so. But this does not matter if you can already break 99% of RSA keys)
Re: Factoring may be easier than we think (2016)
#28Imagine what you would do if you discovered how to factor efficiently? Think carefully. You now how the power to decrypt much of the world's banking and internet traffic and spoof certificates. There are forces in this world that would kill you to have this power. Would you publish your findings for everlasting fame? Would you sell it to the NSA for money (remember you can prove your power without releasing your algo…
This is the main reason that I don't store any of my sensitive data encrypted on cloud storage.
If the encryption eventually gets cracked somehow, my data will be available not only to whoever owns, hacks, or otherwise compromises the cloud storage provider itself, but anyone who happened to have captured the traffic on any of the hops it went through on the way to the provider.
Re: Factoring may be easier than we think (2016)
#29Imagine what you would do if you discovered how to factor efficiently? Think carefully. You now how the power to decrypt much of the world's banking and internet traffic and spoof certificates. There are forces in this world that would kill you to have this power. Would you publish your findings for everlasting fame? Would you sell it to the NSA for money (remember you can prove your power without releasing your algo…
I once asked this a cryptographer. His response was that he would do the following things (if I remember correctly): * Discuss the result with a few cryptographers he trusts, to check whether he didn't make a mistake and to make sure he's not the only one who knows about it. * Write a paper. Put in all kinds of silly things, because it will get published anyway. * Publish proof of having found the algorithm, together…
You don't really need someone else to check if you've made a mistake. So long as you can multiply reliably you can just factor the largest one of the RSA prize semiprimes and then check that you did indeed produce some factors.
I think my plan would just be to publish that factorisation anonymously (being super paranoid to avoid being traced) and then wait however long was necessary before publishing the algorithm.
Re: Factoring may be easier than we think (2016)
#30With a grain of salt > Of course, I have no real evidence for my views: [...]
Might want to include context there:
>Of course, I have no real evidence for my views; ... On the other hand, the people who talk about the great difficulty of factoring have equally little evidence.