A blinding signature allows Bob to sign a messsage, without knowing the message. One of the first methods for this was proposed by David Chaum [1], and uses the RSA method as a core for signing a message.
Blinded signatures (Chaum) |
Theory
With a blinded signature, Bob can sign for a message, without knowning what the message is. The Chaum method uses RSA encryption. With this Bob creates his RSA keys in the usual way, and where he selects two prime numbers (\(p\) and \(q\)) and an encryption key value (\(e=65,535\)) and then computes:
\(n=p \times q\)
\(\Phi=(p-1)(q-1)\)
\(d = e^{-1} \pmod {\Phi}\)
Now Alice has a message (\(m\)) that she wants Bob to blind sign. She first generates a random value (\(k\)) and will then compute:
\(m^* = m k^e \pmod {n}\)
She sends this to Bob, and who uses his private key (\(d\)) to compute:
\(s^* = {m^*}^d \pmod {n}\)
Bob sends this back, and Alice computes the true signature from Bob:
\(s=k^{-1} s^* \pmod n\)
This value is the signature for the message, signed with Bob's private key, and should be the same as:
\(s=m^d \pmod n\)
This is the signature that Bob would have produce if he had signed the message with his private key (\(d\)) and for a message (\(m\)). This works because:
\(s=k^{-1} s^* = s=k^{-1} {m^*}^d = k^{-1} {m k^e}^d = k^{-1} m^d k^{ed} = k^{-1} m^d k^{1} = m^d \pmod n \)
Coding
The coding is here:
import random import libnum from Crypto.Util.number import getPrime from Crypto.Random import get_random_bytes import sys primebits=32 if (len(sys.argv)>1): primebits=int(sys.argv[1]) if (primebits>512): primebits=512 q = getPrime(primebits, randfunc=get_random_bytes) p = getPrime(primebits, randfunc=get_random_bytes) n=p*q PHI=(p-1)*(q-1) e=65537 d=libnum.invmod(e,PHI) print ("e=",e) print ("d=",d) print ("n=",n) k=random.randint(1,n-1) m=10 mstar = (m*pow(k,e,n)) % n sstar = (pow(mstar,d,n)) % n s = (pow(k,-1,n)*sstar) % n print ("\nk: ",k) print ("m*: ",mstar) print ("s*: ",sstar) print ("\nBob signing (Blinded): ",s) s= pow(m,d,n) print ("Bob's signing of message: ",s)
A sample run is:
e= 65537 d= 45660015695261054226217809348211017317484918229747210239714041634497573234801 n= 63622495399505117804644226968867318151973966739151000701138035971396026116259 k: 5133742595325447731602784002338778030284753671553334855663554181261758894874 m*: 27982485328699077215295024281422102642098647825770659374060497139186067401419 s*: 38107181932992184644418690264945069826643556093385949097757693297533502122059 Bob signing (Blinded): 48745119194223367345844639692786566212837875588499951868750614972736019786990 Bob's signing of message: 48745119194223367345844639692786566212837875588499951868750614972736019786990
and:
e= 65537 d= 127880251735988000575126089065260328387708208890517791206528756136604050918338306627007788261966773669526240049407508526113585273423778111213508188685048207123537706200887966419652140931313227847015293708655254425540100515807203336980749321212384259580788935032548168038862618732910676106410054013964798335777 n= 150746241780369911390964071139469856492287806425963459283082867309242026135605755835207738314348450355776336321282464318942118822655841176965963129754874554206441769875757798784046577208874240649011615562549812098164316598013526220888740264733033871367059848108204696401428898139354071300778000731414871344843 k: 6925171139294179012448028649002254226228344011157037104207589643910855779594136252508625825906626186352732437390931454591002100800946568393361590971714687242628652049173427033417789104428203264731916837641117088542524670172786493028854943514004554219880945434608885864800114455457882476937253875389200926772 m*: 103809045696866241855924045409378672500546734598109078439734084682156465456529771823417554152571241557378961357197339635128414863437400214248230244626826104424853228704233491398081115162140557685088562802915336952205466614768316246788694035804480870455532410750314430096238813429725526601224244367671807779919 s*: 65541554606064125850629870117011173942289616060512629605569306672486654483317523689689173876843250415277907197155244072466588672577364645720577818784005277805969022756763838884583313395860764806268767090786918898578855191174522636478156304158548468362595276257586348847145393184663130686798847065691826452679 Bob signing (Blinded): 52911517504771027462808016303440315285493505550610649840751747392567132893264183929758444558583281685773740185032138839836285641479036295637611571093531776380066744658564988325881044794130051574063237887909949021636304407747608575172643448116681316130430798758027581527584318351917018271081993862021725064999 Bob's signing of message: 52911517504771027462808016303440315285493505550610649840751747392567132893264183929758444558583281685773740185032138839836285641479036295637611571093531776380066744658564988325881044794130051574063237887909949021636304407747608575172643448116681316130430798758027581527584318351917018271081993862021725064999
References
[1] Chaum, D. (1983). Blind signatures for untraceable payments. In Advances in cryptology (pp. 199-203). Springer, Boston, MA [here].