Public-key authentication that is feasible by hand, before computers?

Azuresonance

1/13/24, 5:46 AM

I wonder if it's possible to do public key authentication (preferably not vulnerable to replay attacks) before modern computers became a thing (e.g. in a medieval setting).

Specifically:

Authentication can be done in a reasonable time by hand.
Brute force by hand requires unreasonable time. (But it may be possible with modern computers)

As I understand it, this would require that the disparity between the time complexities of normal authentication and brute-force is very large even for small n, where n is something like the length of the key. Is there anything that can achieve this?

745

1 + 3

fgrieu

1/13/24, 8:30 AM

Even secure symmetric authentication based on a non-reusable shared secret key and doable by hand is difficult (we have a [question about that](https://crypto.stackexchange.com/q/47820/555)).

AleksanderCH

1/13/24, 3:02 PM

Does this answer your question? [Does humanly verifiable one time pad authentication exist?](https://crypto.stackexchange.com/questions/47820/does-humanly-verifiable-one-time-pad-authentication-exist)

John Coleman

1/13/24, 4:15 PM

In a medieval setting you might run into the problem of no Hindu-Arabic numbers to compute with.

Score:5

Crypto

Daniel S

1/13/24, 10:07 AM

I could conceive of this in theory. If we look back to when the word "computer" referred to a job done by a human being as early as Renaissance times, computers were capable of lengthy and sophsticated calculation.

In a near miss for the discovery of public key cryptography in 1874 William Stanley Jevons created what could be thought of as the first RSA-like challenge in his book Principles of Science. Jevons thoughts were not far from cryptography at this point and it could certainly be argued that he understood that his "RSA key generation" was simpler than factoring by trial division. Notably though Charles Busk used Fermat's method to factor Jevons number five years later with a moderate amount of effort. Both Jevons and Busk likely had access to mechanical devices or human computers and its possible that if Jevons had devoted longer to generating his key, it would have taken a much longer (infeasible?) amount of time for Busk to factor. Arguably, Fermat's method is more sophisticated than brute forace and so falls outside the parameters of the question.

+ 1

fgrieu

1/13/24, 11:44 AM

Good point that Fermat's primality test is feasible by hand to sizes making factorization by hand much harder. The strong pseudoprime test thus also is feasible (since it's even less costly). Using the CRT, RSA signature of short messages (with crude padding adding redundancy) is of cost comparable to such primality test for both factors, thus doable too, with comparably significant but feasible effort. I wonder for ECC. The parts I see somewhat problematic by hand are finding the group order, and making the equivalent of a hash.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Public-key authentication that is feasible by hand, before computers?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.