ElGamal - Applying Multiple Public Key Operations (ECC)[ElGamal Home][Home]
With the ElGamal method, we can modify the core method so that we can apply the public key multiple times, but only require a single decryption. This will use elliptic curve methods, and using the Edwards 25519 curve.
|
Outline
First we will outline using discrete logs, and then with ECC. We hardly ever use discrete logs these days, as Elliptic Curve Cryptography is just so much more efficient and faster. And, so I love converting discrete log proofs with Elliptic Curve methods. Basically, we convert a power into a multiplicative operation for the base point:
\(g^x \pmod p\) -> \( x.G\)
and where G is the base point of the curve. Then a multiplication is replaced with a point addition, and a division is replaced with a point subtraction:
\(a.g^x \pmod p\) -> \( a+x.G\)
\(\frac{a}{g^x} \pmod p\) -> \( a-x.G\)
Discrete logs
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 \((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\)
his 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 \)
To encrypt a first time gives:
\(a_1=g^{r_1} \pmod p\)
\(b_1=y^{r_1} M \pmod p\)
Now, a second node can also encrypt with:>
\(a_2=g^{r_2}.a_1 \pmod p\)
\(b_2=y^{r_2}.b_1 \pmod p\)
Then we get:
\(a_2=g^{r_1} \times g^{r_2} = g^{r_1+r_2} \pmod p\)
and then:
\(b_2=Y^{r_1} M \times Y^{r_2} = Y^{r_1+r_2} M \pmod p\)
\(M=\frac{b_2}{{a_2}^x} = \frac{Y^{r_1+r_2} M}{({g^{(r_1+r_2)})}^x} = \frac{Y^{r_1+r_2} M}{g^{(r_1+r_2)x}} = \frac{Y^{r_1+r_2} M} {({g^{x})}^{(r_1+r_2)} } = \frac{Y^{(r_1+r_2)} M} { Y^{(r_1+r_2)} } = M \pmod p \)
and so we can keep encrypting, but were a single end decryption process can then decrypt the answer.
ECC
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=x.G\)
His public key is \((Y)\) 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=k.G\)
\(b=M+k.M\)
Bob then receives these and decrypts with:
\(M=b-x.a\)
To encrypt a first time gives:
\(a_1={r_1}.G\)
\(b_1= M+ {r_1}.Y\)
Now, a second node can also encrypt with:>
\(a_2=a_1.{r_2}.G \)
\(b_2=b_1.{r_2}.Y\)
Then we get:
\(a_2={r_1}.G + {r_2}.G = {(r_1+r_2)}.G \)
and then:
\(b_2=M+ {r_1+r_2}.Y \)
We then decrypt with:
\(D=b_2-x.a_2 \)
and so we can keep encrypting, but were a single end decryption process can then decrypt the answer.
The method is defined here:
Coding
The coding is here:
package main import ( "fmt" "os" "go.dedis.ch/kyber/v3/group/edwards25519" "go.dedis.ch/kyber/v3/util/random" ) func main() { message:="Testing" argCount := len(os.Args[1:]) if (argCount>0) {message= string(os.Args[1])} suite := edwards25519.NewBlakeSHA256Ed25519() // Alice's key pair (x,Y) x := suite.Scalar().Pick(suite.RandomStream()) Y := suite.Point().Mul(x, nil) M := suite.Point().Embed([]byte(message), random.New()) G:=suite.Point().Base() r1 := suite.Scalar().Pick(random.New()) a1:= suite.Point().Mul(r1, G) S := suite.Point().Mul(r1, Y) b1 := S.Add(S, M) r2 := suite.Scalar().Pick(random.New()) a2:= suite.Point().Add(a1,suite.Point().Mul(r2, G)) S = suite.Point().Mul(r2, Y) b2 := S.Add(S, b1) fmt.Printf("Message:\t\t%s\n" , message) fmt.Printf("Message point:\t\t%s\n" , M.String()) fmt.Printf("\nPrivate key (x):\t%s\n" , x) fmt.Printf("Public key: (x.G):\t%s\n" , Y) fmt.Printf("\nr1:\t%s\n" , r1) fmt.Printf("a1:\t%s\n" , a1) fmt.Printf("b1:\t%s\n" , b1) fmt.Printf("\nr2:\t%s\n" , r2) fmt.Printf("a2:\t%s\n" , a2) fmt.Printf("b2:\t%s\n" , b2) D:=suite.Point().Sub(b2,suite.Point().Mul(x,a2)) rtn, _:= D.Data() fmt.Printf("\nMessage:\t%s\n" , string(rtn)) }
A sample run is:
Message: Hello Message point: 0548656c6c6f790a2da47228415873d9b6c687b06ca5c53dcbb0da308dcb41a0 Private key (x): e40392e44de430cdb7401e3969eae54e73d52eb9e4fbe62cab8f5e5c76e57207 Public key: (x.G): b01910f26848273cd327e1969c5aca1472dfd1f3db5acf7e4f0a5f95a929bad7 r1: 115f8439c19b088967418e2a75d4ea054064e143bb6f01884278095207e45609 a1: 29cb96fe0d47932589daccfcacddcaab4ee7935ccf36bd6be6c84062b9008fc8 b1: 66afd3e69e8c98dd84a1b78a12e98c0bbe7f2362ef636bbd54f02da64d9b5c39 r2: 4edb25b493de66911a7f216323d88e546fe469732ad0e3fae7d81db2a1879e05 a2: f5c2124722b6d54b5b31cb20502b852b33f37fd5cdb42c85a245e8167e44184f b2: b775f0a95167abfbc37fb5353677ec2d9b9219a9302ac2485620c1c65e2dab81 Message: Hello