Cryptography

By:

Dr. Mohammad Shoab

Week 11 & 12

ElGamal Encryption

• In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange.
• It was described by Taher Elgamal in 1985.
• ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of PGP, and other cryptosystems.
• The Digital Signature Algorithm (DSA) is a variant of the ElGamal signature scheme, which should not be confused with ElGamal encryption.

2

Cryptography

Department of Computer Science

ElGamal Encryption

Parameters:

• p, a large prime
• g, a generator of Z_p^*
• α ∈ Z_p-1, β = g^α mod p
• p, g, β public; α private

Encryption:

• generate random, secret k ∈ Z_p-1.
• E(x, k) = (r, s), where� r = g^k mod p� s = xβ^k mod p
• D(r, s) = s(r^α)^-1 mod p = xg^αkg^-αk mod p = x.

3

Cryptography

Department of Computer Science

ElGamal Encryption

• Plaintext x is masked by a random factor, g^αk mod p.
• DH problem: Given g^α, g^k mod p, what is g^αk mod p?
• p, g can be common. Then g^k mod p can be computed in advance.
• Same k should not be used repeatedly.
• Performance:
• encryption: two exponentiations
• decryption: one exponentiation, one inversion
• Size: Ciphertext twice as large as plaintext.

4

Cryptography

Department of Computer Science

ElGamal – Signature

CS555

5

Parameters: The same as encryption.

Signature:

• generate random, secret k ∈ Z_p-1^*.
• S(m, k) = (r, s), where� r = g^k mod p� s = (m – rα)k^-1 mod (p – 1) �(i.e., m = rα + sk )

Verification:

• Is β^rr^s ≡ g^m (mod p) ?
• β^rr^s = g^αrg^{k(m – rα)k^(-1)} = g^{αr + (m – rα)} = g^m mod p.

Cryptography

Department of Computer Science

ElGamal – Signature

CS555

6

Security:

• Only one who knows α can sign; can be verified by β.
• Solving α from β, or s from r, m, β, is discrete log.
• Other ways of forgery? Unknown.
• Same k should not be used repeatedly.

Variations:

• Many variants, by changing the “signing equation”,� m = rα + sk.
• E.g., the DSA way:� m = –rα + sk�with verification: β^rg^m ≡ r^s (mod p)? (≡ g^{m + rα})

​

Cryptography

Department of Computer Science

CCA Security

CS555

7

• A chosen-ciphertext attack (CCA) is an attack model for cryptanalysis where the cryptanalyst can gather information by obtaining the decryptions of chosen ciphertexts.

​

• From these pieces of information the adversary can attempt to recover the hidden secret key used for decryption.

​

• El Gamal cryptosystem is semantically secure under chosen-plaintext attack, but this semantic security can be trivially defeated under a chosen-ciphertext attack. 

Cryptography

Department of Computer Science

CCA Security

8

• When a cryptosystem is vulnerable to chosen-ciphertext attack, implementers must be careful to avoid situations in which an adversary might be able to decrypt chosen-ciphertexts (i.e., avoid providing a decryption oracle). 
• This can be more difficult than it appears, as even partially chosen ciphertexts can permit subtle attacks.
• Additionally, other issues exist and some cryptosystems (such as RSA) use the same mechanism to sign messages and to decrypt them.
• This permits attacks when hashing is not used on the message to be signed.

Cryptography

Department of Computer Science

RSA Signature

• The RSA public-key cryptosystem provides a digital signature scheme (sign + verify), based on the math of the modular exponentiations and discrete logarithms and the computational difficulty of the RSA problem (and its related integer factorization problem).

​

• There are three steps as follows:
• Key Generation
• RSA Sign
• RSA Verify Signature

CS555

9

Cryptography

Department of Computer Science

Key Generation

• The RSA algorithm uses keys of size 1024, 2048, 4096, ..., 16384 bits.
• RSA supports also longer keys (e.g. 65536 bits), but the performance is too slow for practical use (some operations may take several minutes or even hours).
• For 128-bit security level, a 3072-bit key is required.

CS555

10

Cryptography

Department of Computer Science

Key Generation

• The RSA key-pair consists of:
• public key {n, e}
• private key {n, d}
• The numbers n and d are typically big integers (e.g. 3072 bits), while e is small, typically 65537.
• By definition, the RSA key-pairs has the following property:

​

CS555

11

Cryptography

Department of Computer Science

RSA Sign

• Signing a message msg with the private key exponent d:
• Calculate the message hash: h = hash(msg)
• Encrypt h to calculate the signature: s=h^d (mod n)

​

• The hash h should be in the range [0...n). The obtained signature s is an integer in the range [0...n).

​

CS555

12

Cryptography

Department of Computer Science

RSA Verify Signature

• Verifying a signature s for the message msg with the public key exponent e:
• Calculate the message hash: h = hash(msg)
• Decrypt the signature: h′=s^e(mod n)
• Compare h with h' to find whether the signature is valid or not

​

• If the signature is correct, then the following will be true:

h′=s^e(mod n)=(h^d)^e(mod n)=h

CS555

13

Cryptography

Department of Computer Science

The End

14

Cryptography

Department of Computer Science

Exercise

Q1. What is ElGamal encryption?

Q2. Explain ElGamal signature.

Q3. Explain CCA security.

Q4. What is RSA signature.

Q5. Explain RSA key generation.

Q6. Explain RSA Sign.

Q7. Explain RSA verify signature.

15

Cryptography

Department of Computer Science

Q8. ElGamal encryption system is an?

1. Symmetric key encryption algorithm
2. Asymmetric key encryption algorithm
3. Private key encryption algorithm
4. None of the above

Q9. Which one is the variant of ElGamal signature scheme.

1. DSA
2. RSA
3. CCA
4. Attack

Q10. CCA is an attack model for cryptanalysis where the cryptanalyst can gather information by obtaining the decryptions of.

1. Component of a ciphertext
2. Selected ciphertext
3. Chosen ciphertexts
1. None of the above

​

Cryptography

Department of Computer Science

Q11. Which key size is used by RSA algorithm?

1. 1012 bits
2. 1028 bits
3. 2028 bits
4. 2048 bits

Cryptography

Department of Computer Science