Python implementation of Rivest's Time-lock Puzzles

TimeLockPuzzle.py

'''
Python implementation of Rivest's Time-lock Puzzles as described 
here: http://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt
'''

import time


def GenPuzzle(t, p, q):
	n = p*q
	phi = (p-1)*(q-1)
	return pow(2, pow(2, t, phi), n)


def SolPuzzle(t, n):
	s = 2
	for i in range(t):
		s = pow(s, 2, n)
	return s

if __name__ == '__main__':
	
	p = pow(2,541)-1	#a large prime
	q = pow(2,523)-1	#another large prime
	t = 1000000			#number of time slots desired
	
	start_time = time.time()
	print GenPuzzle(t, p, q)
	print 'GenPuzzle took', time.time() - start_time, "seconds\n"
	
	start_time = time.time()
	print SolPuzzle(t, p*q )
	print 'SolPuzzle took', time.time() - start_time, "seconds"

This code has a fundamental flaw: If you use mersenne primes to generate the private keys p and q, then determining the totient function from n is simple and this implementation can be easily hacked. You are supposed to use truely random primes p and q!

Try this code!

def HackPuzzle(t, n):
    '''
    can't use mersenne primes for randomness generations!

    (2^a-1)*(2^b-1)=2^(a+b)-2^a-2^b+1=n
    Its easy to recover them from n!
    '''
    n-=1
    ilog2=0
    while((1 << ilog2) < n):
        ilog2+=1    
    testmask=(1<<ilog2)-1
    mab=0
    while(testmask & n != testmask):
        testmask-=(1<<mab)
        mab+=1
    mab-=1
    a=mab
    b=ilog2-mab
    p=pow(2,a)-1
    q=pow(2,b)-1
    return GenPuzzle(t,p,q)

outputs:
98828848242696786595841466340205284396711694689568069660144790189953254284686481792464819000669611689231075459879472786415175828643125065382464963453516956350166411805733951927035790611878526487766408345837567283094813621549876982789800508667370998886591427946864058609744146928254374716500118944835639206073778172985345
HackPuzzle took 0.00362491607666 seconds