Elgamal

Elgamal dibuat oleh Taher Elgamal pada tahun 1985. Keamanan Elgamal terletak pada persoalan logaritma diskrit, yaitu $p \in \mathbb{P}, {g, y} \in \mathbb{Z}, \exists x | g^{x} \equiv y (\bmod p)$. Menemukan nilai $x$ akan sangat susah.

Variabel

1. $p \in \mathbb{P}$ (tidak rahasia),
2. $g \in \mathbb{Z}$, $g$ adalah akar primitif dari $p$ (tidak rahasia),
3. $x$, bilangan acak (rahasia),
4. $y = g^x \bmod p$ (tidak rahasia, kunci publik),
5. $m$, plaintext (rahasia),
6. $a, b$, ciphertext (tidak rahasia).

Fungsi Enkripsi dan Dekripsi

Fungsi enkripsi dinyatakan dengan:

$$a = g^x \bmod p$

$$b = y^k m \bmod p$

Pasangan $a, b$ adalah ciphertext yang berukuran $2 \times m$.

Fungsi dekripsi dinyatakan dengan:

$$\begin{aligned} m & = (b/a^{x}) \bmod p \\ & = b(a^{x} )^{-1} \bmod p \end{aligned}$

Dengan:

$$(a^{x} )^{-1} = a^{p-1-x} \bmod p$ (invers modulo).

Skenario

Bagian ini menjelaskan skenario bagaimana kriptografi kunci publik bekerja. Kita akan menggunakan partisipan klasik Alice dan Bob sebagai dua pihak yang melakukan pertukaran informasi.

1. Alice dan Bob setuju untuk menggunakan public-key cryptosystem.
2. Bob mengirimkan public key-nya kepada Alice.
3. Alice meng-encrypt pesan yang dibuatkan dengan menggunakan public key milik Bob dan mengirimkan pesan yang sudah di-encrypt kepada Bob.
4. Bob men-decrypt pesan dari Alice menggunakan private key miliknya.

Pembangkitan Kunci

Alice dan Bob menyepakati $p \in \mathbb{P}, a \in \mathbb{Z}$, kemudian:

1. Alice memilih $x, x < x < p-1$ (acak),
2. Alice menghitung $y = g^x \bmod p$.

Mengasilkan kunci publik: $(y, g, p)$ dan kunci private $(x)$.

Misalnya:

$$p = 2273, g = 3, x = 243$

Alice kemudian menghitung:

$$y = g^x \bmod p = 3^{243} \bmod 2273 = 461$

Menghasilkan kunci publik $(461, 3, 2273)$ dan kunci privat $(243)$.

Contoh Kasus

Pesan $m, 0 > m < p-1$, dapat dibagi kedalam blok $m_1, m_2, \cdots$, sehingga $m < p-1$.

Misalnya $m = 07001114$, dibagi menjadi $m_1 = 0700, m_2 = 1114, \forall m_i < 2273 - 1$.

Enkripsi Pesan

Untuk enkripsi blok $m_1$, dipilih $k = 1463 \in [0, 2273-1]$.

\begin{aligned} m_1 & = 0700 \\ a & = g^k \bmod p \\ & = 3^{1463} \bmod 2273 \\ & = 1439 \\ b & = y^k m_1 \bmod p \\ & = 461^{1463} \cdot 700 \bmod 2273 \\ & = 74 \end{aligned}

Cihpertext untuk $c_1 = (1439, 74)$.

Untuk enkripsi blok $m_2$, dipilih $k = 2001 \in [0, 2273-1]$.

\begin{aligned} m_1 & = 1114 \\ a & = g^k \bmod p \\ & = 3^{20001} \bmod 2273 \\ & = 1220 \\ b & = y^k m_1 \bmod p \\ & = 461^{20001} \cdot 1114 \bmod 2273 \\ & = 1682 \end{aligned}

Cihpertext untuk $c_1 = (1220, 1682)$.

Dekripsi Pesan

Untuk mendekripsi blok $c_1$,

\begin{aligned} c_1 & = (1439, 74) \\ (a^{x} )^{-1} & = a^{p-1-x} \bmod p \\ & = 1439^{2029} \bmod 2273 \\ & = 1791 \\ m_1 & = b/a^{x} \bmod p \\ & = b(a^{x} )^{-1} \bmod p \\ & = 74 \cdot 1791 \bmod 2273 \\ & = 700 \\ & = 0700 \end{aligned}

Untuk mendekripsi blok $c_2$,

\begin{aligned} c_2 & = (1220, 1682) \\ (a^{x} )^{-1} & = a^{p-1-x} \bmod p \\ & = 1220^{2029} \bmod 2273 \\ & = 1125 \\ m_2 & = b/a^{x} \bmod p \\ & = b(a^{x} )^{-1} \bmod p \\ & = 1682 \cdot 1125 \bmod 2273 \\ & = 1114 \end{aligned}

Pesan berhasil di dekripsi kembali, yaitu $07001114$.

Penutup

Elgamal pada awalnya diciptakan untuk digital signature yang kemudian dimodifikasi untuk digunakan untuk enkripsi dan dekripsi. Kekuatan Elgamal terletak pada sukarnya menghitung logaritma diskrit.

Elgamal seperti algoritma asimetrik lainnya, digunakan untuk enkripsi dan dekripsi kunci algoritma simetrik.

Reference

1. Elgamal. T. “A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms”. IEEE Transactions on Information Theory. 1985

2. Munir. R. “Kriptografi Edisi Kedua”. Informatika: Bandung. 2019.

3. Schneier, B. Applied Cryptography, 2nd Ed. John Wiley & Sons, Inc: Canada, 1996.

Lampiran

Penggunaan:

python Elgamal.py

Code:

def is_relative_prime(prime, data):
    while data != 0:
        prime, data = data, prime % data
    return prime

def is_primitive_root(prime, root):
    primitive_root = []
    for i in range(prime - 1):
        primitive_root.append(pow(root, i + 1) % prime)

    # Untuk memastikan tidak terjadi pembandingan primitive_root pada indeks j
    # dan i yang sama
    kampret = 1
    
    # Membandingkan apakah tidak ada data yang sama
    for i in range(len(primitive_root)):
        for j in range(kampret, len(primitive_root) - 1):
            if primitive_root[i] == primitive_root[j + 1]:
                print("Not primitive root")
                return 0

        if is_relative_prime(prime, primitive_root[i]) != 1:
            print("Not relative prime")
            return 0
        kampret += 1
    return 1


def key_builder():
    print("Input prime number, root and secret key (x)")
    prime, root, secret_key = [int(x) for x in input().split(" ")]

    # root number must be primitive root from prime
    if is_primitive_root(prime, root) == 1:
        y = pow(root, secret_key) % prime
        print(f"Public Key (%d, %d, %d)" % (y, root, prime))
        print(f"Private key %d" % secret_key)


def encryption():
    # message is one character, string will be add later
    print("Input message")
    message = input()

    print("Input y, g and p (public key)")
    y, g, p = [int(x) for x in input().split(" ")]

    # k is random number from 1 <= k <= p-1
    print("Input k")
    k = int(input())

    # the ciphertext will be a pair of a and b
    a = pow(g, k) % p
    b = (pow(y, k) * ord(message)) % p

    print(f"Ciphertext (%d, %d)" % (a, b))


def decryption():
    a, b, x, p = [int(x) for x in input().split(" ")]
    m = pow(a, (p-1-x)) * b % p
    print(f"Message %c" % m)

key_builder()
encryption()
decryption()