본문 바로가기

Public Key

ElGamal Public Key Cryptosystem 일반적인 공개키 암호화의 안전성은 그것의 소인수분해가 얼마나 어려운가에 달려있다. 하지만, 그것 외에도 discrete logarithm 문제를 효율적으로 계산할 수 없다는 것에 착안하여 공개키 방식의 암호화를 할 수도 있다. ElGamal 공개키 암호화가 대표적인 방법이다. Alice가 Bob에게 어떤 메세지 m을 보내려고 한다. Bob은 커다란 Prime Number p를 선택하고, 그것의 Primitive Root α를 선택한다. 여기서, m은 0 ≤ m < p인 정수이다. m이 크다면, 이것을 블럭 크기로 분할한다. Bob은 비밀키 a를 선택하고, β ≡ α^a (mod p)를 계산한다. 여기서 (p, α, β)를 공개하며, 이것이 Bob의 공개키가 된다. Alice는 다음의 과정을 거친다. 1... 더보기
RSA Algorithm 가장 대표적인 공개키 암호인 RSA는, 최초 개발자인 Rivest, Shamir, Adleman의 첫글자에서 따온 것이다. RSA는 75자리 이상의 큰 소수인 p, q를 이용하며, 이 체계의 안전성은 이 두 수의 곱인 n = pq가 얼마나 소인수분해하기가 어렵냐에 의해서 결정된다. 암호를 받을 사람은, 다음의 단계를 준비한다. 1. 큰 소수 p, q를 선택하여 n = pq를 계산한다. 2. e * d ≡ 1 (mod Φ(n))인 e와 d를 선택한다. 여기서 e가 gcd(e, n) = 1인지 아닌지는 유클리드 알고리즘으로 신속하게 판단할 수 있다. 그리고 d를 결정하는 문제 또한 유클리드 알고리즘으로 계산할 수 있다. 3. (n, e)를 공개한다. 이것이 공개키가 된다. 4. p, q, d를 절대 비밀로 .. 더보기
Public Key System 대칭키 암호 시스템은, Encryption / Decryption 과정에서 동일한 키가 사용된, 이와 반대로 비대칭키 암호 시스템에서는, Encryption 과정에서 사용되는 키와 Decryption 과정에서 사용되는 키가 다르다. DES, AES에서와 같은 대칭키, 블럭 암호 시스템에서는 동일한 키가 사용됨으로서 Encrpyion / Decryption 과정을 함께 수행할 수 있기 때문에 상대적으로 속도가 빨라진다는 점을 장점이라고 생각할 수도 있다. 하지만, 결국 Encryption / Decryption 과정에서 키가 필요하므로, Ciphertext를 해석할 키를 상대방에게 안전하게 전달해야 한다는 문제가 생기게 된다. 비대칭 암호 시스템은, 공개키 암호 시스템이라고도 하는데, 이것은 한 키는 비밀.. 더보기

티스토리툴바