crytposystems

RSA and ElGamal implementation using Charm-Crypto

• RSA Cryptosystem (Based on Factorization Problem)

1. Select large primes p, q such that p≠ q
2. Calculate n = pq and Ø(n) = (p-1)(q-1)
3. Select b such that gcd(Ø(n),b) = 1 and 1<b< Ø(n)
4. Compute d such that bd ≅ 1(mod Ø(n))
5. Public key (n, b) and private key (d,n)
6. Encryption for message m: c = E_k(m) = m^b(mod n)
7. Decryption for cipher c: D_k(c) = c^d(mod n)

• ElGamal Cryptosystem (Based on Discrete Logarithm)

1. p: Prime, (Z_p^*, . ) and α ∈ Z_p^* primitive element.
2. {(p, α, a, ß): α^a ≅ ß (mod p)}
3. Public Key: (p, α, ß) and Private Key: a
4. Encryption for message m: Select random number r ∈ Z_p-1^*
   c = E_k(m) = (y₁,y₂) where y₁ = α^r (mod p) and y₂ = m. ß^r(mod p)
5. Decryption for cipher c: D_k(c) = y₂.(y₁^a)^-1