공부중

  RSA는 사실상의 공개키 암호 알고리즘의 표준이다. 개발자 세 사람의 이름, Rivest-Shamir-Adleman의 첫 글자를 따서 붙인 이름이라고 한다. 인수분해 문재 해결 난이도가 높다는 사실에 기반하고 있는 알고리즘으로, 암호화와 전자서명 등에 사용된다. RSA 알고리즘에서 키를 생성하는 방법을 알아보겠다. 먼저 p와 q라는 두 개의 서로 다른 소수를 고른다. 두 수를 곱하여 N=pq를 구한다. Φ(N) = (p-1)(q-1)를 구한다. Φ(N)보단 작고, Φ(N)과 서로소인 정수 e를 찾는다. de ≡ 1 (mod Φ(N))을 만족하는 정수 d를 구한다. 이때, N, e는 공개되고, p, q, d는 비밀값이다. 공개키는 {e, N}이 되고, 프라이빗키는 {d, N}이 된다. 만약 공개키 N과 e로부터 프라이빗키 d를 구할 수 있다면 이 RSA 알고리즘은 해독되는 것이다. 이를 어렵게 하기 위해 각 소수 p와 q의 크기는 512비트로 권장되고 있다. 이렇게 만들어진 공개키를 가지고 평문 P를 암호문 C로 암호화할 때에는 다음과 같이 수행한다. C = P^e mod N 이다. 반면에 암호문 C를 평문 P로 복호화 할 때에는 다음과 같이 수행한다. P = C^d mod N 이다.

  RSA 알고리즘의 암호 분석은 n을 두 개의 소수로 인수분해 하는 것에 기반으로 하고 있다. 따라서 RSA의 안전성은 인수분해 성능에 달려있으며, 적절한 시간 내에 인수분해를 마칠 수 있는 방법이 개발되지 않는 한 RSA는 안전하다고 할 수 있다. 다만 RSA도 중간자 공격(MITM)이 적용될 수 있다. 즉, 송신자A가 수신자B에게 메시지를 보내가 위해서 수신자B의 공개키를 요청했을 때, 공격자M가 자신의 공개키를 해당 수신자B의 공개키인 것처럼 속여서 송신자A에게 건넬 수 있는 것이다. 송신자A는 공격자M의 공개키가 원래 수신자B의 공개키인 줄 착각하고 메시지를 공격자M의 공개키로 암호화하여 보내게 된다. 그러면 공격자M는 본인의 프라이빗키로 이 메시지를 복호화 하여 볼 수 있게 된다. 이를 막기 위해서는, 송신자A가 받은 공개키가 정말로 수신자B의 공개키인지 확인할 수 있는 인증이 필요하다. 이때 사용되는 것이 바로 공개키 인증서인 것이다.

  RSA 외의 또 다른 공개키 암호 시스템에는, Rabin, ElGamal, ECC(Elliptic Curve Cryptosystem) 등이 있다. ElGamal 방식의 경우, 이산 대수 문제에 근거하고 있으며, ECC 방식은 타원곡선이라는 이론에 근거하고 있다. 이러한 공개키 암호 시스템에는 2가지 문제가 있다. 하나는, 대칭키 암호 시스템보다 처리 속도가 훨씬 느리다는 점이다. 처리 속도를 해결하기 위해서 대칭키 암호 시스템의 장점과 공개키 암호 시스템의 장점을 결합한 하이브리드 암호 시스템이 생겨났다. 하이브리드 암호 시스템에서는, 메시지를 일단 고속의 대칭키 암호 시스템으로 암호화한다. 그리고 이 메시지를 암호화하는데 사용된 대칭키 암호키의 기밀성을 지키기 위해서 공개키 암호 시스템을 사용한다. 즉, 대칭키 암호의 키 배송 문제를 공개키 암호로 해결하고 있는 것이다. 공개키 암호 시스템의 또 다른 문제점 하나는, 중간자 공격(MITM)에 취약하다는 것이다. 이를 해결하기 위해 공개키에 대한 인증이 필요한다.