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 multiply the ciphered values. With this we encrypt two integers, and then multiply the ciphered values, and then decrypt the result.
Partial Homomorphic Encryption with ElGamal (Multiply) |
Theory
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 \((Y, g, p)\) and he will send this to Alice. Alice then creates a message (\(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 \)
If we have:
\(a_1=g^{k_1} \pmod p\)
\(a_2=g^{k_2} \pmod p\)
\(b_1=y^k M_1 \pmod p\)
\(b_2=y^k M_2 \pmod p\)
The we get:
\(a=a_1 \times a_2 = g^{k_1} \times g^{k_2} = g^{k_1+k_2}\)
\(b=b_1 \times b_2 = y^k M_1 \times y^k M_2\)
\(M=\frac{b}{a^x} = \frac{y^k M_1 \times y^k M_2}{{g^{k_1+k_2}}^x} \)
Code
The coding is [from here]:
package main import ( "crypto/rand" "math/big" "io" "fmt" "os" ) 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) b = s.Mul(s, m) b.Mod(b, pub.P) return } func Decrypt(priv *PrivateKey, a, b *big.Int) (msg []byte, 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) em := s.Bytes() return em, 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:="3" 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: %d",valint(message2)) }
A sample run is:
Prime number size: 512 ====Values (val1=1001 and val2=1001) ====Private key (x): X=42 ====Public key (Y,G,P): Y=13039885828249506231688772247299445547197938118451738724484040265283475187158436392032990161180212758509765634355858852500299761519902486581334607383485678 G=5421644057436475141609648488325705128047428394380474376834667300766108262613900542681289080713724597310673074119355136085795982097390670890367185141189796 P=13232376895198612407547930718267435757728527029623408872245156039757713029036368719146452186041204237350521785240337048752071462798273003935646236777459223 ====Cipher (a1=3822615489308390631347569821164754026061568666038053932657215750958996428208258993245969016873257376007105605349433681912361987625535274424997641468969186390106857499217247887245457782492636647818841587319010985367772517302913842509445614180456413521995713716184259761659246689297220508669448788588192620606) (b1=35875399889732384509574690091821755841824677238754180361205267723720956386431855445742455890929781307208697670944066655157314661137095789184827469108360096005860495221739730695336429190400065658526945759667474755150670557637484355067541967642969500763074772704198419155874940382719990516839214826862782579417): ====Decrypted: 1002001