In 1985, Taher ElGamal wrote A Public key Cryptosystem and A Signature Scheme based on discrete Logarithms (PDF). This lays out the math for:
- Encrypting a message so that only a particular person can read it
- If you are that particular person, decrypting the message so you can read it
- Signing a message so that anyone can convince themselves you wrote it
- Verifying that a message was really written by the person who signed it
I read through the paper and wrote a toy implementation in PowerShell.
In the toy implementation, A wants to send private message “92” to B. She encrypts it to the encrypted message “(33, 76)” using B’s public key 69. B uses his private key 55 to decrypt the message back to 92, so he can read it, but no-one else can.
Then A wants to sign a different message “28”. She uses her private key 57 to generate the signature “(29, 25)”. B uses A’s public key 74 to confirm that both the message 28 and the signature (29, 25) give the same value 80, so only A could have generated the signature.
Here is the output of the toy implementation. If you run it multiple times, the encryption (33, 76) and the signature (29, 25) will vary, but the messages are always the same, and the signature check value 80 is always the same.
-- AGREE ON COMMON PARAMETERS -- Everyone agrees to use prime field GF(p = 101) and generator g = 2 -- GENERATE KEYS -- A's private key is 57 and public key is 74 B's private key is 55 and public key is 69 -- ENCRYPT -- A wants to send B a message so that only B can read it The first block of the message is m = 92 A chooses a random number k = 82 A calculates the key K = (y_B = 69)^(k = 82) mod (p = 101) = 14 A calculates and sends the encrypted message (c1, c2) = (33, 76) * c1 = (g = 2)^(k = 82) mod (p = 101) = 33 * c2 = (K = 14)(m = 92) mod (p = 101) = 76 -- DECRYPT -- B wants to read the message that A sent B B recovers K = (c1 = 33)^(x_B = 55) mod (p = 101) = 14 B calculates m = (c2 = 76)/(K = 14) mod (p = 101) = 92 -- SIGN -- A wants to sign a message so that anyone can prove that A wrote it The first block of the message is m = 28 A chooses a random number k = 91 such that gcd(k = 91, p - 1 = 100) = 1 A calculates and sends the signature (r, s) = (29, 25) These are calculated so g^m = y_A^r r^s mod p Take r = g^k Now we have g^m = g^(x_A r) g^(k s) mod p Which is to say m = x_A r + k s mod (p - 1) We want to solve for s - this is why we needed gcd(k, p - 1) is 1 * r = (g = 2)^(k = 91) mod (p = 101) = 29 * s which makes (m = 28) = (x = 57) * (r = 29) + (k = 91) * (s = 25) mod (p - 1 = 100) -- VERIFY SIGNATURE -- B - or anyone - wants to verify A's signature If the signature is valid, (g = 2)^(m = 28) = (y_A = 74)^(r = 29) (r = 29)^(s = 25) mod (p = 101) This checks because both sides are equal to 80