Spaurh의 느긋한 블로그



ELGAMAL Cryptosystem Programming Tip

public-key cryptosystem

p = larger prime
G = <Zp*, *> r = integer, e2 = e1 mod p (using exponential algorithm - square-and-multiply method)
e2, e1, p = infeasible to calculate

r = log(e1)e2 mod p (dicrete logarithm problem)
=>hard to calculate 

Encryption
C1 = e1^r mod p
C1 = (e2^r * P) mod p
key = (e1, e2, p)

Decryption
p = very larger prime
e1 = primitive root
select d
e2 = e1 mod p

P = C2 * [(C1^d)^-1] mod p

Proof
C2 * (C1^d)^-1 mod p = [(e2^r * P) * (e1^rd)^-1] mod p = e1^dr * P * (e1^nl)^-1 = P