Table of Contents

• 1. Cryptosystem
  • 1.1. RSA
    • 1.1.1. Key generation
    • 1.1.2. Encryption
    • 1.1.3. Decryption
  • 1.2. ElGamal
    • 1.2.1. Key generation
    • 1.2.2. Encryption
    • 1.2.3. Decryption

Cryptosystem

Java implementation of RSA & ElGamal cryptosystems

RSA

Security of RSA depends on the difficulty of factoring large integers.

Key generation

1. Choose the size key (integer)
2. Construct two random prime integer p and q as :
   • 2^[k/2]-1 ≤ p, q ≤ 2^[k/2]-1 - 1
3. N = p * q
4. φ(N) = (p - 1)(q - 1) (Indicatrice d'Euler)
5. Choose e in (Z/_φ(N)Z)^* and compute d as :
   • ed ≡ 1 (mod φ(N))

public key	secret key
(N, e)	(d, p, q)

Encryption

A message m is in Z/_NZ (the size of the message is less or equal to the size key)

• Alice has the public key (N, e)
• c = m^e (mod N)

Decryption

• Bob has the private key (d, p, q)
• c^d (mod N) = m

ElGamal

Security of the ElGamal algorithm depends on the difficulty of computing discrete logs in a large prime modulus

Key generation

1. Choose a random prime integer p as p = 2 p' + 1 with p' is prime
2. Choose a random integer in (Z/_pZ)^* of order p'
3. Choose a random integer x in [0, p' - 1]
4. Compute h = g^x in Z/_pZ

public key	secret key
(p, g, h)	(p, x)

Encryption

1. Choose a random r in [1, p' - 1]
2. The encrypted message is (g^r, m*h^r)

ElGamal encryption is probabilistic, meaning that a single plaintext can be encrypted to many possible ciphertexts (but ElGamal encryption produces a 2:1 expansion in size from plaintext to ciphertext).

Decryption

• Entry : (g^r, m*h^r)
  • h = g^{x 1}
  • (g^r)^x = (g^x)^r = h^r
  • message = m*h^r/h^r

Footnotes:

¹

Cf. 4. of Key generation