In Millionaire's Problem, we can determine which of two millionaires has the most money, without them actually giving away the amount of money they have. In this case we will use the RSA method and use a given number of bits for each of the prime numbers used for the modulus [article].
Millionaire's Problem with real-life RSA example |
Method
The method involves us using RSA encryption. Bob first selects two prime numbers (\(p\) and \(q\)) and computes a modulus:
\(N=p \times q\)
Bob uses a typically encryption key of:
\(e=65537\)
Bob computes PHI with:
\(PHI = (p-1)(q-1)\)
Bob then computes the decryption key (\(d\)) as:
\(d = e^{-1} \pmod {PHI}\)
We define \(I\) as Bob's millions, and \(J\) as Alice's millions:
J =4 I =5
Alice selects a random number \(U\):
U=randint(0,2**16)
And she then computes the \(C\) value (which is the RSA encryption process):
\(C=U^e \mod N\)
Bob and Alice now agree a new prime number (\(z\)) and Alice calculates:
\(m=C - J + 1\)
She shares this with Bob. He then takes this value, and he adds one onto each one and generates 10 values:
\(Z_1 = (((m+1)^d) \mod N) \mod z \\ Z_2 = (((m+2)^d) \mod N) \mod z \\ ..\\ Z_{10} = (((m+2)^d) \mod N) \mod z \\ \)
He sends these to Alice, and Alice now computes:
\(G = U \pmod z\)
She can return this value back to Bob. If the j-th value is the same as \(G\), Alice has more money or the same, else Bob has more money.
Coding
In this case the value of \(bits\) is the number of bits in the prime number, \(I\) is the millions that Bob has, and \(J\) is the millions than Alice has:
import sys from random import randint from Crypto.Util.number import getPrime import Crypto import libnum J = 4 I = 5 bits=120 if (len(sys.argv)>1): I=int(sys.argv[1]) if (len(sys.argv)>2): J=int(sys.argv[2]) if (len(sys.argv)>3): bits=int(sys.argv[3]) p = getPrime(bits, randfunc=Crypto.Random.get_random_bytes) q = getPrime(bits, randfunc=Crypto.Random.get_random_bytes) N = p*q PHI=(p-1)*(q-1) e=65537 d=libnum.invmod(e,PHI) z=getPrime(bits, randfunc=Crypto.Random.get_random_bytes) U=randint(0,2**(bits//2)) C=pow(U,e,N) print('Bob has',I,'millions') print('Alice has',J,'millions') print ('Number of bits in primes:',bits) print('\ne=',e,'d=',d,'\nN=',N,'z=',z) print('\nRandom Value U is:\t',U) print('C value is (U^e %N):\t',C) m = C - J + 1 print("Alice shares this value (C-J-1):",m) Z=[] for x in range(0,10): val = (pow(m+x,d, N)) % z if (x>(I-1)): Z.append(val+1) else: Z.append(val) G = U % z print("\nG value is",G) print("Z values are:") for x in range(0,10): print(Z[x],end=' ') print('\n\nAlice checks U(',U,') against the ',J,'th value (',Z[J-1],')') if (G==Z[J-1]): print("\nBob has more money or the same") else: print("\nAlice has more money")
And a sample run:
Bob has 1 millions Alice has 4 millions Number of bits in primes: 120 e= 65537 d= 770471134956821801939909791310523347230071795120742421920897566201886465 N= 787940309151507871445850258927622631580744465104723004115711942719325789 z= 1059087040792523647134396345815782339 Random Value U is: 984003487085359939 C value is (U^e %N): 244730587296951478732099212522601766601499793583587617445640552476528359 Alice shares this value (C-J-1): 244730587296951478732099212522601766601499793583587617445640552476528356 G value is 984003487085359939 Z values are: 694739033169994812653052260480677119 416680254166531596348098016365338834 778824259049143910406344510017969540 984003487085359940 467610720509671559581965106779176525 910857539099846970898496032275496636 270655113053411213058544385823164265 253556438069990336311898691915880658 84516997256631983194028384729281625 148093822151575868641697089927816886 Alice checks U( 984003487085359939 ) against the 4 th value ( 984003487085359940 ) Alice has more money
and here is an example using 512-bit prime numbers:
Bob has 1 millions Alice has 4 millions Number of bits in primes: 512 e= 65537 d= 55503117782825313482183284884478139620541950021518596342100985231636059674674715696623206408888905523517260982968507669176093082000989997297551971512131385259625547444012126313643024973955694719851677475587728540212680752715414214523166338616033227125561477175614107475553170016288947896603237093108417514737 N= 94179836629288832293758795056677208821465390533108879384622434019256205962746468234202290822032265781911056444108616293783331494578331083884982097635879018943411920573543993133931040642555587578781200236316092457463497297823990148622344101001199640654068335777685654135601766936913122687488230037714144223107 z= 11599249924589324381707313551354572349545744850826684051484116814855289747798557751632579168773503276374411446921642452254564130889791775818042773737152109 Random Value U is: 69141848635073496079467523212481138754945926293657116978800172622919090326225 C value is (U^e %N): 76681819421651653034502936618544959135860742522740814272563410027023643791938380015764292992460837696301608018240954239418813941359118007397030348051890548010904584933580690777385846537271132395686473928762066617428203248637412665996945854312749879594495695599925301914331172635499739699335315312435721744092 Alice shares this value (C-J-1): 76681819421651653034502936618544959135860742522740814272563410027023643791938380015764292992460837696301608018240954239418813941359118007397030348051890548010904584933580690777385846537271132395686473928762066617428203248637412665996945854312749879594495695599925301914331172635499739699335315312435721744089 G value is 69141848635073496079467523212481138754945926293657116978800172622919090326225 Z values are: 664090998280560872025531886722586910809815265519987884179273777985174858799128588903572359252265870823417928521091940546553505415989750088076409969483560 8626546353006576161085888920987367703375406037721153658081935627884165171638563097291915628613630845905852239908678757106742869373495775827099898942863728 6800411854136894247512939950750818073370219068586264476775079304085690855761802658283220915404432134115125922858417319280949434154424471711756375255523690 69141848635073496079467523212481138754945926293657116978800172622919090326226 8835149884555011787134806028241862240798394597699056697423972319840877511041217437958311919006301867105709178010051563415173896156275682672073763055108858 9048773277450124991591990077265784077964184949835686735979493807057599964492691640674011433857061409058728984606077444843518380055507714942715101604142184 1816977116794807351588250937510447482672918223213021419262659848145600023081573699717771116724490767278390362525797393642519172033479085604314773688097220 3625438784281930758712289392513529494682272132334107057318382233276188662734217446635850917046113879414567834322869019127412243277651426884896589720235638 4993545969753190050099174114774910863650620565147075358272639082731002606434947521188263117794747957001184141981882870612559493783732170191348629677452439 11051159759467877744455360699332744714559334808046069846219211241860875164722753744453832918757808359844342274945059769995441064812741626983068749288051559 Alice checks U( 69141848635073496079467523212481138754945926293657116978800172622919090326225 ) against the 4 th value ( 69141848635073496079467523212481138754945926293657116978800172622919090326226 ) Alice has more money
A more formal definition is [here]: