# -*- coding: utf-8 -*-

# Blind signatures with RSA

''' Based on Chaum\'s untraceble payment system
http://www.hit.bme.hu/~buttyan/courses/BMEVIHIM219/2009/Chaum.BlindSigForPayment.1982.PDF '''


import random

"Modular division: http://www.math.harvard.edu/~sarah/magic/topics/division"
def divide(x, y, N):
    if y%N == 0: 
        return (0, 1, N)
    
    a = y; b = N; q = []
    
    while a % b != 0:
        q.append(-1*(a//b))
        (a,b)=(b,a%b)
    
    (a, b, gcd) = (1, q.pop(), b)
    
    while q:
        (a,b) = (b, b * q.pop()+a)
        
    return (x*a) % N


# Normal RSA init

p = 61
q = 53

n = p*q # 3233
e = 17
d = 2753

# Bank (TTP)
PublicKey  = (n, e)
PrivateKey = (n, d)

'''
The technique involves the User preparing a Blank that is blinded before being sent
to the Issuer to sign and return to the User. 

The User removes the blinding to obtain a signed Blank, i.e. a Token. 

The User gives the Merchant the Token in exchange for goods and 

the Merchant returns the Token to the Issuer to redeem the value once the Issuer has verified that the signature is valid.
'''

print ''' Starting points:
1. User has an account in the Bank
2. Merchant has an account in the Bank
3. Anything signed from the Bank has a value of 1 USD
'''

Note = 10 #random.randint(0,n) 
print '1.1) User creates a note of value 1 USD with serial number:',Note

r = 33 #random.randint(0, n)
print '1.2) User creates a random number to hide (blind) the serial number:',r

Note_blind = Note * (r**e) % n # blinded_message
print '1.3) User hides (blinds) the serial number of the note:',Note_blind
print "The user knows: Serial %d; Random blinder: %d; Blinded serial:%d "%(Note, r, Note_blind)

print ''
Bank_signature = (Note_blind**d) % n # Bank singnature
print '2.1) Bank signs the Blinded note: %d. Bank signature: %d'%(Note_blind, Bank_signature)
print '2.2) Bank returns the Bank signature to User and credits his account with 1USD'
print "The Bank knows: Blinded serial: %d; Signature over the blinded serial: %d"%(Note_blind, Bank_signature)

print ''

unblinded_signature_of_blind = divide( Bank_signature, r, n )
print '3.1) User strips the blinder and gets the signature over the real serial',unblinded_signature_of_blind 
Note_check = unblinded_signature_of_blind**e % n
print '3.1) User checks if the correct note is signed:',Note_check
print '3.3) User has payment Note serial: %d with Bank signature: %d' %(Note_check,unblinded_signature_of_blind)

print ''
print '4.1) User gives Note: %d with Unblinded Bank signature: %d to Merchant' %(Note,unblinded_signature_of_blind)
Check_Bank_signature = (unblinded_signature_of_blind**e) % n
print '4.2) Merchant checks Unblinded Bank signature: %d and confirms the Note serial: %d'%(unblinded_signature_of_blind, Check_Bank_signature)
print '4.3) Merchant accepts payment from User'
print '4.1) Merchant gives Note: %d with Unblinded Bank signature: %d to Bank' %(Note,unblinded_signature_of_blind)
print ''
Check_Bank_signature = (unblinded_signature_of_blind**e) % n
print '5.1) Bank checks its signature: %d over the Blinded Note: %d'%(unblinded_signature_of_blind, Check_Bank_signature)
print '5.2) Bank debits Merchant account'