비대칭키 암호(공개키 암호)

키 배송 문제

대칭키 암호를 사용하기 위해서는 키 배송 문제(Key distribution problem)를 해결해야 한다.

키를 보내지 않으면 수신자 밥은 수신된 암호문을 복호화할 수 없다. 그렇다고 암호화되지 않은 키를 보내면 도청자인 이브(eavesdropper)도 복호화할 수 있다.

키 배송 문제를 해결하기 위해 아래와 같은 4가지 방법이 있다.

 

- 키의 사전 공유에 의한 해결

키 사전 분배란 키 관리기관(TA,  Trusted Authority)이 사전에 임의의 두 사용자(A,B)에게 비밀 경로를 통해 임의 키 K(a,b) = K(b,a) 를 선택하여 전달하는 방법이다.

이 방법은 일반적으로 TA와 네트워크 상의 모든 사용자 사이에 안전한 통로가 필요하며 사용자가 많은 경우에 TA는 물론 사용자들도 많은 키를 관리해야 하는 단점이 있다. (사용자가 많아질 수록 관리가 복잡해지며 비용이 많이 지불됨)

 

- 키배포 센터에 의한 해결 (온라인 키 분배)

암호 통신이 필요해질 때마다 통신용 키를 키배포 센터(KDC, key distribution center)라는 신뢰받는 제3자에 의뢰해서 개인과 키배포 센터 사이에만 키를 사전에 공유하는 것이다. (KDC는 TA와 같다고 생각해도 됨)

KDC는 n명의 사용자가 있다면 n개의 키를 DB에 저장한다.

 

- Diffie-Hellman 키 교환에 의한 해결 

Diffie-Hellman 키 교환은 공개키 암호방식을 최초로 제안한 Whitfield Diffie와 Martin Hellman이 발명한 알고리즘이다. 공개키 암호방식의 개념을 이용하여 두 사용자 간에 공통의 암호화키를 안전하게 공유할 수 있는 방법을 제시하였다.

DH 프로토콜 방법에서는 양쪽 통신주체가 KDC 없이 대칭 세션키를 생성한다. 대칭키를 만들기 전에 양쪽은 두 개의 수 p와 g를 선택해야 한다. (p와 g는 비밀로 할 필요가 없음) 여기서 p는 매우 큰 소수로서 300자리가 넘는 10진수이다.(1024비트)

키 교환이라는 이름이 붙어 있으나 실제로는 키를 교환하는 것이 아닌 합의하는 것이며 유한체상의 이산대수 문제(DLP)를 풀기 어렵다는 사실이 DH 키 교환을 뒷받침하고 있다.

 

-> DH 절차

1. Alice가 임의의 큰 수 a를 0 ≤ a ≤ p-1 안에서 선택하고 A = g^a mod p 를 계산한다.

2. Bob이 다른 임의의 수 b를 0 ≤ b ≤ p-1 안에서 선택하고 B = g^b mod p를 계산한다.

3. Alice는 A를 Bob에게 보낸다. a 값을 보내는 것이 아니라 A(gª mod p)만 보낸다.

4. Bob도 B를 Alice에게 보낸다. 역시 b 값이 아닌 B(g^b mod p)만 보낸다.

5. Alice는 K=A^b mod p를 계산한다.

6. Bob은 K=B^a mod p를 계산한다.

7. 이렇게 구한 K는 앞으로 세션에 사용될 대칭키가 된다. (K=g^ab mod p)

 

Diffie-Hellman의 안전성

1. 이산대수 공격

키 교환의 안전성은 DLP 문제를 풀기 어렵다는데 기반을 두고 있다.

만약 Eve가 A와 B를 가로채어 A=g^a mod p 에서 a를 구하고, B=g^b mod p에서 b를 구할 수 있다면 대칭키 K=g^ab mod p를 계산할 수 있게 되어 비밀키가 더 이상 비밀키가 되지 못한다.

 

2. 서비스 거부 공격(DoS, Denial of Service)

DH 프로토콜은 지수 함수에 기초하고 있으므로 계산이 복잡하여 많은 수의 장치와 동시에 통신을 하고 있을 경우 비밀키 생성에 큰 지연 시간이 발생할 수 있다.

