Socialist Millionaire Problem with GoWith the socialist millionaire problem (SMP) - aka as the Off-the-Record Messaging protocol - we need to show that two millionaires either have the same amount of money or not, and without revealing their own value: |
Theory
With the socialist millionaire problem (SMP), we need to show that the two millionaires either have the same amount of money or not. First the two millionaires (Bob and Ailce), create public values of \(p,h\) and where \(p\) is a prime number and \(h\) is the base of the discrete logarithm operation. The prime number is used to create a finite field, and where each of the operations are done \(\pmod p\).
Alice then creates a message (\(x\)) and three random values: \(a,\alpha ,r\).
Bob then creates a message (\(y\)) and three random values: \(b,\beta ,s\).
Bob and Alice now have to prove the \(x\) and \(y\) are the same, without revealing their values.
Alice sends Bob, \(h^a\) and Bob sends Alice \(h^b\). They then use the Diffie-Hellman method to create a shared value of:
\(g = h^{ab}\)
Alice sends Bob, \(h^{\alpha}\) and Bob sends Alice \(h^{\beta}\). They then use the Diffie-Hellman method to create a shared value of:
\(\gamma = h^{\alpha\beta}\)
Next Alice creates and sends Bob these values:
\(P_a=\gamma^r\)
and:
\(Q_a=h^r g^x\)
Bob creates and send Alice these values:
\(P_b=\gamma^s\)
and:
\(Q_b=h^s g^y\)
They then use the Diffie-Hellman method to come up with:
\(c=(Q_{a} Q_{b}^{-1})^{\alpha \beta }\)
and also:
\(c'=P_a P_b^{-1}\)
They then test if \(c=c'\). If they are, the values that Bob and Alice have are the same.
This works because:
\(\begin{aligned}P_{a}P_{b}^{-1}&=\gamma ^{r}\gamma ^{-s}=\gamma ^{r-s}\\&=h^{\alpha \beta (r-s)}\end{aligned}\)
Therefore:
\( \begin{aligned}c&=\left(Q_{a}Q_{b}^{-1}\right)^{\alpha \beta }\\&=\left(h^{r}g^{x}h^{-s}g^{-y}\right)^{\alpha \beta }=\left(h^{r-s}g^{x-y}\right)^{\alpha \beta }\\&=\left(h^{r-s}h^{ab(x-y)}\right)^{\alpha \beta }=h^{\alpha \beta (r-s)}h^{\alpha \beta ab(x-y)}\\&=\left(P_{a}P_{b}^{-1}\right)h^{\alpha \beta ab(x-y)}\end{aligned} \)
And thus if \(x=y\), we get:
\(P_a P_b^{-1}\)
Coding
The following provides the code [code]. In this case we covert the message to a Big Int, in order to operate on it:
package main import ( "github.com/cowlicks/socialist-millionaire-go" "fmt" "os" ) func main() { pub := smp.NewPublic() m1:="Hello" m2:="Goodbye" argCount := len(os.Args[1:]) if (argCount>0) {m1= string(os.Args[1])} if (argCount>0) {m2= string(os.Args[2])} msgalice := []byte(m1) msgbob := []byte(m2) n:=60 // Chars to show of Big Int // Create the parties alice := smp.NewPerson(pub, msgalice) bob := smp.NewPerson(pub, msgbob) fmt.Printf("==Alice parameters (truncasted first %d chars)==\n",n) fmt.Printf("Prime: %s\n",(alice).P.String()[:n]) fmt.Printf("g (base): %s\n",(alice).G1.String()[:n]) fmt.Printf("Secret: %s\n",(alice).Secret.String()) fmt.Printf("Exp1: %s\n",(alice).Exp1.String()[:n]) fmt.Printf("Exp2: %s\n",(alice).Exp2.String()[:n]) fmt.Printf("Exp3: %s\n",(alice).Exp3.String()[:n]) fmt.Printf("\n==Bob parameters (truncasted first %d chars)==\n",n) fmt.Printf("Prime: %s\n",(bob).P.String()[:n]) fmt.Printf("g (base): %s\n",(bob).G1.String()[:n]) fmt.Printf("Secret: %s\n",(bob).Secret.String()) fmt.Printf("Exp1: %s\n",(bob).Exp1.String()[:n]) fmt.Printf("Exp2: %s\n",(bob).Exp2.String()[:n]) fmt.Printf("Exp3: %s\n",(bob).Exp3.String()[:n]) // Alice and Bob secure some values with Diffie-Hellman exchanges alice.FirstKeyReceive(bob.FirstKeySend()) bob.FirstKeyReceive(alice.FirstKeySend()) // They do another exchange of derived values alice.SecondReceive(bob.SecondSend()) bob.SecondReceive(alice.SecondSend()) // Final exchange alice.FinalReceive(bob.FinalSend()) bob.FinalReceive(alice.FinalSend()) // They check if their secret messages were the same //fmt.Printf("Bob details base: %s\n",bob) fmt.Printf("\nBob checks message: %v\n",bob.Check()) fmt.Printf("Alice checks message: %v", alice.Check()) }
And a sample run:
==Alice parameters (truncated first 60 chars for Big Ints)== Alice message: $1000 Prime: 208377547780369483084186412308320683874733610481954110027380 g (base): 164800197169104954668640411878892798099760272065720764974947 Secret: 155444064304 Exp1: 143670080153724033765766132162880753598165235495801544409523 Exp2: 191798691993487773724351508865038086793100766799489639860591 Exp3: 149982282211908603133252102086415762969084371998208330024049 ==Bob parameters (truncated first 60 chars for Big Ints)== Bob message: $1000 Prime: 208377547780369483084186412308320683874733610481954110027380 g (base): 164800197169104954668640411878892798099760272065720764974947 Secret: 155444064304 Exp1: 163618767301267085382108027583064554978259246312642480229980 Exp2: 193862404423280266026149369480445305832538817401826374981904 Exp3: 432952157101636852450200548978485840810466648938237415677055 Bob checks message: true Alice checks message: true