El Gamal Encryption

Question 1

Discrete Logarithm Assumption

Answer 1

Core Idea: It’s really hard to work out the power used to raise a number to get another number when calculations are done modulo a large prime.

Implication: This assumption makes it safe to use exponentiation in public key exchange methods, like Diffie-Hellman and El Gamal encryption, because reversing the operation is impractical.

Security: The strength of many encryption systems depends on the Discrete Logarithm problem being unsolvable in a reasonable amount of time by any current or foreseeable technology.

Question 1

Diffie Hellman Key Exchange Assumption

Answer 1

The Diffie-Hellman key exchange assumption is based on the difficulty of the Discrete Logarithm problem. It postulates that when two parties use a public base and a large prime modulus to exchange keys, it is computationally infeasible for an eavesdropper to calculate the shared secret key. This shared key is derived independently by both parties using their private keys and the other’s public key.

Question 2

El Gamal Key Generation

Answer 2

El Gamal Key Generation Flashcard:

• Goal: Create a secure key pair for El Gamal encryption.
• Steps:
  
  1. Form a cyclic group G of order q with a generator g
  2. Select a private key x randomly from the group.
  3. Compute the public key h as g^x mod p.
• Output:
  
  • Public key pk includes the group G, the generator g, and h.
  • Private key sk includes the group G, the order q, the generator g, and x

Question 3

El Gamal Algorithm

Answer 3

El Gamal Encryption Flashcard:

• Key Generation (KeyGen):
  
  • Use El Gamal to generate public key pk with group G, generator g and h and private key sk with x.
• Encryption (Enc):
  
  • With public key pk and a message m, pick a random y from group.
  • Create ciphertext (c 1 =g ^y , c 2 =h^y · m).
• Decryption (Dec):
  
  • With private key sk and ciphertext c_1, c_2, compute message m = c 2 · (c 1x ) ^-1.

Question 4

El Gamal attacks on weak randomness

Answer 4

El Gamal Weak Randomness Attack:

• Relies on the predictability of the random number generator used in encryption.
• If the ephemeral keys are predictable, an attacker might guess them.
• Using the same ephemeral key more than once can give away secure information.
• Weak randomness can potentially allow attackers to solve the Discrete Logarithm problem easier.
• Ensuring strong, unpredictable randomness is crucial for the security of El Gamal encryption. Use a CSPRNG to avoid such attacks.

Question 5

El Gamal vs RSA Encryption

Answer 5

Comparison of RSA and El Gamal Encryption:

• RSA:
  
  • Deterministic encryption.
  • Operates in the group (Zn)* with n being the product of two primes.
  • Encryption and decryption both involve one exponentiation.
  • Security is based on the difficulty of factoring large numbers, known as the RSA problem.
• El Gamal:
  
  • Randomized encryption, resulting in different ciphertexts for the same plaintext.
  • Operates in the group (Zp)*
  • Encryption involves two exponentiations, while decryption involves one.
  • Security relies on the difficulty of the Discrete Logarithm problem and the Diffie-Hellman problem.