Image for post
Image for post

John Napier’s Legacy Lives on in the 21st Century within ElGamal Encryption

I am lucky to work in the tower where John Napier discovered logarithms:

Now discrete logarithms are used as a base to perform key exchanges over the Internet. They are also being used within encryption — using the ElGamal method.

Public key encryption is typically used to sign for things (and where we use the private key to encrypt something and prove this with the public key) and within key exchange methods. The core methods used are RSA and Elliptic Curve. But an alternative is to use discrete logarithms. One of the most interesting is ElGamal, and was created by Taher Elgamal in 1985.

With ElGamal, 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:

Image for post
Image for post

His public key is then (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:

Image for post
Image for post

Bob then receives these and decrypts with:

Image for post
Image for post

This works because:

Image for post
Image for post

Some sample code is [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
}

func fromHex(hex string) *big.Int {
n, ok := new(big.Int).SetString(hex, 16)
if !ok {
panic("failed to parse hex number")
}
return n
}
type PublicKey struct {
G, P, Y *big.Int
}

type PrivateKey struct {
PublicKey
X *big.Int
}

func Encrypt(random io.Reader, pub *PublicKey, msg []byte) (a, b *big.Int, err error) {


k, _ := rand.Int(random, pub.P)


m :=new(big.Int).SetBytes(msg)

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 main() {

s:="hello world"
x:="40"
plen:="512"

s = string(os.Args[1])
x = string(os.Args[2])
plen =string(os.Args[3])

fmt.Printf("Input message: %s\n",s)
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)

message := []byte(s)
a, b, _ := Encrypt(rand.Reader, &priv.PublicKey, message)

message2, _ := Decrypt(priv, a, b)

fmt.Printf("====Private key (x):\nX=%d",priv.X)
fmt.Printf("\n\n====Public key (Y,G,P):\nY=%d\n\nG=%d\n\nP=%d",priv.Y,priv.PublicKey.G,priv.PublicKey.P)


fmt.Printf("\n\n====Cipher (a=%s)\n\n(b=%s): ",a,b)
fmt.Printf("\n\n====Decrypted: %s",string(message2))


}

In this case I have used Diffie Hellman group parameters for g, and p. A sample run is:

Input message: hello
Prime number size: 512

====Private key (x):
X=42

====Public key (Y,G,P):
Y=13039885828249506231688772247299445547197938118451738724484040265283475187158436392032990161180212758509765634355858852500299761519902486581334607383485678

G=5421644057436475141609648488325705128047428394380474376834667300766108262613900542681289080713724597310673074119355136085795982097390670890367185141189796

P=13232376895198612407547930718267435757728527029623408872245156039757713029036368719146452186041204237350521785240337048752071462798273003935646236777459223

====Cipher (a=10503137704154464640139409096180378450280945842974790197762651686774136663204267255536427109860643340473705516672240368851788858115494182159810217684111037)

(b=4054818746976519740094945741473934294426146873627558873251145631446282787632223746599936736928462111195626161828687198260149999269066225763403094068906537):

====Decrypted: hello

A demo is here:

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles…

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store