12
$\begingroup$

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?

$\endgroup$
9
  • 61
    $\begingroup$ I use 10% of my spare brain power to mine crypto. $\endgroup$
    – qwr
    Jul 20, 2021 at 18:09
  • 43
    $\begingroup$ Autistic people are not magical. The "savant" myth has grown out of Autistic people with uncommon interests who have chosen to hone unusual skills, which can be extremely impressive. In the end though these skills pretty much anyone can learn if they put in the many hours of practice it has taken the "savants" to master them. So no, we don't have magic powers like that. $\endgroup$
    – Jasmijn
    Jul 20, 2021 at 19:34
  • 35
    $\begingroup$ This question is based on counterfactual magical thinking and misrepresentation of autistic people, not about cryptography, and should be closed. $\endgroup$ Jul 20, 2021 at 23:03
  • 2
    $\begingroup$ @Jasmijn One of the prominent accounts comes from Oliver Sacks, the story of the twins who like prime numbers. It is not rigorous and 50 or so years ago. But he raises the idea that the twins' look at the "number landscape" is as different from a computer algorithm as the human prowess at recognizing faces or judging a character. More a gestalt thing. The computer has a biometric data set of eye distance and nose poistion; we simply know it's dad. $\endgroup$ Jul 21, 2021 at 12:45
  • $\begingroup$ @RockPaperLz-MaskitorCasket As an autistic person, I can say that the reason I know a lot about coding is because the way I express my interest in it leads to a lot of research. There's a video by an autistic person explaining it better here: youtube.com/watch?v=RE-TT1Ac-jU $\endgroup$
    – ARI FISHER
    Jul 23, 2021 at 10:21

8 Answers 8

55
$\begingroup$

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".

$\endgroup$
8
  • 9
    $\begingroup$ I agree, the numbers are simply overwhelmingly bad for humans — even exceptionally gifted and capable humans. You may imagine a superhero nicknamed Pentium all day for entertainment; but I dare you, try to beat even 32-bit math in you head. You'll see how unexpectedly long the road to 2048 bits is. $\endgroup$
    – ulidtko
    Jul 20, 2021 at 11:50
  • 3
    $\begingroup$ Perhaps; though certainly there have been cases of astounding mathematical intuition that did not come from algorithmic calculation (e.g. the formulas that the goddess Namagiri allegedly whispered into Ramanujan's ear). $\endgroup$
    – user168715
    Jul 20, 2021 at 17:54
  • 4
    $\begingroup$ @Peter-ReinstateMonica, Oliver Sacks never let the facts get in the way of a good story. His essay on those twins is simply incredible, in the literal sense of the word. $\endgroup$
    – TonyK
    Jul 21, 2021 at 22:14
  • 2
    $\begingroup$ @Peter pepijnvanerp.nl/articles/oliver-sackss-twins-and-prime-numbers $\endgroup$
    – Martheen
    Jul 22, 2021 at 5:00
  • 2
    $\begingroup$ @Peter-ReinstateMonica The twins case is interesting, even though skepticism is warranted. In so far as they had some (difficult to determine) skill involving prime numbers it might be closer to a neural network approach to prime detection than a more conventional algorithm. That is a studied problem which has so far not yielded a practical algorithm. In any event, detecting if a number is prime isn't the hard part of RSA, so even the most optimistic take on the twins' skills has little direct relevance. $\endgroup$ Jul 23, 2021 at 12:18
22
$\begingroup$

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).

$\endgroup$
10
  • 4
    $\begingroup$ Not sure if a question without an inherent assertion can be pseudoscience. I guess it is more of an over-extrapolation - there are apparently people that could factorize easily, and that must mean that somebody could do this with numbers over 300 decimal digits. $\endgroup$
    – Maarten Bodewes
    Jul 20, 2021 at 10:36
  • 14
    $\begingroup$ I agree that there's almost certainly no large scale coherent quantum processing going on in the brain, but saying that the brain operates on discrete states might be misleading to some. Neuron firings (action potentials) are discrete events, but they're best understood as encoding analog signals via the frequency of their firing and the overall processing that goes on can be most cleanly modeled using continuous-time analog signals with lots of feedback loops. There's no reason to believe brains would have a factoring advantage, but it's not because they're equivalent to digital computers. $\endgroup$
    – Dan Bryant
    Jul 20, 2021 at 17:05
  • 9
    $\begingroup$ The biggest fallacy in modern science is to think that your brain 'computes' anything remotely like a computer. It does not. That analogy is extremely limited and helps no one to understand either the brain OR computers. $\endgroup$
    – Nelson
    Jul 21, 2021 at 4:10
  • 1
    $\begingroup$ Human brains and the neurons within operates on discrete states. If you are talking about discrete systems, we currently have no scientific proof that the human brain operates as a discrete system. $\endgroup$ Jul 21, 2021 at 7:37
  • 5
    $\begingroup$ There is a controversial theory by physicist Roger Penrose that coherent superpositions of quantum states exist within microtubule structures in the brain, and these quantum effects are relevant to human thought. en.wikipedia.org/wiki/… $\endgroup$
    – Nick Alger
    Jul 21, 2021 at 21:15
