1
$\begingroup$

With all our tools in math, isn't it really possible to find the prime number p of an RSA key without brute-forcing it with a computer? I'm not talking about doing it in 2 minutes but doing it in a clever way that is faster than our computers. Some algorithms work really well like MSIEVE and GGNFS, but it takes too much time to proceed. Can't we really find the prime p without the help of an algorithm?

$\endgroup$
  • 1
    $\begingroup$ Well, no. At least not with our current knowledge. Otherwise CAs and DNSSEC would long have been compromised and we all would be screwed. $\endgroup$ – SEJPM Oct 26 '16 at 22:40
  • 1
    $\begingroup$ "...without the help of an algorithm ...". Well, the only alternative I have in mind is a kind of magic ;-) $\endgroup$ – user27950 Oct 27 '16 at 5:23
  • 1
    $\begingroup$ If you have enough paper (say in the form of a heavy book) then you can in fact break RSA using the paper alone without the help of any algorithms. Just find someone who knows the primes (or the passkey for where the primes are stored) and beat them with the book until they tell you the answer. $\endgroup$ – J.D. Oct 27 '16 at 11:03
  • 1
    $\begingroup$ @J.D. Nope, your idea still does not satisfy the OP's request because what you suggest is an algorithm: - find someone who knows the primes (or the passkey for where the primes are stored) - beat them with the book until they tell you the answer. :) $\endgroup$ – tum_ Oct 27 '16 at 11:15
  • 2
    $\begingroup$ @A.Toumantsev - torture is not technically an algorithm, because it can 'terminate' without producing a correct output. $\endgroup$ – J.D. Oct 27 '16 at 12:02
5
$\begingroup$

If there was a general strategy to do this with pen and paper, we could do it with a computer just as well. Most pen and paper solutions to any math exercise rely on using lots of “shortcuts” or “tricks” that exploit special situations or specific properties of the numbers in the problem. However, since RSA keys tend to be very big, we'd need an impossible number of special situations to have an approach that works generally.

$\endgroup$
0
$\begingroup$

As a basic rule from computer science:

Computers are always better at calculations than humans.

There is no algorithm in the world, which a computer could not execute, if someone made the effort to write the program. Especially "math by hand" can only use the same tricks or clever ways, which can be used by a computer as well. And that's not only due to computation speed, a computer does not make mistakes (assuming the program is correct) or write down everything.

There are things, where humans are much better than computers, for example any kind of pattern recorgnition - both in sound and images. For images, computers have for example huge problems with difficult lighting scenarios. And for a computer to recognize words with a low error rate, you need a training phase and even then speak more clearly than usual.

Oh, and btw. RSA keys are chosen long enough that you cannot find $p$ with all the computation power in the universe. That's the entire point.

$\endgroup$
  • $\begingroup$ A Formalist would agree with you, but not a Platonist. $\endgroup$ – user27950 Oct 30 '16 at 15:20
  • $\begingroup$ I am not sure what platonism has to do with this. There is no statement or question about abstract objects or concepts which are neither physical nor mental. $\endgroup$ – tylo Nov 2 '16 at 11:25
  • $\begingroup$ If you are referring to constructive mathematics only, then there is probably no difference between "math by hand" and "math by computers". But there is a difference, if you take also non constructive proofs into account, e.g. Proof by contradiction. $\endgroup$ – user27950 Nov 2 '16 at 11:53
  • $\begingroup$ The question was adressed towards calculations, and not proofs. More specifically, it was about factorization algorithms and being able to do any tricks that a computer can't do. $\endgroup$ – tylo Nov 2 '16 at 11:59
  • $\begingroup$ You are completely right with respect to the stated question about factorization. I referred to the general statement you made with the sentence starting with "Especially, "math by hand" ...". $\endgroup$ – user27950 Nov 2 '16 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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