Factoring may be easier than we think (2016) • Hacker News Board

Re: Factoring may be easier than we think (2016)

#11

Post by pas » Sun, Jun 30, 2019, 3:07 PM UTC

Jabbles wrote: post #2

Let's say a serious attempt consists of several months of work by an expert, someone who knows enough number theory to read the literature on this problem. Then the number of people who have seriously tried must be on the order of magnitude of 100. In academia, maybe. But I would not be surprised if millenia of experts' time has been spent on this problem in intelligence agencies.

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 would be very likely reported, and we'd see it in charts like these:

https://aiimpacts.org/progress-in-general-purpose-factoring/

Re: Factoring may be easier than we think (2016)

#12

Post by doubleunplussed » Sun, Jun 30, 2019, 3:11 PM UTC

I've heard the following called "Aaronson's trilemma": Either the extended Church-Turing thesis is false, or quantum computers are impossible, or...there exists a classical polynomial factoring algorithm that runs in polynomial time.

One of these things must be true, and debates around quantum computing usually focus on the first two. But as argued, we don't have great reasons to believe factoring in polynomial time is impossible. We certainly don't have a proof that no such algorithm exists.

Re: Factoring may be easier than we think (2016)

#13

Post by goerz » Sun, Jun 30, 2019, 3:12 PM UTC

alexandercrohde wrote: post #6

Jabbles wrote: post #2

Let's say a serious attempt consists of several months of work by an expert, someone who knows enough number theory to read the literature on this problem. Then the number of people who have seriously tried must be on the order of magnitude of 100. In academia, maybe. But I would not be surprised if millenia of experts' time has been spent on this problem in intelligence agencies.

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

Re: Factoring may be easier than we think (2016)

#14

Post by aykevl » Sun, Jun 30, 2019, 3:13 PM UTC

waynecochran wrote: post #7

Imagine 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 with a hash of the paper.

* Wait ~3 years until everyone has moved to a better algorithm. The normal responsible disclosure period is 3-6 months but this is so big it has to take a bit longer.

* Publish the paper.

I certainly think this is pretty dangerous. It may in fact be better to do the initial publication anonymously... and make sure you avoid all possible traces (the NSA will do everything in their power to get a hold of you).

Re: Factoring may be easier than we think (2016)

#15

Post by jahnu » Sun, Jun 30, 2019, 3:14 PM UTC

alexandercrohde wrote: post #6

Jabbles wrote: post #2

Let's say a serious attempt consists of several months of work by an expert, someone who knows enough number theory to read the literature on this problem. Then the number of people who have seriously tried must be on the order of magnitude of 100. In academia, maybe. But I would not be surprised if millenia of experts' time has been spent on this problem in intelligence agencies.

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?

Re: Factoring may be easier than we think (2016)

#16

Post by goerz » Sun, Jun 30, 2019, 3:15 PM UTC

adamnemecek wrote: post #5

Fast factorization is going to be one of the killer apps of photonic computers.

You mean quantum computing (for which photonics are not a leading candidate), or regular photonic computing? Because the latter doesn’t scale any better than normal computers.

Re: Factoring may be easier than we think (2016)

#17

Post by delinka » Sun, Jun 30, 2019, 3:15 PM UTC

JPLeRouzic wrote: post #9

I am not a scientist, but in my team 15 years ago, many people much more talented than me were in love with public cryptography. For them encryption with a 1024 key was perfect, impossible to break. They did not even considered that several RSA challenges had already been found. Even if I had no education in mathematics I tried to show that in fact it was feasible to factor some enough large numbers with "bc" (using…

I'm not following your story.

At the time when 1024-bit numbers used in RSA were 'perfect', it was infeasible to factor the number in a reasonable amount of time. The most straightforward approach is just to iterate over integers from 2 to your target number (call it n), and see if anything divides evenly. Now, you start looking for shortcuts. First, you can test only half the numbers, because the second half will give identical results (e.g. n=20, n/2 = 10; later, n/10 = 2; no need to even test the second half of the range.) Next, it becomes obvious that we only care about odd numbers (if it's divisible by an even number, it's divisible by two); but really, when it comes down do it, we only care about prime factors (for one thing, all non-primes can be decomposed into prime factors; for another, we used prime numbers to get n.) And lastly, for the simple shortcuts, you really only have to get to int(sqrt(n)) + 1 or so. So we've cut down the number of integers we have to divide with.

Did we find the two prime factors of our n in a "reasonable" time? If so, just double the bit length to get a problem twice as hard. Every publicly-known shortcut to factoring large numbers just means you need to make your n larger to increase the workload on an attacker.

The question then becomes: has anyone found a shortcut that will factor any number within a "reasonable" time? We don't know.

As to your career-related comments, I read cluelessness from your boss, and carelessness from the 'other guy' - if OG "would not try to break any encryption scheme," then he's not the person whose advice you want about the strength of cryptosystems. Your boss just lacked critical thinking skills.

Re: Factoring may be easier than we think (2016)

#18

Post by garmaine » Sun, Jun 30, 2019, 3:16 PM UTC

pas wrote: post #11

Jabbles wrote: post #2

Let's say a serious attempt consists of several months of work by an expert, someone who knows enough number theory to read the literature on this problem. Then the number of people who have seriously tried must be on the order of magnitude of 100. In academia, maybe. But I would not be surprised if millenia of experts' time has been spent on this problem in intelligence agencies.

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 probably similar.

I work in this field as a non-academically-trained cryptographer. Cryptographers prefer to assume their assumed-hard functions are in fact hard and move on. Especially those that have academic training--they supposedly know better than to waste their time on such a hard problem.. but by induction that means approximately nobody is really looking at it.

Re: Factoring may be easier than we think (2016)

#19

Post by wbl » Sun, Jun 30, 2019, 3:17 PM UTC

doubleunplussed wrote: post #12

I've heard the following called "Aaronson's trilemma": Either the extended Church-Turing thesis is false, or quantum computers are impossible, or...there exists a classical polynomial factoring algorithm that runs in polynomial time. One of these things must be true, and debates around quantum computing usually focus on the first two. But as argued, we don't have great reasons to believe factoring in polynomial time…

What is the extended Church-Turing thesis? We already know quantum computers give speedups beyond classical lower bounds.

Re: Factoring may be easier than we think (2016)

#20

Post by garmaine » Sun, Jun 30, 2019, 3:17 PM UTC

delinka wrote: post #17

JPLeRouzic wrote: post #9

I am not a scientist, but in my team 15 years ago, many people much more talented than me were in love with public cryptography. For them encryption with a 1024 key was perfect, impossible to break. They did not even considered that several RSA challenges had already been found. Even if I had no education in mathematics I tried to show that in fact it was feasible to factor some enough large numbers with "bc" (using…

I'm not following your story. At the time when 1024-bit numbers used in RSA were 'perfect', it was infeasible to factor the number in a reasonable amount of time. The most straightforward approach is just to iterate over integers from 2 to your target number (call it n ), and see if anything divides evenly. Now, you start looking for shortcuts. First, you can test only half the numbers, because the second half will g…

Even 15 years ago 1024-bit numbers were not secure.