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:

  1. 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.
  2. 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.
  3. 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 =`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 () #


Aaron Swartz Movies
Today’s Hack: display.cgi
Rescued Data
Visiting Boston, Cambridge
Secure Coin Flipping
Putting Books Online Increases Sales
Boston Trip
NYTimes on Google’s DMCA Issues
Motion Blur

Aaron Swartz (