12
$\begingroup$

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.

$\endgroup$
9
  • 24
    $\begingroup$ The second part of this seems like nonsense. If it takes a human N seconds to read one page of text, it takes 2N seconds to read two pages. (Anyone can verify that for themselves.) .The fact that in this case the two pages of text represent a single number that is much more than twice as big as a one-page number is irrelevant. $\endgroup$
    – alephzero
    Jul 20, 2021 at 17:25
  • 1
    $\begingroup$ @alephzero: yup, humans normally think about numbers as lists of digits in some base greater than 1. So the brain space scales with log_b(|N|), the number of digits, not |N| the magnitude. If we thought of numbers in terms of collections of marbles (or cardinality of generic sets), that would be different. Computer algorithms for multiplication for example are quadratic in the number of digits (or less with algorithms like Karatsuba), which is why wider chunks give speedups for biginteger math. But also why computers doing RSA with 4096-bit keys aren't 2^2048 x slower than with 2048-bit k. $\endgroup$ Jul 21, 2021 at 8:24
  • 3
    $\begingroup$ Your composite number ends in a 5, for heaven's sake. $\endgroup$ Jul 21, 2021 at 12:34
  • $\begingroup$ It ends in 25, so it's clearly divisible by 5 at least twice. $\endgroup$
    – dan04
    Jul 22, 2021 at 23:21
  • 1
    $\begingroup$ What are integer-FLOPS?!?! Isn't that a bit contradictory? $\endgroup$
    – jjj
    Jul 23, 2021 at 13:57
4
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ This answers an answer, not the question: are savants "concern when designing cryptographic ciphers"? It's not even related, since highly composite integers like the one factored are not suitable for use as modulus in RSA cryptography (or other based on the intractability of factorization of certain integers). $\endgroup$
    – fgrieu
    Aug 19, 2021 at 18:13
  • $\begingroup$ Sorry @fgrieu, it did not appear I had enough reputation points to reply to the comment, so I posted as a answer. I'll follow the rules and do it your way. Thanks. $\endgroup$ Aug 19, 2021 at 19:08
-1
$\begingroup$

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.

$\endgroup$
-3
$\begingroup$

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.

$\endgroup$
5
  • 5
    $\begingroup$ I don't think that would constitute a proof that P=NP (factoring isn't known to be NP-complete and probably isn't, and the factoring savant isn't a computer). $\endgroup$ Jul 21, 2021 at 5:25
  • $\begingroup$ @thedefault.: Indeed, the P = NP problem is based on the classical model of computation, and a savant is not a programmable Turing-machine-equivalent computation device. They might be able to solve some large NP problems for you quickly, but only if you can transform such problems into factorization. But so can quantum computers. (That's what D-Wave claims to be doing commercially - en.wikipedia.org/wiki/D-Wave_Systems#Orion_prototype) $\endgroup$ Jul 21, 2021 at 8:29
  • $\begingroup$ @PeterCordes As far as we know, a human brain can be emulated on a Turing machine $\endgroup$
    – user253751
    Jul 21, 2021 at 8:29
  • 3
    $\begingroup$ @user253751: Is that the current consensus? Roger Penrose argued that wasn't (or might not be) the case (in The Emperor's New Mind). That was decades ago, but I didn't think the scientific consensus was confident of understanding how human brains work in enough detail to rule out quantum processes. Note that a Turing machine has no source of true randomness, for example (only sufficiently-advanced PRNGs), but quantum processes do. $\endgroup$ Jul 21, 2021 at 8:35
  • 2
    $\begingroup$ @user253751: Other than true randomness, though, I think we can simulate quantum processes, so even if the brain is quantum, that's not a problem for correctness, only performance. And with a large enough state, a PRNG can give high-quality randomness for as long as we need to simulate for. $\endgroup$ Jul 21, 2021 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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