정보보안기사 필기 - 4(비대칭키 암호)

- 키 배송 문제

대칭키 암호를 사용하려고 하면 송신자와 수신자는 서로 키를 주고받아야합니다. 만약, 키를 보내지 않으면 수신자는 수신한 암호문을 복호화할 수 없고 그렇다고 암호화 되지 않은 키를 보내면 도청자가 복호화할 수 있습니다. 키를 보내지 않으면 안되는데 키를 보내서도 안된다. 이것이 대칭키 암호의 키 배송문제입니다.

 

- 키 배송 문제 해결

 

<키의 사전 공유에 의한 해결>

키 사전 분배란 키 관리기관(TA, trusted authority)이 사전에 임의의 두사용자에게 비밀 경로를 통하여 키를 전달하는 방법입니다. 이 방법은 TA와 네트워크 상의 모든 사용자 사이에 안전한 통로가 필요하며 사용자가 많은 경우에 TA와 사용자들은 많은 키를 관리해야하는 문제점이 있습니다. 사용자가 N명일때 TA가 관리해야하는 키의 수는 N(N-1)/2개로 관리비용이 많이 듭니다.

 

<키 배포센터에 의한 해결>

암호 통신이 필요해질 때마다 키배포센터(KDC, Key Distribution Center)라는 신뢰받는 제 3자에 의뢰해서 개인과 키배포 센터 사이에서만 키를 사전에 공유하는 방법(TA가 네트워크 상의 모든 사용자와 필요할때마다 키를 공유하는 방법)입니다. 아래는 절차입니다.

 

1. 송신자 앨리스는 키 배포센터에 밥과 통신하고싶다고 신청합니다.

2. 키배포센터는 일시적인 세션키(K)를 만듭니다. 이것은 앨리스와 밥의 대칭키로 앨리스와 밥(수신자)에게 전달 및 이번 한번만 사용하는 키입니다.

3. 키배포센터는 데이터베이스에서 앨리스의 키와 밥의 키를 꺼냅니다.

4. 키 배포센터는 앨리스의 키로 세션키를 암호화하여 앨리스에게 보냅니다.

5. 키 배포센터는 밥의 키로 세션키를 암호화하여 밥에게 보냅니다.

6. 앨리스는 자신의 키로 세션키를 복호화하여 평문과 함께 암호화한 후 밥에게 보냅니다.

7. 밥은 키 배포센터로 부터 받은 암호문을 자신의 키로 복호화 하여 세션키를 얻어내어, 앨리스가 보낸 암호문을 세션키로 복호화합니다.

 

<Diff-Hellmam 키 교환에 의한 해결>

Diff-Hellmam 키 교환은 1976년 휘트필드 디피(Whiutfield Diffe)와 마틴 헬먼(Martin Hellman)이 발명한 알고리즘으로 유한체상의 이산대수 문제를 풀기 어렵다는 사실(Diff-Hellmam 키 교환은 R1과 g,p를 가지고 x값을 유추하기 어렵다)로 만들어낸 알고리즘입니다. 키 교환이라는 이름이 붙어있지만 실제로는 키를 교환하는 것이 아닌 공유할 키를 계산하여 만들어내는 것으로 키 합의 라고도 불립니다. 아래는 간단한 절차입니다.

 

1. 앨리스는  임의의 x를 선택하여 R1 = g^x mod p 를 계산하여 밥에게 R1을 보냅니다..(이때 g와 p는 공개되며 p는 소수입니다.)

2. 밥은 임의의 y를 선택하여 R2 = g^y mod p 를 계산하여, R2를 앨리스에게 보냅니다.

3. 앨리스는 K = (R2)^x mod p를 계산하여 K(대칭키)를 구합니다.

4. 밥은 K = (R1)^y mod p를 계산하여 K(대칭키)를 구합니다.

(R2)^y mod p = (R1)^x mod p = g^xy mod p

 

Diff-Hellman 키 교환의 공격 방법은 아래와 같습니다.

1. 이산대수 공격 : 도청자 Eve가 R1에서 이산대수를 풀어 x값을 알고 R2에서 y값을 알아내면 키를 알 수 있습니다.

2. 서비스 거부 공격 : DH 기법은 계산이 복잡하여 비밀키 생성에 큰 지연 시간이 발생할 수 있습니다. 악의적인 제3자가 공격 대상 서버에대해 키 생성 요청을 동시에 다수 요청함으로써 키 생성 부담으로 서버가 마비되도록 공격 할 수 있습니다.

3. 중간자 공격 : 앨리스는 이브와 이브는 밥과 통신하면서 앨리스에게 밥처럼 밥에게는 앨리스처럼 위장하여 통신하는 방법입니다. 

 

<공개키 암호에 의한 해결>

공개키 암호에 의한 대칭키 교환의 방식은 아래와 같습니다.

 

1. 수신자 밥은 송신자 앨리스에게 암호화키를 알려줍니다.