따라서 DH 기법은 제3자에 의한 DoS 공격에 대한 취약점을 가지고 있다. 즉, 악의적인 제3자가 공격 대상 서버에 IP 스푸핑 등을 통해 위조한 키 생성 요청을 동시에 다수 요청함으로써 키 생성 부담으로 서버가 마비되도록 공격할 수 있다.

 

3. 중간자 공격(Man-in-the-middle attack)

키 교환 프로토콜은 인증 단계가 없기 때문에 이런 공격에 취약하다. 이 공격을 막기 위해 전자셔명과 PKI 등을 이용해 인증 과정을 거쳐야 한다.

 

- 공개키 암호에 의한 해결

대칭키 암호에서는 암호화키와 복호화키가 같은 것이다. 하지만 공개키 암호에서는 암호화키와 복호화키는 다르다.

암호화키가 알려져도 Eve는 복호화할 복호화키가 없기 때문에 복호화할 수 없다.

 

공개키 암호(public-key cryptography)

대칭키 암호는 평문을 복잡한 형태로 변환해서 기밀성을 유지한다. 반면 공개키 암호는 수학적으로 해결하기 곤란한 문제를 토대로 기밀성을 유지한다.

공개키 암호에서는 암호화키와 복호화키가 분리되어 있으며 이 키쌍을 이루는 2개의 키는 서로 수학적 관계가 있다. 이 때문에 공개키와 개인키를 각각 별개로 만들 수 없다.

 

RSA 암호시스템

RSA는 공개키 암호 알고리즘 중의 하나이며 인수분해 문제 해결의 높은 난이도를 이용한 가장 대표적인 공개키 암호 알고리즘으로 암호화뿐 아니라 전자서명의 용도로도 사용한다.

 

- 암호화와 복호화

RSA에서는 두 개의 지수 e와 d를 사용한다. 여기서 e는 공개하는 값이고 d는 비밀로 유지하는 값이다. P는 평문이고 C는 암호문이다.

이때 Alice는 C=P^e mod n을 이용하여 평문 P에서 암호문 C를 생성한다. Bob은 암호문 C에서 P=C^d mod n을 구하여 Alice가 보낸 평문을 얻는다. 모듈러 n은 매우 큰 수이고 키 생성 프로세스를 통해 만들어진다.

 

- 키 생성

p와 q라고 하는 두 개의 서로 다른 소수를 먼저 고른다. 그 후 두 수를 곱하여 N=pq 을 찾는다.

Φ(N)=(p-1)(q-1)를 구한다.

Φ(N)보단 작으면서 Φ(N)과 서로소인 정수 e를 찾는다.

확장된 유클리드 호제법을 이용하여 d×e를 Φ(N)으로 나누었을 때 나머지가 1인 정수 d를 구한다.

 

만약 공개키 n과 e로부터 비밀키 d를 구할 수 있다면 RSA는 해독되게 된다. RSA 알고리즘의 안전성은 n의 소인수 분해, 즉 p와 q를 구해내는 것에 달려 있다.

안전을 위해서 권장되는 각 소수 p와 q의 크기는 512비트이다. 이 크기는 10진수로 약 154자리수이다. 이런 소수를 사용하면 모듈러로 사용할 n은 1024비트로 십진수 309자리가 된다.

 

- RSA에 대한 공격

1. 수학적 공격(소인수분해 공격)

수학적 공격의 핵심은 두 개의 소수 곱을 인수분해 하고자 하는 노력이다. 수학적 공격을 막으려면 키의 길이가 긴 걸 사용해야 한다. 그래서 개인키 d의 비트수가 크면 클수록 안전하다.

하지만 키 생성과 암/복호화에서의 계산량을 고려하면 복잡한 문제가 될 수 있다. 키 길이가 길어지면 시스템 처리 속도가 느려지기 때문이다.

 

2. 타이밍 공격(시간 공격)

복호화 알고리즘의 실행 시간에 따라 키 길이를 추측하는 공격이다. Random delay 방법 등을 사용해 소요되는 시간이 드러나지 않게 막아 타이밍 공격을 막는다.

 

