I'm glad to see that people are willing go even longer distances than me for a practical joke. Unrelated, but this must be the only wikipedia page I know of that contains a joke.
I like these sorts of articles. Sometimes you just need to understand what's happening without going into the real detail. I've always learned best when there's an ELI5. I used to prefer the for dummies and idiots books for exactly this reason.
There was a video of someone describing cryptography during a lecture with the example of a secret locked by Alice and sent to Bob. Bob has no way of opening Alice’s lock, so they simply add their lock and send it back to Alice. Then Alice removes her lock and sends the secret back to Bob, who now can remove their own lock and access the secret.
What kind of cryptography is that? Does anyone know what lecture that was?
I sourced it from your link. I disagree that the above commenter is describing "PKI" and is specifically describing "DH Key Exchange" as evidenced by the image linked from the article you referenced.
Not exactly as you describe, but very similar and still a good explanation of simple key exchange is [1]. However I believe (Its a long time since college for me...) Diffie Helman as mentioned elsewhere is a bit more complex [2].
It isn't. That is an example where a physical system that would work[‡] does not when applied to mathematics, given as an example where physical world analogies do not translate to useful mathematical methods. It is used as part of the journey towards understanding remote key exchange and public key cryptography, such lectures usually follow the rough pattern:
1. That two-lock physical method is described, which won't work because there is no mathematical operation that can be applied and removed out of sequence like that which is also both not trivial to break/brute-force and doesn't require a pre-shared value which defeats the objective (if you can arrange to securely share that value then you can use that method to share the original secret).
2. But, what about modulo operations? Goes on to show how rotating through a prime modulus might have the same effect, pushing through to explaining a key exchange scheme like DH (where there are pre-shared parameters, but they do not need to be secret). Both parties end up with the same key without ever transmitting it, and can use that to encode the actual message(s).
3. But, key exchange like that, while effective and sufficiently difficult to crack assuming good parameter choices, relies upon both parties being in current contact or the latency is very high as it takes a few back-and-forths to decide the key that will be used to encode the message. What if I want to send a message to you right now, that you can read as soon as you receive it, without having to wait for you to be online so we can derive a secure key first?
4. Goes on to describe the scheme R, S, & A came up with (as did another group in GCHQ a little earlier, but their work was classified for decades so very few knew about it) using public & private key pairs and clever† application of co-prime numbers and modulo arithmetic, and the birth of public key encryption and signing.
--
[‡] ignoring the round-trip latency, and the need for truly indestructible boxes and locks!
[†] it might not seem so genius now as we've known about it for nearly half a century and other schemes are supplanting it, but it is one of those ideas that are relatively obvious once explained but not at all easy to come up with from scratch
> 1. That two-lock physical method is described, which won't work because there is no mathematical operation that can be applied and removed out of sequence like that which is also both not trivial to break/brute-force and doesn't require a pre-shared value which defeats the objective (if you can arrange to securely share that value then you can use that method to share the original secret).
That isn't exactly the issue. The key sharing problem is unavailable in both meat-space and math-space and so is irrelevant in context (it applies just as well to the physical locks). With key sharing not a concern, all you need is for your locks and keys to be commutative. That's easy#1 to do securely.
#1 Basically all "secure" cryptography other than a one-time pad is reducible to a "hard" problem, but last I checked those hard problems may have vulnerabilities we haven't discovered. Nobody has proven any of those techniques actually secure. However, that would be a criticism of all modern cryptography, not just commutative locks.
I think some of the current work on encrypted databases might wander into this territory.
I can't recall if symmetric ciphers are commutative or not. Specifically if:
f(f(x)) = x
g(g(x)) = x
are there cipher systems where
f(g(f(x))) = g(x)
because that's essentially the problem here. Any other encryption method would require Alice to know Bob's key, or is more easily solved with public key cryptography, where Alice just encodes the secret with Bob's public key and sends it to him.
Note that this requires the encryption to be commutative - in the third step Alice has a message in the form e_B(e_A(msg)), where e_B and e_A are Bob's and Alice's encryption functions. Alice must be able to apply her key to obtain e_B(msg), removing the inner encryption. This can be achieved with some modular exponentiation magic.
I don't know of any practical applications of this, probably because it requires both parties to be online at the same time, so they may as well use the simpler Diffie-Hellman key exchange.
Neat; but if I were non-technical person, the next question I would ask would be, why can't Mallory just forge Ted's certificate and use that to fool Alice or Bob? In this scenario, Alice or Bob would receive a box which has a certificate which looks very similar to what they remember Ted having.
What would be a good non-technical metaphor for that?
In reality of course, we use trustworthy browsers such as Firefox which (relatively invisibly) enforce certificate validity for us. I'm wondering where that would fit in the metaphor.
20 comments
[ 66.5 ms ] story [ 1474 ms ] threadFrom: https://en.wikipedia.org/wiki/April_Fools%27_Day_Request_for...
What kind of cryptography is that? Does anyone know what lecture that was?
What you described is the goto illustration used for PKI
https://en.m.wikipedia.org/wiki/Public-key_cryptography
https://upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Pu...
[1] https://www.youtube.com/watch?v=U62S8SchxX4 [2] https://www.youtube.com/watch?v=pa4osob1XOk
It isn't. That is an example where a physical system that would work[‡] does not when applied to mathematics, given as an example where physical world analogies do not translate to useful mathematical methods. It is used as part of the journey towards understanding remote key exchange and public key cryptography, such lectures usually follow the rough pattern:
1. That two-lock physical method is described, which won't work because there is no mathematical operation that can be applied and removed out of sequence like that which is also both not trivial to break/brute-force and doesn't require a pre-shared value which defeats the objective (if you can arrange to securely share that value then you can use that method to share the original secret).
2. But, what about modulo operations? Goes on to show how rotating through a prime modulus might have the same effect, pushing through to explaining a key exchange scheme like DH (where there are pre-shared parameters, but they do not need to be secret). Both parties end up with the same key without ever transmitting it, and can use that to encode the actual message(s).
3. But, key exchange like that, while effective and sufficiently difficult to crack assuming good parameter choices, relies upon both parties being in current contact or the latency is very high as it takes a few back-and-forths to decide the key that will be used to encode the message. What if I want to send a message to you right now, that you can read as soon as you receive it, without having to wait for you to be online so we can derive a secure key first?
4. Goes on to describe the scheme R, S, & A came up with (as did another group in GCHQ a little earlier, but their work was classified for decades so very few knew about it) using public & private key pairs and clever† application of co-prime numbers and modulo arithmetic, and the birth of public key encryption and signing.
--
[‡] ignoring the round-trip latency, and the need for truly indestructible boxes and locks!
[†] it might not seem so genius now as we've known about it for nearly half a century and other schemes are supplanting it, but it is one of those ideas that are relatively obvious once explained but not at all easy to come up with from scratch
That isn't exactly the issue. The key sharing problem is unavailable in both meat-space and math-space and so is irrelevant in context (it applies just as well to the physical locks). With key sharing not a concern, all you need is for your locks and keys to be commutative. That's easy#1 to do securely.
#1 Basically all "secure" cryptography other than a one-time pad is reducible to a "hard" problem, but last I checked those hard problems may have vulnerabilities we haven't discovered. Nobody has proven any of those techniques actually secure. However, that would be a criticism of all modern cryptography, not just commutative locks.
I can't recall if symmetric ciphers are commutative or not. Specifically if:
are there cipher systems where because that's essentially the problem here. Any other encryption method would require Alice to know Bob's key, or is more easily solved with public key cryptography, where Alice just encodes the secret with Bob's public key and sends it to him.Note that this requires the encryption to be commutative - in the third step Alice has a message in the form e_B(e_A(msg)), where e_B and e_A are Bob's and Alice's encryption functions. Alice must be able to apply her key to obtain e_B(msg), removing the inner encryption. This can be achieved with some modular exponentiation magic.
I don't know of any practical applications of this, probably because it requires both parties to be online at the same time, so they may as well use the simpler Diffie-Hellman key exchange.
Pity :-(
What would be a good non-technical metaphor for that?
In reality of course, we use trustworthy browsers such as Firefox which (relatively invisibly) enforce certificate validity for us. I'm wondering where that would fit in the metaphor.