Cryptosystem

○Diffie-Hellman's Key Exchange

 ▷Discrete Log Problem을 이용한 Key교환

 ▷큰 소수 p와 그의 generator g를 기준으로

 ▷서로 Personal key X와 Public key y를 가짐.

  ▷y = g^X mod p

 

 ▷secret Key K = g^(X_A×X_B) mod p

  ▷= y_B^X_A mod p = y_A^X_B mod p

 

 

○ElGamal Cryptosysstem

 ▷Discrete Log Problem의 어려움을 이용한 암호화

 ▷Personal Key x와 이에 대응하는 Public Key p, g, y를 가짐.

  ▷p: 큰 소수

  ▷g: generator

  ▷y: g^x mod p

 

 ▷내용 M을 a, b로 나누어 암호화함. (k: 무작위 수)

  ▷a = g^k mod p

  ▷b = y^k M mod p

 

 ▷내용 M = b / a^x mod p 으로 복호화함.

  ▷M = y^k M / g^kx mod p = g^kx M / g^kx mod p = M mod p

 

○RSA Cryptosystem

 ▷큰 수의 소인수분해의 어려움을 이용

 ▷Public Key n, e와 Personal Key d를 가짐. (r = φ(n))

  ▷n : pq (p, q : 매우 큰 무작위 소수)

  ▷e : r과 서로소인 수들 중 하나

  ▷d : modular r 공간에서 e의 inverse (e^-1 mod r)

 

 ▷암호화: E(M) = M^e mod n = C

 

 ▷복호화: D(C) = C^d mod n = M

  ▷C^d mod n = M^ed = M^kφ(n) = M mod n

  ▷ed = 1 mod r -> ed = kr+1

  ▷gcd(a, n) = 1에서, a^φ(n) = 1 mod n

 

 ▷RSA의 성립조건

  ▷gcd(M, n) = 1이여야함.

  ▷실패할 가능성이 매우 낮음 (1/p + 1/q - 1/pq)