Tomorrow (well, it’s past midnight so today, I guess), I’m supposed to give a talk on cryptography for my number theory course. While preparing it I realized there was one cool cryptographical protocol I hadn’t executed yet: secure coin flips.
Secure coin flips work like this:
- Alice picks a random number and hashes it (using a previously agreed-upon hash function — a hash function is a function that takes a message and scrambles it up) and reveals the hash.
- Bob tries to guess if the number Alice picked is even or odd. He doesn’t know the number, only the hash (which is designed to be practically impossible to reverse) so he’s making a shot in the dark. (To be particularly safe, Bob should probably try to flip a coin of his own.) He tells Alice his guess.
- Alice then reveals whether he was right or wrong, and the original number. Bob can verify Alice isn’t cheating by hashing the number and making sure it’s the same as the hash Alice revealed in step 1.
Wanna flip with me? 256bcc724e035a29cac6e9b676b56210641f229f — even or odd?
The one way to cheat is to find both an odd and an even number that hash to the same thing. Using a regular hash function this should be pretty hard to do, but that hasn’t stopped me from looking for one. ;-)
import sha
h, i = {}, 0
while 1:
i += 1
c = sha.new(`i`).hexdigest()
if c in h: print "Whoa! it works for", i, "and", h[c]
else: h[c] = i
posted April 15, 2002 12:13 AM () #