With ElGamal public key encryption we have a public key of \((Y,g,p)\) and a private key of \((x)\). The cipher has two elements (\(a\) and \(b\)). With this, Bob selects a private key of \(x\) and the calculates Y (\(g^x \pmod p\)) for his public key. We can use it for partial homomorphic encryption, and where we can add the ciphered values. With this we encrypt two integers, and then add the ciphered values, and then decrypt the result.
Partial Homomorphic Encryption with ElGamal (Addition) |
Theory
With ElGamal encryption, initially Bob creates his public key by selecting a \(g\) value and a prime number (\(p\)) and then selecting a private key (\(x\)). He then computes \(Y\) which is:
\(Y=g^x \pmod p\)
His public key is then \((Y, g, p)\) and he will send this to Alice. Alice then creates a message for Bob (\(M\)) and selects a random value (\(k\)). She then computes \(a\) and \(b\):
\(a=g^k \pmod p\)
\(b=Y^k M \pmod p\)
Bob then receives these and decrypts with:
\(M=\frac{b}{a^x} \pmod p\)
This works because \(\frac{b}{a^x} \pmod p = \frac{Y^k M}{ {(g^k)}^x } \pmod p = \frac{{(g^x)}^k M}{ {(g^k)}^x } \pmod p = = \frac{g^{xk} M} { g^{xk} } \pmod p = M \)
Now with additive homomorphic encryption, we change the encryption to be:
\(a=g^k \pmod p\)
\(b=Y^k g^M \pmod p\)
Notice that instead of \(b=Y^k M \pmod p\) we now have \(b=Y^k g^M \pmod p\).
The result of the decryption then gives:
\(Result = \frac{b_1 b_2}{a_1^x a_2^x} = g^{M_1+M_2} \pmod p\)
Then just need to brute force the resulting value to find a value which matches \(g^i\).
The working out is:
\(a_1=g^{r_1} \pmod p\)
\(b_1=g^{M_1} Y^{r_1} \pmod p\)
\(a_2=g^{r_2} \pmod p\)
\(b_2=g^{M_2} Y^{r_2} \pmod p\)
and then:
\(Result = \frac{b_1 b_2}{a_1^x a_2^x} = \frac{g^{M_1} Y^{r_1} g^{M_2} Y^{r_2}}{ { (g^{r_1})}^x {(g^{r_2})}^x } = \frac{ g^{M_1+M_2} {g^x}^{r_1} {g^x}^{r_2} } { g^{x r_1} g^{x r_2} }= g^{M_1+M_2} \pmod p \)
We then search the result for possible values of \(M_1+M_2\).
Code
The coding is [from here]:
package main import ( "crypto/rand" "math/big" "io" "fmt" "os" "strconv" ) func get_g_p(size string)(g, p *big.Int) { if (size=="512") { p,_ = new(big.Int).SetString("FCA682CE8E12CABA26EFCCF7110E526DB078B05EDECBCD1EB4A208F3AE1617AE01F35B91A47E6DF63413C5E12ED0899BCD132ACD50D99151BDC43EE737592E17",16) g,_ = new(big.Int).SetString("678471B27A9CF44EE91A49C5147DB1A9AAF244F05A434D6486931D2D14271B9E35030B71FD73DA179069B32E2935630E1C2062354D0DA20A6C416E50BE794CA4",16) } if (size=="768") { p,_ = new(big.Int).SetString("E9E642599D355F37C97FFD3567120B8E25C9CD43E927B3A9670FBEC5D890141922D2C3B3AD2480093799869D1E846AAB49FAB0AD26D2CE6A22219D470BCE7D777D4A21FBE9C270B57F607002F3CEF8393694CF45EE3688C11A8C56AB127A3DAF",16) g,_ = new(big.Int).SetString("30470AD5A005FB14CE2D9DCD87E38BC7D1B1C5FACBAECBE95F190AA7A31D23C4DBBCBE06174544401A5B2C020965D8C2BD2171D3668445771F74BA084D2029D83C1C158547F3A9F1A2715BE23D51AE4D3E5A1F6A7064F316933A346D3F529252",16) } if (size=="1024") { p,_ = new(big.Int).SetString("FD7F53811D75122952DF4A9C2EECE4E7F611B7523CEF4400C31E3F80B6512669455D402251FB593D8D58FABFC5F5BA30F6CB9B556CD7813B801D346FF26660B76B9950A5A49F9FE8047B1022C24FBBA9D7FEB7C61BF83B57E7C6A8A6150F04FB83F6D3C51EC3023554135A169132F675F3AE2B61D72AEFF22203199DD14801C7",16) g,_ = new(big.Int).SetString("F7E1A085D69B3DDECBBCAB5C36B857B97994AFBBFA3AEA82F9574C0B3D0782675159578EBAD4594FE67107108180B449167123E84C281613B7CF09328CC8A6E13C167A8B547C8D28E0A3AE1E2BB3A675916EA37F0BFA213562F1FB627A01243BCCA4F1BEA8519089A883DFE15AE59F06928B665E807B552564014C3BFECF492A",16) } return } type PublicKey struct { G, P, Y *big.Int } type PrivateKey struct { PublicKey X *big.Int } func Encrypt(random io.Reader, pub *PublicKey, msg string) (a, b *big.Int, err error) { k, _ := rand.Int(random, pub.P) m,_ := new(big.Int).SetString(msg, 10) a = new(big.Int).Exp(pub.G, k, pub.P) s := new(big.Int).Exp(pub.Y, k, pub.P) gm :=new(big.Int).Exp(pub.G, m, pub.P) b = s.Mul(s, gm) b.Mod(b, pub.P) return } func Decrypt(priv *PrivateKey, a, b *big.Int) (msg *big.Int, err error) { s := new(big.Int).Exp(a, priv.X, priv.P) s.ModInverse(s, priv.P) s.Mul(s, b) s.Mod(s, priv.P) return s, nil } func valint(a []byte)(i int) { if (len(a)==1) { i=int(a[0])} if (len(a)==2) { i=(int(a[0])<<8)+ int(a[1])} if (len(a)==3) { i=(int(a[0])<<16)+ int(a[1])<<8+int(a[2])} if (len(a)==4) { i=(int(a[0])<<24)+ int(a[1])<<16+int(a[2])<<8+int(a[3])} return } func main() { x:="40" plen:="512" val1:="4" val2:="4" argCount := len(os.Args[1:]) if (argCount>0) {val1 = string(os.Args[1])} if (argCount>1) {val2 = string(os.Args[2])} if (argCount>2) {x = string(os.Args[3])} if (argCount>3) { plen =string(os.Args[4]) } fmt.Printf("Prime number size: %s\n\n",plen) xval,_ := new(big.Int).SetString(x, 10) g,p:=get_g_p(plen) priv := &PrivateKey{ PublicKey: PublicKey{ G: g, P: p, }, X: xval, } priv.Y = new(big.Int).Exp(priv.G, priv.X, priv.P) a1, b1, _ := Encrypt(rand.Reader, &priv.PublicKey, val1) a2, b2, _ := Encrypt(rand.Reader, &priv.PublicKey, val2) message2, _ := Decrypt(priv, a1.Mul(a1,a2), b1.Mul(b1,b2) ) fmt.Printf("====Values (val1=%s and val2=%s)\n",val1,val2) fmt.Printf("====Private key (x):\nX=%d",priv.X) fmt.Printf("\n\n====Public key (Y,G,P):\nY=%d\nG=%d\nP=%d",priv.Y,priv.PublicKey.G,priv.PublicKey.P) fmt.Printf("\n\n====Cipher (a1=%s)\n\n(b1=%s): ",a1,b1) fmt.Printf("\n\n====Decrypted: %s",message2) for i := 1; i <= 1000000; i++ { m,_ := new(big.Int).SetString(strconv.Itoa(i), 10) gm :=new(big.Int).Exp(priv.G, m, priv.P) if (gm.Cmp(message2)==0) { fmt.Printf("\n\nResult: %d",i) break } } }
A sample run is:
Prime number size: 512 ====Values (val1=12 and val2=2) ====Private key (x): X=42 ====Public key (Y,G,P): Y=13039885828249506231688772247299445547197938118451738724484040265283475187158436392032990161180212758509765634355858852500299761519902486581334607383485678 G=5421644057436475141609648488325705128047428394380474376834667300766108262613900542681289080713724597310673074119355136085795982097390670890367185141189796 P=13232376895198612407547930718267435757728527029623408872245156039757713029036368719146452186041204237350521785240337048752071462798273003935646236777459223 ====Cipher (a1=4547927178037700916215771041221488056446444096971083956191712574568742633629081729008485105605150669318428402984277061499641259052010174888282620372887340225546714535726523817529800768588721246438936796161547184464348194772577443396073707170127819752297202250717436533979521449338996191756105402989892144640) (b1=2910889186491095399228678360041277686201778254373963081499542599279100322584169161366876978573148865460432749713753378274780723605679306509961823893751647005106963971731825269315741073118362014421461573563104286081228791858429145555479247956780679935972540258190004779147681891431178522944767077100284081996): ====Decrypted: 2679540000547642396321815357991835281660554401869868515709677626004780484890804145075485817064287554512961432458622208304412076249094052595006844740055530 Result: 14