ElGamal

The ElGamal system utilizes the Discrete Logarithm Problem as its primal measure obtain security. Diffie-Hellman is used as fundamental, and is converted into public key encryption to embody ElGamal system.

Basic Setting

${\mathcal{E}}^{\prime }=({\text{Gen}}^{\prime },{\text{Enc}}^{\prime },{\text{Dec}}^{\prime })$ is a private-key encryption with $K=G$

• Bob computes $k=u^y$ and encrypts $m$ using the private-key encryption ${\mathcal{E}}^{\prime }$. Resulting ciphertext is $c=(v,c^{\prime })$
• Alice computes $k=v^x$ and derives $m$ by decrypting $c^{\prime }$

Key Generation in ElGamal Encryption:

Computed by Alice (reciever)

• A large prime number $x$ is selected from group $Z_q$ as a private(secret) key, and public key $u=g^x$ is made public
• can be represented as equation below $\text{Gen}:sk=x\leftarrow {\mathbb{Z}}_q$ and $pk=u\leftarrow g^x$

Encryption Process of Message m:

Computed by Bob (encryptor)

• random number $y\leftarrow {\mathbb{Z}}_q$ is chosen
• $v=g^y$, $k=u^y$ is computed, using public key generated by Alice(reciever)
• encryption is done by computing $c^{\prime }\leftarrow {\text{Enc}}_k^{\prime }(m)$, which is a private key encrytion of message m, via key $k$
• output $c=(v,c^{\prime })$ as a final ciphertext

Decryption Process:

• utilizes private key $x$ to compute $k=v^x$ (shared key generated by Bob)
• using shared key $k$ obtained above, ciphertext $c$ can be transfromed into the original plaintext $m$ through $m\leftarrow {\text{Dec}}_k^{\prime }(c^{\prime })$

In RSA, encrypting the same message always produces the same ciphertext, whereas the ElGamal system uses random numbers, resulting in different ciphertexts for the same message each time it is encrypted. Therefore, RSA-OAEP is used in commercial systems. Additionally, the ElGamal system offers security with smaller private key sizes compared to RSA.

Security of ElGamal

let ${\mathcal{E}}^{\prime }=({\text{Gen}}^{\prime },{\text{Enc}}^{\prime },{\text{Dec}}^{\prime })$ be a private key encryption with $K=G$. If ${\mathcal{E}}^{\prime }$ is CPA-secure and the DDH assumption holds, the ElGamal is CPA-secure.

Key Generation in ElGamal Encryption:

•	A large prime number  p  is selected, and a primitive root  g  on  Z_p  and  p  are made public.
•	An arbitrary element  d  on  Z_p  is chosen, and \( e \equiv g^d \mod p \) is calculated. ( e  is the public key, and  d  is the private key)

Encryption Process of Message M :

•	 r \in_R Z_p  (Generate a random number  r  on  Z_p )
•	Calculate \( K \equiv e^r \mod p \) using the recipient’s public key  e .
•	Compute \( C_1 \equiv g^r \mod p \) and \( C_2 \equiv KM \mod p \).
•	The ciphertext is  C = (C_1, C_2) .

Decryption Process:

•	Use the private key  d  to calculate \( K \equiv {C_1}^d \mod p \).
•	Using the  K  obtained above, decrypt by calculating \( M \equiv C_2/K \mod p \).

In RSA, encrypting the same message always produces the same ciphertext, whereas the ElGamal system uses random numbers, resulting in different ciphertexts for the same message each time it is encrypted. Therefore, RSA-OAEP is used in commercial systems. Additionally, the ElGamal system offers security with smaller private key sizes compared to RSA.