public key... a padlock (anyone can lock it)

private key... the key to the padlock (only key owner can open it)

Alice and Bob each have their own padlock and key

Anyone can get a replica of any padlock (public key) but only the padlock owner can open it (private key)

Alice sends Bob a private message:

  1. Alice locks a box with Bob's padlock (public key)
  2. Only Bob can unlock it.

Bob wants to be sure the box came from Alice: (Bob gets Alice's signature)

  1. Bob sends box to Alice locked with her padlock
  2. Alice unlocks it, then puts Bob's padlock on instead, and sends it back to Bob
  3. Bob sees only one padlock which he unlocks with his key. He knows that Alice had the box as only she could have taken her padlock off.
  • $\begingroup$ More or less correct, although the signature verification analogy isn't really how it works in practice. $\endgroup$ – Luke Park May 11 '20 at 3:46
  • $\begingroup$ see also blog.vrypan.net/2013/08/28/… $\endgroup$ – Alex Taylor May 11 '20 at 4:17
  • $\begingroup$ @LukeJoshuaPark many thanks, although not accurate in practice, is the effect identical logically speaking? If not what scenario for example would comprise an exception? $\endgroup$ – Alex Taylor May 11 '20 at 4:21

(Disclaimer: I am not qualified to speak authoritatively on cryptography - I didn't even take any undergraduate classes on cryptography as a student either)

The first part (the analogy for public-key encryption) is valid (analogising a public-key as a padlock works, but disregards the fact that a public-key (padlock) can be used to decrypt data encrypted with the private-key (the key) - which is counter-intuitive to a layperson).

As for the second part:

Bob wants to be sure the box came from Alice: (Bob gets Alice's signature)

  1. Bob sends box to Alice locked with her padlock
  2. Alice unlocks it, then puts Bob's padlock on instead, and sends it back to Bob
  3. Bob sees only one padlock which he unlocks with his key. He knows that Alice had the box as only she could have taken her padlock off.

Key-exchange - or any subsequent interaction between Alice and Bob - is not necessary to prove message authenticity:

In PKI, a digital-signature is basically a message-digest (i.e. a hash like SHA-256) that has been encrypted with a private-key (rather than a public-key) - so that anyone with the public-key can decrypt the encrypted hash (and then recompute the hash and if it matches then that's proof that the message came from the holder of the private-key for the corresponding public-key), like so:

  1. Alice sends Bob a private message.
    • The message is encrypted with Bob's public-key, so only Bob can decrypt it.
      • (Assuming Bob's private-key hasn't been leaked or discovered, of course).
    • While the message is encrypted with Bob's public-key, that has absolutely no bearing on the originator or attestor of the message - because anyone can encrypt anything with someone's public-key.
      • So Alice also adds her signature to the message, which does two things:
        1. It means that Bob can trust that Alice is responsible for the message (that she either authored or she's attesting to it) - again, assuming Alice's key isn't leaked or discovered.
        2. It proves that the message from Alice to Bob has not been modified (otherwise the recomputed hash wouldn't match).
      • Alice adds her signature by computing a hash of the message, then encrypting the hash with her private-key, so anyone with her public-key can decrypt it and see her hash.
  2. Bob then receives the message:
    • The message is encrypted with Bob's public-key, so only Bob can decrypt it with his private-key.
    • The message has Alice's signature attached to it, so Bob can verify the authenticity and integrity of the message:
      1. Bob has Alice's public-key and decrypts Alice's signature, revealing Alice's computed hash of the message.
      2. Bob then computes his own hash of the message.
      3. Bob sees that his hash - and Alice's hash match - therefore the signature is valid and Alice sent the message.

Regarding Step 3 in the scenario you've posted:

Bob sees only one padlock which he unlocks with his key. He knows that Alice had the box as only she could have taken her padlock off.

This is not guaranteed and must not be assumed: Alice could have sent the exact same message to other people, and those other people could have encrypted the message with Bob's public-key and then forwarded it to Bob - if Bob receives one of those messages then there is absolutely no indication it actually came from Alice or that he was the original intended recipient.

This is why, for example, S/MIME for e-mail requires the entire message body and headers to be included in the message hash (in S/MIME this is actually done by copying certain headers like To:, Subject:, From:, etc into the message and then hashing and encrypting that) - so while the adage that anyone can encrypt anything with someone's public-key, so long as the message is also signed by the sender then at least this approach preserves information about the intended recipient in addition to the actual sender.

Example scenarios:

  • Alice wants to send a non-secret newsletter that can be redistributed by anyone:
    • Alice would sign her newsletter content with her private-key.
    • Anyone is able to redistribute (copy, forward, etc) this newsletter, and provided they keep the signature attached to the newsletter then anyone who receives it can be sure it originated with Alice.
    • Because anyone could simply remove Alice's signature and replace it with their own, Alice can prove she originated the message by getting a signed timestamp signature, as anyone else who subsequently signs the same message (after removing Alice's signature) would have a higher timestamp.
      • Note that this requires the use of a widely-trusted source of time information. Without a trusted source of timestamps the only solution in a zero-trust distributed system is by using a distributed ledger (aka blockchain) - which is another topic in itself.
  • Alice wants to send a secret message to a single individual recipient (Bob):
    • Alice would encrypt her message using Bob's public-key.
    • Alice should also sign the message to allow Bob to know the message came from her and to ensure the message isn't tampered with in-transit.
    • Note that nothing stops Bob from redistributing the message after decrypting it - encryption still relies on trust: encryption can't protect data if you can't trust the intended recipient of a secret message to actually keep it secret.
  • Note that there is little point to encrypting a message using PKI without also signing it because (strictly speaking) encryption doesn't ensure message integrity (i.e. changing random bytes in an encrypted message in most crypto-systems will result in changed output (usually garbled output though, but some crypto-schemes like ECB mode can be successfully attacked without knowing any of the secret keys).
  • $\begingroup$ That's excellent thanks so much for taking the time to explain that. Re step 3, if I understand correctly, Bob can be sure that the box came from Alice, but not necessarily directly. If not directly from Alice, I guess that would make her deceptive in the interaction. Any example scenario where Alice would want to do that? $\endgroup$ – Alex Taylor May 11 '20 at 4:39
  • $\begingroup$ @AlexTaylor No, if something is signed (but not encrypted) by someone then it definitely either originated with that person or at least passed-through that person; but without additional information in the signed-message it's impossible to know the intended recipient (unless the message is encrypted with the recipient's public key - or the message signature includes information about its intended-recipient). As for indirect messages: No. Alice does not need to be deceptive (intentionally or otherwise) if Alice sent identical messages to other users (e.g. a newsletter). $\endgroup$ – Dai May 11 '20 at 5:44

The analogy for public key encryption works, with the catch that in reality, "anyone can get a replica of any padlock" is highly unusual, for it can't reasonably coexist with "only key owner can open it".

The analogy for digital signature is overly complex and far from practice: actual digital signature requires only one public/private key pair, that of the signer; when the analogy uses two. I find the analogy is only at best an argument against "impossible".

I dislike analogies that are remote from reality, especially when reality is at hand. We do not introduce electricity to kids with a water circuit analogy: we show it working, and how that's done. My advise is to do the same for public-key crypto, especially now that's in common use, and a computer language for beginners can do it (python supports large integers, allowing compact illustration). When the audience has grasped the principles of symmetric crypto, how public-key crypto works can be introduced stepwise:

  • Modular arithmetic with clock arithmetic, generalizing to any moduli.
  • Additional property of arithmetic modulo a safe prime $p$, starting with 11 instead of 12 or 23 instead of 24: when we multiply an element $g$ (other than 1 or -1) repeatedly, we obtain all elements except 0, or half these.
  • The transformation $x\mapsto y=g^x\bmod p$ can efficiently be computed (by putting $x$ in binary)
  • The reverse $y\mapsto x$ is much harder, to the point of being intractable for large $p$ (it should be stated that even though primes thin out, and safe prime even more so, there remains enough to be found; and that we can establish that a large integer is prime with a repeated use of Euler's test).
  • Diffie-Hellman key exchange, which is the ah ah moment.
  • Making that non-interactive to build public key encryption (e.g. with ElGamal encryption reduced to secret establishment, then using symmetric crypto on top of that unless the audience was exposed to group theory).
  • ElGamal or Schnorr signature.

Your Answer

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