# post_election_audit.py # Ronald L. Rivest # October 4, 2009 # # This Python program is for use with the Scantegrity II election system. # See www.scantegrity.org for information on Scantegrity II. # # It was written specifically for the version of Scantegrity II used # in the Takoma Park, Maryland election of November 3rd, 2009. It # may need slightly modifications for use with other versions of # Scantegrity. # # This program is invoked as: # # python post_election_audit.py randomDataFileName firstInFileName secondInFileName outFileName \ # same_side instance_list # # randDataFileName must be given; it is arbitrary file name (e.g. stock price data) # if firstInFileName is omitted, it is MeetingOneIn.xml # if secondInFileName is omitted, it is MeetingThreeOut.xml # if outFileName is omitted, it is MeetingFourIn.xml # same_side is 1 for having all tests on same side, 0 mixed (default mixed) # instance_list is list of integers separated by : (colon) e.g. 1:2:6:8:9 # (default all instances if omitted, or if ALL (in caps) is specified) # # IMPORTS # import base64 import hashlib import sys from xml.etree import ElementTree as etree # # PSEUDO-RANDOM NUMBER GENERATOR # def prn(seed,index,modulus): """ Return pseudo-random number based on seed, index, and modulus: seed is arbitrary byte string index is integer to distinguish different calls modulus specifies what the output modulus is; value is between 0 and modulus-1 """ # Append decimal representation of index at end of seed to form hash input hash_input = seed + "%d"%index # Apply SHA1 hash function to get a byte sequence of length 20 bytes (160 bits), # encoded as 40 hex digits. hash_output = hashlib.sha1(hash_input).hexdigest() # Return hash output (treated as integer) modulo given modulus hash_value = int(hash_output,16) # interpret hash output as a base-16 integer output_value = hash_value % modulus # mod modulus ==> output value return output_value # # ROUTINE FOR READING XML MEETING ONE INPUT FILE # def read_MeetingOneIn(inFileName): """ Read the XML input file inFileName, and return the values found therein of noBallots (number of ballots) constant (election identifier) noDs (number of D tables) """ doc = etree.parse(inFileName) root = doc.getroot() for node in root: if node.tag == "noBallots": noBallots = int(node.text) if node.tag == "constant": constant = base64.decodestring(node.text); if node.tag == "noDs": noDs = int(node.text); return (noBallots,constant,noDs) def main(): args = sys.argv[1:] print print " Scantegrity II Post-Election Audit Challenge Generator" print " Version 1.1. October 26, 2009." print if len(args) == 0: print ' usage: python post_election_audit.py randomDataFileName firstInFileName secondInFileName outFileName' \ " same_side instance_list" print " randDataFileName must be given; it is arbitrary file name (e.g. stock price data)" print " if firstInFileName is omitted, it is MeetingOneIn.xml" print " if secondInFileName is omitted, it is MeetingThreeOut.xml" print " if outFileName is omitted, it is MeetingFourIn.xml" print " same_side is 1 for having all tests on same side, 0 mixed (default mixed)" print " (*** the program will not run if same_side = 0 and the firstInFileName specifies" print " noDs -- that is, number of D tables -- to be greater than one, as this" print " would very likely result in loss of voter privacy ***)" print " instance_list is list of integers separated by : (colon) e.g. 1:2:6:8:9" print " (default all instances if omitted, or if ALL (in caps) is specified)" print sys.exit(-1) randomDataFileName = args[0] if len(args) >= 2: firstInFileName = args[1] else: firstInFileName = "MeetingOneIn.xml" if len(args) >= 3: secondInFileName = args[2] else: secondInFileName = "MeetingThreeOut.xml" if len(args) >= 4: outFileName = args[3] else: outFileName = "MeetingFourIn.xml" if len(args) >= 5: same_side = int(args[4]) else: same_side = 0 # mixed if len(args) >= 6: instance_list = ":"+args[5]+":" # e.g. :1:2:4:5: else: instance_list = "ALL" # read random data seed from file print " Step 1. Obtain random data seed from:",randomDataFileName f = open(randomDataFileName,"rb") seed = f.read() f.close() # Read XML input (MeetingOneIn.xml file by default) (noBallots,constant,noDs) = read_MeetingOneIn(firstInFileName) print " Step 2. Read input file:", firstInFileName print " Number of ballots = ",noBallots print " constant = '",constant,"'" print " noDs (number of D tables) = ",noDs # check that row-wise reveals are not being used inappropriately # i.e., when noDs is greater than 1 # if so, abort if same_side == 0 and noDs > 1: print "Error: same_side is specifed as 0 (row-wise reveals)" print " but noDs (number of D tables) is greater than 1" print " This would lead to loss of voter privacy !!" print " Input error. Program is terminating." sys.exit(1) # append election constant to seed seed = seed + constant print " Step 3. Producing output file:", outFileName file = open(outFileName,"w") file.write("\n \n") doc = etree.parse(secondInFileName) root = doc.getroot() database_node = root[0] counter = 0 for partition_node in database_node: partition_id = partition_node.get("id") file.write(' \n \n'%partition_id); decrypt_node = partition_node[0] for instance_node in decrypt_node: instance_id = instance_node.get("id") instance_side = ("LEFT","RIGHT")[prn(seed,counter,2)] counter+=1 if ((":"+instance_id+":") in instance_list) or (instance_list == "ALL"): file.write(' \n'%instance_id) for row_node in instance_node: row_id = row_node.get("id") if same_side == 1: row_side = instance_side else: row_side = ("LEFT","RIGHT")[prn(seed,counter,2)] counter+=1 file.write(' \n'%(row_id,row_side)) file.write(' \n') file.write(" \n \n"); file.write(" \n\n") file.close() print " Done." print sys.exit(0) # normal return if __name__ == '__main__': main()