ElGamal¶
Diffie-Hellman key distribution scheme¶
IN 1975, Diffie and Hellman introduced the concept of public key cryptography.
Suppose that \(A\) and \(B\) want to share a secret \(K_{AB}\) , where A has a secret \(x_A\) and \(B\) has a secret \(x_B\) . Let \(p\) be a large prime and \(\alpha\) be a primitive element mod \(p\), both known. computes \(y \equiv \alpha^{x_a} \mod p\) , and sends \(y_A\) . Similarly, \(B\) computes \(y_B \equiv \alpha^{x_B} \mod p\) and sends \(y_B\) . Then the secret \(K_{AB}\) is computed as:
In any of the cryptographic systems based on discrete logarithms, p must be chosen such that \(p - 1\) has at least one large prime factor. If \(p - 1\) has only small prime factors, then computing discrete logarithms is easy
[1]:
from klefki.numbers.primes import generate_prime
from klefki.algebra.meta import field
from klefki.algebra.utils import randfield
from math import gcd
[2]:
p = generate_prime(32)
F = field(p)
mF = field(p-1)
G = F(generate_prime(32))
[3]:
xa, xb = randfield(F).value, randfield(F).value
ya, yb = G ** xa, G ** xb
G ** (xa * xb) == ya ** xb == yb ** xa
[3]:
True
ElGamal signature scheme¶
Let m be a document to be signed, where \(0 \le m \ge p - 1\). The public file still consists of the public key \(y \equiv x \mod p\) for each user.
To sign a document, a user \(A\) should be able to use the secret key \(x_A\) to find a signature for \(m\) in such a way that all users can verify the authenticity of the signature by using the public key \(y_A\) (together with \(\alpha\) and \(p\)), and no one can forge a signature without knowing the secret \(x_A\) .
The signature for \(m\) is the pair \((r, s), 0 \le r, s < p - 1\), chosen such that the equation
is satisfied.
[4]:
m = randfield(F).value
alpha = G
x = xa
y = ya
The Signing Procedure
The signing procedure consists of the following three steps.
Choose a random number \(k\), uniformly between \(0\) and \(p - 1\), such that \(gcd(k, p - 1) = 1\).
Compute
which can be solved for \(s\) by using
Above Equation as a solution for \(s\) if \(k\) is chosen such that \(gcd(k, p - 1) = 1\).
[5]:
k = generate_prime(32)
assert gcd(k, p-1) == 1
[6]:
from klefki.numbers import invmod
r = (alpha ** k).value
s = ((mF(m) - mF(r) * mF(x)) * ~mF(k)).value
[7]:
assert pow(alpha, m) == pow(alpha, (x * r + k * s))
The Verification Procedure
Given \(m, r\), an \(s\), it is easy to verify the authenticity of the signature by computing both sides of \(\alpha^m \equiv y^r r^s \mod p\) and checking that they are equal.
[8]:
alpha ** m == y ** r * F(r) ** s
[8]:
True
ElGamal encryption over Cyclic Group¶
[9]:
from klefki.curves.secp256k1 import EllipticCurveGroupSecp256k1 as Curve
from klefki.curves.secp256k1 import FiniteFieldSecp256k1 as F
from klefki.algebra.meta import field
Key generation¶
The first party, Alice, generates a key pair as follows:
Generate an efficient description of a cyclic group \(G\), of order \(q\) with generator \(g\). Let \(e\) represent the unit element of \(G\).
Choose an integer \(x\leftarrow Z_q\)
Compute \(h:=g^x\)
he public key consists of the values \(( G , q , g , h )\). Alice publishes this public key and retains \(x\) as her private key, which must be kept secret.
[10]:
G = Curve.G
sk = randfield(F)
H = G @ sk
Encryption¶
A second party, Bob, encrypts a message \(M\) to Alice under her public key \(( G , q , g , h )\) as follows:
Map the message \(M\) to an element \(m\) of \(G\) using a reversible mapping function.
Choose an integer \(y\) randomly from \(\{ 1 , … , q − 1 \}\)
Compute \(s := h^y\). This is called the shared secret.
Compute \(c_1 := g^y\)
Compute \(c_2 := m \cdot s\)
Bob sends the ciphertext \(( c_1 , c_2 )\) to Alice.
[11]:
M = F(1235)
[12]:
y = randfield(F).value
m = Curve.lift_x(M)
c1 = G @ y
c2 = H @ y + m
(c1, c2)
[12]:
(EllipticCurveGroupSecp256k1::(FiniteFieldSecp256k1::0xad78a3d6fd61dbf18585d0bdfc5263ead132b1dcb2fcf5d008e1f30662299c9e, FiniteFieldSecp256k1::0xc691845486a1ceebf28e1092de6b875f155b594e99036dc216207e36884167db),
EllipticCurveGroupSecp256k1::(FiniteFieldSecp256k1::0xa81a8ede02088dd0fabc535a5a58621ed70cdfdc34c5d71cec152845bffcb3d5, FiniteFieldSecp256k1::0x189dbf0231b9df69af56e5dd08fa5f7026078d9faf2480c32e5c5406de58cade))
Decryption¶
Alice decrypts a ciphertext \(c_1, c_2\) with her private key \(sk\) as follows:
Compute \(s := c_1^{x}\).
Compute \(s^{-1}\), the inverse of \(s\) in the group \(G\).
Compute \(m:=c_2\cdot s^{-1}\)
[13]:
m = (c2 - (c1 @ sk))
[14]:
m.x == M
[14]:
True
Test¶
[15]:
from klefki.curves.secp256k1 import EllipticCurveGroupSecp256k1 as Curve
from klefki.curves.secp256k1 import FiniteFieldCyclicSecp256k1 as CF
from klefki.curves.secp256k1 import FiniteFieldSecp256k1 as F
from klefki.algebra.meta import field
from klefki.blockchain.ethereum.private import decode_privkey, encode_privkey
from klefki.crypto.ecdsa.secp256k1 import pubkey
from klefki.utils import int_to_byte, byte_to_int
key = decode_privkey("65860affb4b570dba06db294aa7c676f68e04a5bf2721243ad3cbc05a79c68c0")
[16]:
pubkey = G @ F(key)
[17]:
m_x = [253, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 116, 101, 115, 116]
m_y = [102, 240, 6, 242, 139, 13, 202, 191, 92, 132, 250, 2, 205, 187, 196, 131, 154, 248, 95, 123, 242, 215, 83, 237, 38, 195, 221, 29, 137, 141, 2, 132]
[18]:
m_x = F(byte_to_int(m_x))
m_y = F(byte_to_int(m_y))
[19]:
m = Curve(m_x, m_y)
m
[19]:
EllipticCurveGroupSecp256k1::(FiniteFieldSecp256k1::0xfd00000000000000000000000000000000000000000000000000000074657374, FiniteFieldSecp256k1::0x66f006f28b0dcabf5c84fa02cdbbc4839af85f7bf2d753ed26c3dd1d898d0284)
[20]:
r = F(0x1f9275dbafdfba81942eb3330b07f38cbee4ebb86bdc2174af9648d5f5509a54)
[21]:
c1 = G @ r
[22]:
c1
[22]:
EllipticCurveGroupSecp256k1::(FiniteFieldSecp256k1::0xfca855e9dc774cd9346ca71beabcc55f48d594d46fff063b09866f79af09bd69, FiniteFieldSecp256k1::0x142d0d3df53288b7b6d2a97854cc4d8a0c74320973628af5183ddf9037b4e73b)
[23]:
ss = pubkey @ r
[24]:
ss.x.value
[24]:
98638154376543494645275106847376508464438552902924450790959126183159388906274
[25]:
c2 = ss + m
[26]:
t = c1 @ key
[27]:
d = (c2 - (c1 @ key))
[28]:
d.x == m.x
[28]:
True
Ref:¶
ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Trans. Info. Theory, IT 31:469–472, 1985.
ElGamal encryption https://en.wikipedia.org/wiki/ElGamal_encryption
[ ]:
[ ]: