Cracking RSA (or other algorithms) manually by a savant

Question

RSA cryptography strength comes from the hardness (or so we believe) of factoring big numbers. For key lengths over 2048 bits, it is infeasible for current or near-future computers to factor those numbers in a reasonable time.

But what about the human brain? There are people with remarkable math abilities; for example, savants that can perform many complex calculations. Imagine a person who is fixated on factoring composite numbers. Maybe his or her abilities could be augmented by drugs.

Is this a genuine concern when designing cryptographic ciphers? Could an evil organization employ one of these people to crack cryptographic keys (for any modern cipher)? Maybe there is some real-life example?

Answer 1

Mental calculators do not have the result appearing in their brain by staring at the input. They follow some (broadly sequential) algorithm¹. And computers vastly outperform them when they use the same algorithm. That was already by at least a factor >100 for inexpensive personal computers in the late 1970s.

For example, the record for 10 multiplications of two 8-digit numbers is stated at 162 seconds (source). Even by a schoolbook algorithm working in decimal, that task at worse requires 640 elementary operations involving 4 decimal digits. An Apple ][ with a proper (6502 assembly) program would do this well under 1 second, including extracting the digits from and storing the results into screen "text" memory.

I conclude we can entirely discount human prodigies outperform computers at breaking any proper crypto.

---

Update: the same source states as a record mentally finding in 6'38" the factors of 20 random five-digit composites, which is considerably easier than for proper RSA biprimes. This is telling about the human brain not being good at factoring.

Update2: It's also stated as a performance factoring a 16 (resp. 15, 14)-digit integer known to be the product of four consecutive primes at an average of 23'24" (resp. 13'21", 6'06"). I guesstimate an Apple ][ can outperform that by a factor ≈10000 even when working in decimal, using a single step of Fermat's method for each of three factorizations.

---

¹ See a performer multiplying two 20-digit numbers in 5'26"; world record is stated as 2'48".

Answer 2

Your thinking is against the common sense in cryptography and computing. And to be blunt, it's blatant pseudoscience.

Human brains and the neurons within operate on scalar states. While it's arguable whether the brain process is deterministic or probabilistic, it does not possess the capability to create state superpositions like quantum computers could. Thus has no advantage over classical supercomputers on integer factorization or discrete logarithm (Shor's algorithm), nor does it have any advantage at searching through unsorted database (Grover's algorithm).

Answer 3

For human brains, it's all too easy to ignore the depth of the 2048+ bit figure. Let's do some engineering guesstimation exercise to illustrate.

The original post by @derjack measures almost 700 characters long. Here's a 2048-bit number, written in 617 decimal digits (almost as long as the question):

32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448280710318450446268407511633591722075539194702809692695116208601753153385228164358637425253452063124531982403270024154882788029124087013649227429510942494747262878176328960795460204004486651813356499189783184670257748061985168288109350852763136493356212118910302261417784227884243069534873234110239729827362916848850208533176280055919120540762635115410724871087269605319201076899957787049604743491139956908133927452563472712188255099007744935013999050172650250829825

You can take my word that it's a composite number (i.e. not prime).

You can also take a closer look and observe that the last digit is 5 and therefore, 5 is a divisor. But simply as a challenge, can you find the larger factors?

Let's establish a lower bound on the time an existing human could crack this. My references are wonky here¹, but it seems plausible to take 3850 words per minute as an upper bound on human reading speed. Converted, it's 302 characters per second (with 4.7 average word length in English²). I'll also extrapolate this figure to long numbers; so we arrive at the ballpark of 300 digits per second reading speed.

>>> 617 / 301.6
2.045755968169761

The fastest human reader in the world will need no less than 2045 milliseconds just to load the number into their memory. For more ordinary readers like me and you, there's a 17× factor¹; so just reading the number will take 35 seconds no less. Notice that for the lower-bound estimation we're doing here, we have to assume infinite integer-FLOPS performance of the brain. The 35 seconds would be the IO before the compute.

¹: https://www.brainread.com/en/the-fastest-reader-in-the-world/

²: https://norvig.com/mayzner.html

---

Now, I recommend you repeat the exercise yourselves, e.g. for 4096 bits. It's not twice as many! Wrong abstraction level if you think so. 4096-bit numbers are on average 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 times larger than 2048-bit numbers, in absolute value.

The exercise might help you realize how deceivingly easy it is to hear something about "N-bits" calculations and imagine you understood something. That's way harder than it sounds—if you do the math.

Answer 4

Any human being who can factor 2048 bit numbers in their head faster than a computer is almost certainly a human being who has, in effect, discovered a new algorithm to factor numbers. Which, if implemented on a computer, would be even faster.

But that doesn't rule this out.

I'm going to be a bit less than totally precise below. For example, I'll mix up decision problems and algorithms to keep terms simple.

We don't know how hard factoring numbers is really. We know it is in a complexity class BQP, which for classical computers (or a human running a classical algorithm in their head) in NP.

A problem is in NP if it is relatively cheap to verify you got the right answer. The example here is that if someone states that the factors of some number are A and B, you can check it by ... calculating A*B and seeing if it matches.

But there there isn't any proof that NP isn't the same as P. If NP=P, then every problem whose solution can be verified fast can be solved fast. (This is very hand-wavy, but true within those bounds). And if NP=P, then BQP which is in NP is also in P.

For problems in NP, we know of no classical algorithm that is much all that much faster than "just try every possibility" here for generous definitions of "all that much". (the fastest factoring algorithms are strictly sub-exponential; like O(e^(k + bits^(1/3)*ln(bits)^(2/3)) if I copied that right).

So, if someone came up with an algorithm to factor large numbers that was polynomial time, they could in theory learn how to run the algorithm in their head, and be able to factor large composite numbers faster than any computer can.

This is implausible. And, honestly, such an algorithm would probably be more valuable to share than to stuff into your head.

The Savant could find fast factorization without showing NP=P or even that BQP=P; for example, it could be that factorization of the specific kinds of primes we use for cryptography is easier than the general problem, or maybe a large percent of such composite numbers are easy to factor (but not all of them), or that there is some other "corner case" that lets it work (even sometimes) extremely faster than "try every case". Such a result would be powerful, but wouldn't be revolutionary on the scale of rewriting much of what we consider interesting mathematics (which an efficient P algorithm for NP problems would do, honestly).

Answer 5

The other answers have already correctly pointed out that animal brains are vastly slower and more error-prone than modern computers on all computational tasks except a select few that benefit a lot from the specific kind of pattern-recognition and planning skills that brains were evolved for. Obviously, this does not mean that an animal brain cannot be useful cryptographically: indeed, the best cryptographic attacks known today have all been found at least in part by animal brains. However, for standard cryptographic schemes, it seems vastly unlikely that a brain could run a successful attack (it might, however, be very useful at the stage of planning it).

That said, I do find the question amusing whether a cryptographic scheme could be designed that is secure against all known attacks that are based on a fully specifiable attack algorithm but not secure against paper-and-pencil cryptanalysis. I do not think the answer to this is obviously negative. One could, for instance, think about encoding a long random bit sequence into a series of Winograd schemes. The receiver would then manually solve the Winograd schemes and subsequently post-process the recovered bit sequence to privacy-amplify their decoding advantage against state of the art language models and obtain a one time pad that cannot be reconstructed with high accuracy by automated methods. Finally, the derived OTP would be used to encrypt a short message.

However, since there is no evidence that brains are intrinsically better at anything than computers, all such schemes will be prone to practical automatic attacks eventually.

Answer 6

The 2048 bit 617 decimal digit number @ulidtko posted above can be factored in hours or less and possibly by a savant with a big integer calulator. I have factored this and found the special form of the factors. The small factors are easy, but the large factors are not if you do not find the special form.

The savant type of ability needed is the ability to spot patterns in the binary representation of the smaller factors of the 2048 bit number.

Here are the decimal and binary values of the lowest factors: 3 - 11, 5 - 101, 7 - 111, 13 - 1101, 17 - 10001, 97 - 1100001, 193 - 11000001, 241 - 11110001, 257 - 100000001

Can you see the pattern? There are 3 patterns. First pattern all 1's 11,111 2nd pattern 101,10001, 100000001 3rd pattern other 1101, 1100001, 11110001

The 2nd pattern is 2^k+1. The first pattern is 2^k-1. If you pick the 2nd pattern and trial divide out the 2^k+1 factors this reduces the factorization.

The factors are: 3^3 x 5^2 x 7 x 13 x 17 x (2^768+1)(2^384+1)(2^256+1)(2^192+1)(2^128+1)(2^96+1)(2^64+1)(2^48+1)(2^32+1)(2^24+1)(2^16+1)(2^12+1)(2^8+1)

After dividing out the larger 2^k+1 factors, you are left with 1044225=3^3 x 5^2 x 7 x 13 x 17 to factor.

Answer 7

History: Alan Turing and cracking the Enigma machine. Thus:

Is this a genuine concern when designing cryptographic ciphers? Could an evil organization employ one of these people to crack cryptographic keys (for any modern cipher)?

Yes, as far as you're able to find your Alan Turing and provide what's needed (or build it from scratch, as was the case of the Enigma machine "bombs").

No, if you think your Alan Turing will do it using paper and pencil.

Answer 8

Actually, if you could find a factoring savant, that would constitute a proof that p=np (or that a massive fraud was being conducted at your expense) I'll bet a large amount on the latter.