Cryptography Fundamentals 10: ElGamal Encryption and Signatures ASecuritySite Podcast

Blog: https://billatnapier.medium.com/cryptography-fundamentals-elgamal-encryption-and-signature-2de5f16b1127 
ElGamal methods: https://asecuritysite.com/elgamal 
Introduction
In research, we build on the shoulders of giants, and Taher Elgamal is one of the giants of cybersecurity. His work on Netscape led to the creation of SSL, and for which much of our Web security is still built on. Along with this, he published this paper in 1985 [here]:
It was true classic, and has been reference over 12,500 times. Within the paper, Tahir outlined an encryption methods and a digital signature method. His ‘base’ was to take John Napier’s logarithm, and make them discrete. This discrete element meant that we only dealt with positive integer values, and where we worked within a finite field. This field was defined by a prime number (p).
While the core ElGamal encryption method was overtaken in its usage by RSA, and then by ECC (Elliptic Curve Cryptography), the signature method was adopted as the Digital Signature Standard (DSS) by NIST. This has since scaled into ECC to become ECDSA, and which is used by Bitcoin and Ethereum.
Tahir studied electrical engineering in the late 1970s at Stanford University. It was there he met Marty Hellman and who helped him spark an interesting in cryptography. He received his PhD in 1984 and it was Marty introduced him to Paul Kocker at Netscape Communications. Together, Paul and Tahir worked on a method to implement end-to-end encryption, and published SSL 3.0 in November 1996:
Examples are at:
https://asecuritysite.com/elgamal
The ElGamal Method Befre we start we need to look at some of the basics of logarithms and where:
{g^a}^b is g^{ab}
and:
g^a . g^b = g^{a+b}
To make these discrete to add (mod p) in our operations and where p is a prime number. This constrains our integrates with a finite field, between 0 and p-1.
In the ElGamal method, 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 (mod 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 (mod p)
b=y^k.M (mod p)
Bob then receives these (a and b), and then uses his private key (x) to decrypt the values and discover the message:
M=b/(a^x) (mod p)
With the divide by (a^x) we basically take the inverse of (a^x) mod p, and then multiply. The operation works because:
ElGamal and Signatures With ElGamal signing, Alice has a public key (y,g,p) and a private key of a. She then takes a message m and creates a signature (r,s). This signature can then be checked by Bob. 
With ElGamal, Alice selects a generator (g), prime number of p and a private key of a. Her public key is then (y,g,p) and where y is:
y=g^a (modp)
To sign a message (m) we generate a secret random number (k) and we must make sure:
gcd(k,p−1)=1
Next we compute:
r=g^k (mod p)
Next we compute:
k^{−1} (mod p−1)
and then:
s=k^{−1}(h(m)−ar) (modp−1)
The signature is then (r,s). Bob verifies the signature by computing two values:
v1=y^r.r^s (mod p)
and:
v2=g^{h(m)} (mod p)
If v1 is equal to v2
the signature has been verified. The proof is given here:
https://asecuritysite.com/elgamal/el_sig2
While, ElGamal signing is not used these days, its method were applied into the Digital Signature Algorithm (DSA), and which was since been coverted into the Elliptic Curve Digital Signature Algorithm (ECDSA) method.
Converting from discrete logs to elliptic curves In discrete logs we convert from:
Y=g^a (mod p)
to
Y=a.G
and where we have a exponential for discrete logs we have:
Y = {g^a}^ b
is equivalent to:
Y=a.b.G
and for a multiplication we have
Y=g^a.g^b (mod p) = g^{a+b} (mod p)
In elliptic curves we convert the multiplication to a point addition:
Y = a.G + b.G = (a+b) G
Converting from John Napier’s Logarithm