Skip to content

IlyasRidhuan/ElGamal

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

57 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

ElGamal

What's included
  • ElGamal (Multiplicative)
  • Modified ElGamal (Additive)
  • Threshold Encryption (m-of-n)
  • Elliptic Curve El Gamal
  • Zero Knowledge Proof of Correct Encryption (Honest Verfier)

Introduction

The ElGamal Cryptosystem is an asymmetric public key encryption scheme based on the Diffie-Hellman key exchange. Its security is based on the intractability of computing discrete logarithms for a large prime modulus. While ElGamal is naturally multiplicatively homomorphic, a modification to the message structure can be made to result in an additively homomorphic scheme (modified ElGamal).

Implementation

Key Generation

  • Generate a safe prime p, alternatively generate a Sophie Germain q such that p = 2q + 1 and both p & q primes.
  • Find a generator, g such that it will generate the cyclic group G with order q and not any other subgroup of $Z_q^*$ where $Z_q^*$ is the list of invertible elements less than q, i.e (1,..,q-1). Helpful link
  • Calculate $y \;=\; g^x \;mod ;p$
  • The public key is < p,q,g,y >
  • The private key is $x \in Z_q$

Encryption

  • Randomly select an $r \in_R Z_q$
  • Encrypt a plaintext $ s \in Z_p^*$ to a corresponding ciphertext $ c \;=\; (\alpha,\beta)$ where $\alpha \;=\; g^r mod\;p$ and $\beta \;=\; sy^r\;mod\;p$
Modified ElGamal
  • In the modified ElGamal $\beta \;=\; g^sy^r mod\;p$

Decryption

  • Decrypt some ciphertext $ c\;=\; (\alpha,\beta)$ using the private key x and computing $ s \;=\; \beta \alpha^{-x} \; mod \; p$ where $\alpha^{-1}$ indicates the modular multiplicative inverse
Modified ElGamal
  • In the modified ElGamal, decryption involves solving for the discrete log $y\;=\; g^m$. While normally intractable the discrete log is feasible for small values of m $(\approx \;< \; 2^30)$. Current implementation is a brute force search although will probably move to Pollard's kangaroo algorithm when I find the time.

Threshold Encryption

Shamir Secret Sharing (SSS)
  • The basic idea of SSS is a polynomial of degree n can be uniquely identified by (n-1) distinct points. By using Lagrange polynomials we can guarantee that the for a set of points the lowest degree polynomial is in fact unique.
Threshold Decryption
  • To use threshold encryption, each owner of a key split calculates the partial decryption $z_j \; = \; \alpha^{x_j}$ where $x_j$ is the private key of their split
  • The plaintext message can then be recovered from the partial decryption using $ s \; = \; \frac{\beta}{\prod_{j \in S}z_j^{\mu_j}}$ where S is the set of sufficient partial decryptions and $\mu_j\;=\;\prod_{j' \in S \backslash j} \frac {j'} {j'-j}$

Incorporating Zero Knowledge Proofs

Non Interactive Proof of Knowledge of Discrete logarithms
  • Each owner of a key,${x_j}$, also calculates a verification key $v_j \; = \; g ^{x_j} \;mod\;p$
  • Based on the $\Sigma$ Protocol but extended for two logarithms, each partial decryption is accompanied by a proof of correct decryption using a zero-knowledge proof of equality of discrete logarithms ($\log_g(v_j) = \log_\alpha (z_j)$)
  • The normally interactive proof is made non-interactive using the Fiat-Shamir heurtistic where the collision-resistant hashing function used in this case is SHA256

About

WIP ElGamal Cryptosystem

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published