2. 송신자 앨리스는 암호화키로 교환할 대칭키를 암호화하여 밥에게 보냅니다.

3. 밥은 자신만 알고 있는 복호화키(비밀키)로 암호문을 복호화하여 대칭키를 얻어냅니다.

 

- 공개키 암호 RSA

 

<RSA 암호시스템>

RSA는 공개키 암호 알고리즘 중의 하나이며 세계적으로 표준 알고리즘입니다.  RSA의 키 생성 알고리즘은 간단하게 아래와 같습니다.

 

1. p, q라고하는 두개의 서로다른 소수를 고릅니다.

2. 두수를 곱하여 N = pq를 찾습니다.

3. O(N) = (p-1)(q-1)을 구합니다.

4. O(N) 보다 작고, O(N)과 서로소인 정수 e를 찾습니다.

5. de mod O(N) = 1인 d를 구합니다.

 

<RSA를 이용한 암,복호화 과정>

1. 수신자 밥은 송신자 앨리스에게 공개키(e, n)을 알려줍니다.

2. 앨리스는 P(평문)^e mod n의 값인 C(암호문)을 수신자인 밥에게 보냅니다.

3. 밥은 자신의 개인키인 (d, n)을 이용해 C^d mod n 값인 P를 얻어냅니다.

 

<RSA의 간단한 예시>

1. p = 17 q = 11

2. N = 17 * 11 = 187

3. O(N) = (17-1) * (11-1) = 160

4. 160보다 작고 서로소인 e = 7

5. d*7 mod 160 = 1를 만족하는 d = 23

6. 수신자 밥은 송신자 앨리스에게 공개키(7, 187)을 알려줍니다.

7. 앨리스는 88^7 mod 187의 값인 11을 수신자인 밥에게 보냅니다.

8. 밥은 자신의 개인키인 (23, 187)을 이용해 11^23 mod 187 값인 88을 얻어냅니다.

 

<RSA의 공격 방법>

1. 수학적 공격 : 도청자 Eve가 얻어낼 수 있는 정보는 (e, N)입니다. 이를 토대로 d를 알아내기 위해선 de mod O(N) = 1의 관계식을 이용해야합니다. 이 식을 이용하려면 O(N)을 구해야합니다. O(N)은 (p-1)(q-1) 이므로 N을 소인수 분해해서 알아내야합니다. 하지만 엄청 큰 소인수분해문제는 풀기에 오랜시간이 걸리므로 RSA의 안전성은 N을 소인수분해 하여 p,q를 구해내는 것에 달려있습니다.

2. 타이밍 공격 : 복호화 알고리즘은 실행 시간에 따라 달라지므로 키길이를 추측하여 수학적 공격에 사용할 수 있습니다.

3. 선택암호문공격 : 공격자는 자신이 만든 위조 암호문을 서버에 여러차례 보내고, 서버가 회신해주는 오류 메시지나 타이밍을 해석해서 키나 평문 정보를 조금이라도 얻으려하는 방법

 

- 공개키 암호 Rabin

Rabin 암호시스템은 합성수 모듈로에 관하여 제곱근을 찾기 어렵다는 사실로부터 안전성을 얻습니다. 즉, 소인수 분해 문제를 푸는 어려움과 동등한 문제입니다.  Rabin 암호시스템에서 암호화는 매우 간단합니다. 따라서 성능이 낮은 플랫폼에서 잘 활용되며 예시로 스마트카드를 들 수 있습니다.

 

- 공개키 암호 ElGamel 

ElGamel 방식은 이산대수 문제에 근거해서 만든 시스템입니다. 실제로 Diffe-Hellman 알고리즘의 확장판으로 다른 알고리즘에 비교했을때 가장 느립니다.

 

- 공개키 암호 타원 곡선 암호(ECC, Elliotic Curvce Cryptosystem)

RSA와 ElGamel은 안전한 비대칭키 암호시스템이기는 하지만 보안을 위해서는 키의 길이가 매우커야한다는 단점이 있습니다. 연구원들은 이들과 동일한 수준의 보안성을 제공하면서 키의 길이는 짧아도 되는 암호시스템에대해서 연구하였고 그 결과물이 ECC입니다. ECC는 유한체 위에서 정의된 타원 곡선 군에서의 이산대수의 문제에 기초한 공개키 암호알고리즘입니다. RSA보다 키의 비트수를 적게하면서도 동일한 성능을 제공합니다.(160비트 ECC는 1024비트 RSA와 동이라한 보안수준) E :y^2 = x^3+ax+b 의 형태로 정의되는 타원곡선상의 점들간의 덧셈 연산을 통해 키를 산출합니다. 타원 곡선을 주기적으로 바꿔 보안을 강화할 수 있습니다.

 

- 하이브리드 암호

평문은 대칭키로 암호화하고 대칭키는 공개키로 암호화하는 방식입니다.