Simple digital signature example that one could compute without a computer?

Question

I am working on a document to explain Bitcoin to students. But I am having a hard time translating the principle described in §2 of the Bitcoin whitepaper in layman's terms.

There is a great question (Is there a simple hash function that one can compute without a computer?) with a great answer, which helps to understand hashing in cryptography better. I am looking for a similar answer like the question above received, but related to Bitcoin… more specifically, the digital signatures (public key & private key) used by the Bitcoin protocol.

I'm trying to understand how a verification works in the image below:

The goal is to simplify the signature generation and verification algorithm in a way that I can make it understandable for students that are not familiar with digital signatures or elliptic curve cryptography at all. So, what I am looking for is a pseudo/toy-algorithm (something like the Caesar cipher) that the students can use to understand how public and private keys work in an extremely simplified way.

Does any such digital signature example exist that one could compute without a computer? Or could you give me a helping hand coming up with an example that I could provide to my students?

Answer 1

The main difference between what you want an example for (digital signatures) and secure communication is this: the roles of the public and private keys are reversed.

Also, the content being encrypted is different. For secure communication, the entire message is encrypted. For digital signatures, the message format is irrelevant; you are trying to prove authenticity, not protect message content. Rather, it is a digest, hash, or checksum of the message that is encrypted.

The signature algorithm computes the digest, encrypts it with the private key (known only to the sender), and includes this encrypted digest (the signature) along with the message, to prove its authenticity.

The verification algorithm takes the public key (known to everyone) and uses it to decrypt the signature, as well as computing the hash or digest of the message itself. It then compares its computed hash of the message to the decrypted signature. If they are identical, verification was successful. If not, verification fails.

This is in contrast to security usage, protecting the content of a message. In this case, the message is encrypted using the public key of the recipient, and thus can only be decrypted by that intended recipient who has the matching private key.

So if you have an existing pen and paper example for security purposes, you could just use that same example, reversing the roles of the private and public keys. It's just a matter of understanding the differences in the process.

The only additional piece is the digest or hash. You can choose any mathematical function for this; a checksum or simple equation would be fairly easy to compute by hand. A checksum for example could be used to make a digest this way:

Message: HELLO

We can make it simple: A = 1, B = 2, etc. So we have

H = 8
E = 5
L = 12
L = 12
O = 15

The checksum is then computed by multiplying the position of each letter by its value, and summing them all up. So now we have

checksum(HELLO) = (8*1)+(5*2)+(12*3)+(12*4)+(15*5)=8+10+36+48+75=177

Now we encrypt 177. If our encryption method is xor (to simplify things on paper) and our private key is 915, the xor result is

177^915

Simplify using place values:

=(1^9)*100+(7^1)*10+(7^5)

Simplify again using binary:

=(0001^1001) | (111^001) | (111^101)

Now we can easily compute the binary xor operations and add the results:

=1000 | 110 | 010

Back to decimal:

=8*100+6*10+2=862

So we send the message HELLO862 probably along with some way to specify the message length. In most cases the signature might not be distinguishable from the message itself without knowing in advance how long the message is.

Then take 862, the signature, back through the decryption process. In our case we used xor which is a symmetric encryption, so it sort of defeats the purpose, but when using RSA, your private key and public key are two different numbers.