ElGamal — Applying Multiple Public Key Operations (ECC)

ElGamal — Applying Multiple Public Key Operations (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:

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:

Now, here’s an example. On the left hand side we have the discrete log proof, and the right hand side has the equivalent elliptic curve proof:

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 [here]:

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