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:

\begin{align} K_{AB} &\equiv \alpha^{x_ax_B} \mod p\\ &\equiv y_A^{x_B} \mod p\\ &\equiv y_B^{x_A} \mod p \end{align}

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

\[\alpha^m \equiv y^r r^s \mod p\]

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.

  1. Choose a random number \(k\), uniformly between \(0\) and \(p - 1\), such that \(gcd(k, p - 1) = 1\).

  2. Compute

\[\begin{split}r \equiv \alpha^k \mod p\\ \alpha^m \equiv \alpha^{xr}\alpha^{ks} \mod p\end{split}\]

which can be solved for \(s\) by using

\[m \equiv xr + ks \mod (p-1)\]

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.

\[c=g^r, h^{mr}\]
[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}\)

\begin{align} m&=\frac{c_2}{c_1^x}=\frac{H^{rm}}{G^{xr}}=\frac{G^{xrm}}{G^{xr}} \end{align}
[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:

[ ]:



[ ]: