Cosu

In the past two weeks we had a lottery-type thing on RGC.ro (Romanian Guitarist Community). Proguitar, the official importer of Fender products in Romania, wanted to give-away a custom made Fender Stratocaster electric guitar. To register, the community users had to fill out a form and choose from a series of custom options for the guitar.

As organizers we had to pick out the lucky winner of the raffle. Usually this is done by someone who is impartial. Due to the fact that we had about 1600 entries and that we are geeks we wanted to do something that geeks would do. Therefore we ditched the “extract the name of the lucky winner from a bowl”. The geek version of this is described in RFC2777 – Publicly Verifiable Nomcom Random Selection

In short RFC2777 describes a simple publicly verifiable algorithm to pick out a set of entries from a group as random as possible. The keywords here are public – anyone can see how the entries are picked – and as random as possible. To have random values a thing called information entropy is needed. To get that initial random value full of juicy entropy we used, as suggested in the RFC, the results from three international lotteries. This initial random value was slightly modified for each “extracted” entry and then transformed into a MD5 hash. Due to the nature of a hash when slightly modifying the original the resulting hash differs heavily from the original hash.

Below you can find a naive python implementation that can be freely used for any purpose. Just make sure you fill in the entropySource with a good initial random value.

import md5                                                 

if __name__ == '__main__':

    entropySource = "9.24.30.32.36.40./18.25.35.43.46.47./1.3.4.8.23.31./"

    numberOfEntries = 1655
    numberOfWinners = 10  

    numbers = map( lambda x: x + 1, range( numberOfEntries ) )

    i = 0
    entries = numberOfEntries
    print "index \t hex value of MD5 \t div \t selected"
    while ( i < numberOfWinners ) :
        md5hash = md5.new()
        md5hash.update( chr( i ) + entropySource + chr( i ) )
        val = int( md5hash.hexdigest(), 16 )
        modulo = val % entries
        print str( i + 1 ) + "\t" + md5hash.hexdigest() + "\t" + str( entries ) + "\t" + str( numbers[modulo] )
        del numbers[modulo]
        i += 1
        entries -= 1