3. 선택 암호문 공격(CCA)

공격자가 자신이 만든 위조 암호문을 서버에 여러 차례 보내고 서버가 회신해 주는 오류 메시지나 타이밍을 해석해서 키나 평문 정보를 조금이라도 얻으려고 한다. 이를 막기 위해 최적 비대칭 암호화 패딩(OAEP)이라고 하는 프로시저를 사용해 평문을 수정할 것을 권장한다.

 

+ 최적 비대칭키 암호 패딩(OAEP)

RSA-OAEP는 RSA를 개량한 알고리즘이다. RSA-OAEP 복호화에서는 평문 해시값과 정해진 개수의 0 등으로 만들어진 인증 정보를 평문 앞에 추가하고 RSA로 암호화한다.

RSA-OAEP의 복호화에서는 RSA로 복호화한 후 올바른 인증 정보가 나타나지 않으면 평문을 알고 있는 사람이 만든 암호문이 아니라고 판단해서 오류 메시지를 회신한다. (어떤 오류인지를 알리지 않음)

이와 같이 하면 공격자가 RSA-OAEP 복호 오라클로부터 정보를 얻을 수가 없어져서 선택 암호문 공격으로부터 안전하게 된다.

 

Rabin 암호시스템

RSA 암호시스템의 변형이다. RSA가 지수합동에 근거하고 있고, Rabin은 2차 합동에 근거하고 있다.

Rabin 암호시스템에서 암호화는 매우 간단하다. 연산은 오직 한 번의 곱셈으로 이루어져 있고 이 연산은 매우 빨리 수행된다. 그래서 Rabin 암호시스템은 성능이 낮은 플랫폼에서 잘 활용될 수 있다.

Rabin 시스템은 p와 q가 충분히 크기만 하면 안전하다. (소인수분해 문제)

Rabin 암호시스템은 결정적 알고리즘이 아니다. 복호화를 하면 동등한 확률로 4개의 평문 후보가 나타난다.

 

ElGamal 방식

ElGamal은 이산대수 문제(DLP)에 근거하여 만든 시스템이다. 디지털 서명, 암호화, 키 교환에 사용할 수 있는 공개키 알고리즘이지만 다른 알고리즘과 비교할 때 가장 느리다.

평문이 암호문으로 될 때 순서쌍으로 표현되므로 암호문의 길이는 평문의 2배가 된다.

 

타원 곡선 암호 (ECC)

RSA와 ElGamal이 안전한 공개키 암호시스템이지만 보안을 위해서는 키의길이가 매우 커야 한다는 단점이 있다. 키의 길이는 짧아도 보안을 제공하기 위한 시스템이 타원 곡선 암호 시스템이다.

타원 곡선을 이용하면 암호화, 서명, 키 합의 같은 일반적인 공개키 암/복호화 연산을 기존 기술들보다 빠르게 수행할 수 있다.

 

- 특징

다양한 암호방식 설계가 용이하며 하드웨어와 소프트웨어 둘 다 구현하기 용이하다. 메모리와 처리 능력이 제한된 스마트카드나 무선통신 단말기에 특히 효율적이다.

타원곡선 암호는 유한체상에서 E: y² = x³ + ax + b 의 형태로 정의되는 타원곡선상의 점들 간의 덧셈 연산을 통해 키를 산출한다.

 

하이브리드 암호시스템(hybrid cryptosystem)

대칭키 암호를 사용하면 기밀성을 유지한 통신이 가능해지지만 키 배송 문제를 해결해야 한다. 공개키 암호를 사용하면 키 배송 문제는 없어지지만 대칭키 암호에 비해 처리속도가 훨씬 느리며 중간자 공격에 취약하다는 단점이 있다.

공개키 암호 방식과 대칭키 암호 방식의 장점을 조합하기 위해 하이브리드 암호시스템을 사용한다.

 

하이브리드 암호 시스템에서는 메시지를 고속의 대칭키 암호로 암호화한다. 그리고 대칭키 암호키의 기밀성을 지키기 위해서 대칭키에 공개키 암호를 사용한다.

중간자 공격은 인증을 사용하여 막는다.