SE 04) 1. 비대칭키 암호

(1) 키 배송 문제

 

  1) 개요

 

     ① 대칭키 암호를 사용하려고 하면 키 배송 문제 (key distribution problem)가 발생한다.

     ② 키를 보내지 않으면 수신자 밥은 수신한 암호문을 복호화할 수 없다. 그렇다고 암호화되지 않은 키를 보내면 도청자 이브도 복호화할 수 있다. 키를 보내지 않으면 안 되는데 키를 보내서도 안 된다. 이것이 대칭키 암호의 키 배송 문제이다.

     ③ 키 배송 문제를 해결하지 위한 방법에는 몇 가지가 있다.

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

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

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

        ■ 공개키 암호에 의한 해결

 

 2) 키의 사전 공유에 의한 해결

 

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

     ② 이 방법은 일반적으로 TA와 네트워크 상의 모든 사용자 사이에 안전한 통로가 필요하며, 사용자가 많은 경우에 TA는 물론 사용자들도 많은 키를 관리해야 하는 문제점이 있다.

     ③ 즉 n명의 사용자가 있다면 각 사용자는 n-1가지 키를 관리해야 하며 TA는 n(n-1)/2가지 키를 관리하여야 하므로 매우 복잡하고 관리 비용이 많이 지불된다.

 

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

 

   (A) 개요

       ① 암호 통신이 필요해질 때마다 통신용 키를 키배포 센터(KDC, key distribution center)*라는 신뢰받는 제3자에 의뢰해서 개인과 키배포 센터 사이에서만 키를 사전에 공유하는 것이다. (TA가 네트워크 상의 모든 사용자와 필요할 때마다 키를 공유하는 방법)

       ② 회사 안에 키배포 센터의 역할을 하는 컴퓨터를 지정해둔다. n명의 사원이 있다면 n개의 키를 컴퓨터 데이터베이스에 저장한다.

 

 * 키배포 센터 (KDC, Key Distribution Center)

  - KDC는 키 관리 기관 (TA)과 같다고 봐도 무방하다.

 

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

 

   (A) 개요

       ① Diffie-Hellman 키 교환(Diffe-Hellman key exchange)은 1976년에 공개키 암호방식을 최초로 제안한 휘트필드 디피와 마틴 헬먼이 발명한 알고리즘이다.

       ② 공개키 암호 방식의 개념을 이용하여 두 사용자 간에 공통의 암호화키를 안전하게 공유할 수 있는 방법을 제시하였으며, 많은 키 분배 방식에 관한 연구의 기본이 되었다. (최초의 비밀키 교환 프로토콜)

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

       ④ 「키 교환」이라는 이름이 붙어 있지만, 실제로는 키를 교환하는 것이 아니라 공유할 키를 계산하여 만들어 내는 것이다. 그 때문에 Diffie-Hellman 키 합의라 불리기도 한다.

       ⑤ 유한 체상의 이산 대수 문제(DLP, Discrete Logarithm Problem)를 풀기 어렵다는 사실이 Diffe-Hellman 키 교환을 뒷받침하고 있다. (이산 대수 문제 : Gª mod P에서 수 A를 구하는 문제)

 

 * 소수 p, g

  - p와 g는 비밀로 할 필요는 없고, 도청자 이브에게 알려져도 문제없다.

 

   (B) 절차

       ① 앨리스는 임의의 큰 수 x를 0 ≤ x ≤ p-1 안에서 선택하고 R₁ = g(^x) mod p를 계산한다.

       ② 밥은 다른 임의의 큰 수 y를 0 ≤ y ≤ p-1 안에서 선택하고 R₂ = g(^y) mod p를 계산한다.

       ③ 앨리스는 R₁을 밥에게 보낸다. 여기서 앨리스틑 x값을 보내는 것은 아니다. 오직 R₁만 보낸다.

       ④ 밥은 R₂를 앨리스에게 보낸다. 여기서도 밥은 y값을 보내는 것이 아니고 오직 R₂만 보낸다.

       ⑤ 앨리스는 K = (R₂)^x mod p를 계산한다.

       ⑥ 밥은 K=(R₁)^y mod p를 계산한다.

       ⑦ 이렇게 구한 값 K는 아래와 같고 이것이 세션에 사용될 대칭키이다.

K=(g^x mod p)^y mod p = (g^y mod p)^x mod p = g^xy mod p

 

   (C) Diffie-Hellman의 안전성

       ① 이산대수 공격

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

          ■ 이브가 R₁과 R₂를 가로챌 수 있을 것이다. 만약 이브가 R₁ = g^x mod p에서 x를 구하고 R₂ = g^y mod p에서 y를 구할 수 있다면, 이브는 대칭키 K = g^xy mod p를 계산할 수 있게 된다. 이렇게 되면 비밀키가 더 이상 비밀키가 더이상 비밀이 되지 못한다.

       ② 서비스 거부 공격 (Dos, Denial of Service)

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

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

       ③ 중간자 공격(man-in-the-middle attack)*

          ■ 키 교환 프로토콜은 이런 공격에 취약한데 그 이유는 인증 단계가 없기 때문이다. 이런 공격을 막기 위해서는 전자 서명과 공개키 인증서 등을 이용하면 된다.

 

* 중간자 공격

  - 이 공격은 양동이 소방대 공격이라고도 한다. 그 이유는 마치 불을 끄려고 한줄로 늘어선 자원 봉사자들이 물이든 양동이를 옆 사람에게 전달하는 것처럼 보이기 때문이다. Diffie-Hellman에 기반을 둔 다음 방법에서는 이런 공격을 막기 위해 인증을 사용한다.

 

TIP

√ 국-대-국 키 합의

   - 국-대-국 프로토콜 (STS, Station-To-Station protocol)은 Diffie-Hellman에 기반을 둔 방법이다. 여기서는 앨리스와 밥 사이의 세션키를 만들기 위해 공개키 인증서를 이용한 전자 서명을 사용한다. 국-대-국 프로토콜은 중간자 공격을 막는다.

 

   (D) Diffie-Hellman 알고리즘의 응용

 

 5) 공개키 암호에 의한 해결

   ① 대칭키 암호에서 「암호화키」와 「복호화키」는 같은 것이다. 그러나 공개키 암호에서는 「암호화키」와 「복호화키」는 다른 것이다.

   ② 수신자는 미리 「암호화키」를 송신자에게 알려 준다. 이 「암호화키」는 도청자에게 알려져도 괜찮다. 송신자는 「암호화키」로 암호화하여 수신자에게 보낸다.

   ③ 복호화할 수 있는 것은 「복호화키」를 가지고 있는 사람(수신자)뿐이다. 이렇게 하면 「복호화키」를 수신자에게 배송할 필요가 없어진다.

 

(2) 공개키 암호 (public-key cryptography)

 

 1) 개요

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

   ② 공개키 암호*에서는 「암호화키」와 「복호화키」가 분리되어 있다. 송신자는 「암호화키」를 사용하여 메시지를 암호화하고, 수신자는 「복호화키」를 사용하여 암호문을 복호화한다.

   ③ 키쌍을 이루고 있는 2개의 키는 서로 밀접한 관계(수학적 관계)가 있다. 이 때문에 공개키와 개인키를 각각 별개로 만들 수는 없다.

 

 2) 공개키 암호의 중간자(man-in-the-middle) 공격

   ① 공개키 암호에서 중간자 공격은 기밀성에 대해 매우 유효한 공격 방법이다.

   ② 중간자 공격이란, 적극적 공격자 맬로리가 송신자와 수신자 사이에 들어가서 송신자에 대해서는 수신자처럼, 수신자에 대해서는 송신자처럼 행세하는 공격이다. 중간자라는 것은 「사이에 있는 사람」이라는 의미이다.

   ③ 중간자 공격은 RSA뿐만 아니라 어떤 공개키 암호에도 사용할 수 있다.

   ④ 중간자 공격을 막기 위해서는 입수한 공개키가 정말로 밥의 것이라는 것을 확인할 수단인 인증이 필요하다. 이때 사용되는 것이 공개키 인증서이다.

 

(3) RSA 암호시스템

 

 1) 개요

 

   (A) 기본 개념

      ① RSA는 공개키 암호 알고리즘 중 하나이며, 세계적으로 사실상의 표준이다.

      ② RSA라는 이름은 개발자 세 사람의 이름 즉, Rivest-Shamir-Adleman의 첫 글자를 따서 붙여졌다.

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

      ④ SSL 프로토콜을 가진 많은 웹 브라우저, PGP 그리고 공개키 암호 시스템을 사용하는 정부 시스템 등이 RSA를 사용한다.

 

   (B) 암호화와 복호화

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

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

 

   (C) 키 생성

      ① 알고리즘

          ■ p와 q라고 하는 두 개의 서로 다른 (p ≠ q) 소수를 고른다.

          ■ 두 수를 곱하여 N = pq를 찾는다.

          ■ ∮(N) = (p - 1)(q - 1)을 구한다.

          ■ ∮(N)보단 작고, ∮(N)과 서로소인 정수 e를 찾는다.

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

      ② 만약 공개키 n과 e로부터 비밀키 d를 구할 수 있다면 RSA는 해독되게 된다. 이렇게 되기 위해서는 공개키 n으로부터 ∮(n) = (p-1)(q-1)을 구해내야 한다. ∮(n)을 구하게 되면 유클리드 알고리즘을 이용하여 쉽게 d를 구할 수가 있게 되므로 RSA알고리즘의 안전성은 n의 소인수 분해, 즉 p와 q를 구해내는 것에 달려있다.

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

 

2) RSA 알고리즘 예

    ① 두 소수 p = 17과 q = 11을 선택한다.

    ② N = p × q = 17 × 11 = 187을 계산한다.

    ③ ∮(N) = (p - 1)(q - 1) = 16 × 10 = 160을 계산한다.

    ④ ∮(N) = 160보다 작으면서 ∮(N)과 서로소인 수 e를 선택한다. 여기서 e = 7을 선택한다.

    ⑤ d < 160이면서 de mod 160 = 1인 수 d를 결정한다. 여기에 적합한 수는 d = 23이다. 왜냐면 23 × 7 = 161 = 1 × 160 + 1이기 때문이다.

    ⑥ 결과로 얻어지는 공개키 PU = {7, 187}이고, 개인키는 PR = {23, 187}이다.

 

3) RSA에 대한 공격

   (A) 수학적 공격(소인수분해 공격)

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

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

      ③ 현실적인 시간 내에 소인수분해를 마칠 수 있는 효율적인 소인수분해 알고리즘*이 개발되지 않는 한 RSA는 안전하다고 말할 수 있는 것이다.

 

* 소인수분해 알고리즘 (Factoring Attack)

  - 공격의 목표는 RSA 알고리즘. 공개키와 개인키를 생성하기 위한 알고리즘에 사용되는 숫자들의 인수분해를 풀어냄으로써 키를 찾는 시도를 한다.

 

   (B) 타이밍 공격(시간 공격)

      ① 복호화 알고리즘의 실행 시간에 따라 달라진다. (선택-암호문 공격)

      ② 다양한 방법을 통해 소요되는 시간이 드러나지 않게 막아 키 길이를 추측하는 공격을 막을 수 있다. 예를 들면, 랜덤 지체(random delay)라는 방법을 이용하여 타이밍 공격을 막는다.

 

   (C) 선택 암호문 공격(CCA, Chosen Ciphertext Attack)과 OAEP

      ① 선택 암호문 공격이라는 것은 「임의의 데이터를 송신하면 그것을 암호문으로 간주하고 회신해주는 서비스」를 공격자가 이용할 수 있다는 것을 가정한 공격이다. 이 서비스를 복호 오라클이라고 한다.

      ② 네트워크에서 통신하는 서버는 송신한 데이터에 형식이 갖추어지지 않으면 「데이터 오류」라는 오류 메시지를 통신 상대방에 반송하는 경우가 종종 있다. 이와 같은 친절을 공격자가 노리는 것이다.

      ③ 공격자는 자신이 만든 위조 암호문을 서버에 여러 차례 보내고, 서버가 회신해주는 오류 메시지나 타이밍을 해석해서 키나 평문 정보를 조금이라도 얻으려고 하는 것이다. 이 경우 서버가 복호 오라클과 유사한 움직임을 하게 되어버리는 것이다.

      ④ 정교한 선택 암호문 공격을 막기 위해 RSA Security사에서는 최적 비대칭 암호화 패딩(OAEP)라고 하는 프로시저를 사용해 평문을 수정할 것을 권장하고 있다.

 

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

 

 5) 권장사항

    ① 다음과 같은 권장 사항은 이론적이거나 실험적인 결과에 근거하여 만들어진 것이다.

         ■ n의 비트수는 적어도 1024비트가 되어야 한다. 즉, n은 2¹⁰²⁴ 근방에 있는 수거나 309자리 이상의 십진수가 되어야 한다.

         ■ 두 개의 소수 p와 q는 적어도 512비트가 되어야 한다. 즉, p와 q는 2⁵¹² 근방에 있는 수거나 154자리 이상의 십진수가 되어야 한다.

         ■ p와 q는 같지 않고 거의 같은 크기의 소수이어야 한다.

         ■ p-1과 q-1은 커다란 소인수를 각각 가져야 한다.

         ■ p-1과 q-1의 최대 공약수는 작은 수여야 한다.

         ■ 메시지는 OAEP를 사용해서 패딩 되어야 한다.

 

(4) Rabin 암호 시스템

 

 1) 개요

    ① Rabin 암호시스템은 M. Rabin이 고안한 것으로서 RSA 암호 시스템의 변형이다. RSA가 지수합동에 근거하고 있고, Rabin은 2차 합동에 근거를 두고 있다.

 

중요 체크!

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

 - Rabin 방식은 소인수분해가 곤란하다는 것을 이용한다.

 

(5) ElGamal 방식

 

 1) 개요

    ① RSA와 Rabin 이외에 또 다른 공개키 암호 시스템으로 ElGamal이 있는데 이것은 발명자의 이름인 Taher ElGamal을 따서 지은 것이다.

    ② ElGamal은 이산대수 문제*에 근거해서 만든 시스템이다.(오픈소스를 기초로 하여 키분배 방식 및 공개키 암호 방식을 실현)

    ③ ElGamal은 디지털 서명, 암호화, 키 교환에 사용될 수 있는 공개키 알고리즘이다. ElGamal은 실제로 Diffie-Hellman 알고리즘의 확장이다.

    ④ ElGamal의 주요한 결점은 성능이다. 다른 알고리즘과 비교할 때 가장 느리다.

* 이산대수 문제

 - 이산대수를 구하는 고속 알고리즘은 아직 발견되지 않았다. 이산 대수는 키 교환 프로토콜의 하나인 Diffie-Hellman 키 교환이나 공개키 알고리즘의 하나인 Elgamal 방식에서 사용하고 있다.

 

 2) 특징

    ① ElGamal 암호계에서는 암호문 전달 과정에서 알 수 있듯이 평문이 암호문으로 될 때 순서쌍으로 표현되므로 이 암호계에서 암호문의 길이는 평문의 약 2배가 된다.

    ② 즉, RSA 암호와 비교하여 그만큼 많은 메모리 공간이 필요하며 전송 속도 또한 지체되는 단점을 가지고 있다. 최근 이산대수 문제에 대한 연구가 발전됨에 따라 소수 p의 크기는 768비트 이상의 수를 사용하도록 권고하고 있다.

 

 3) 응용

    ① ElGamal은 RSA를 활용할 수 있는 곳에는 어디에나 사용할 수 있다. 키 교환, 인증, 짧은 메시지의 암호화와 복호화에 사용할 수 있다.

    ② 암호 소프트 웨어 GnuPG에 구현되어 있다.

 

(6) 타원 곡선 암호 (ECC, Elliptic Curve Cryptosystem)

 

 1) 개요

    ① 1985년 코블리치와 밀러가 RSA 암호방식에 대한 대안으로 처음 제안하였다.

    ② 1985년에 도입된 타원곡선 암호(ECC)는 공개키 기반 암·복호화 방법을 혁신했다. ECC는 RSA나 고전적 디피-헬먼 같은 다른 대안들보다 훨씬 강력하고 효율적이다. (키가 256비트인 ECC는 키가 4096비트인 RSA보다 강하다) 그러나 더 복잡하다.

    ③ 타원곡선을 이용하면 암호화, 서명, 키 합의 같은 일반적인 공개키 암·복호화 연산들을 기존 기술들보다 빠르게 수행할 수 있다. 이산대수 문제 (DLP)에 의존하는 대부분의 암·복호화 응용들은 DLP의 타원곡선 버전인 ECDLP(타원곡선 이산대수 문제*)에 기초해서 잘 작동한다.

 

* 타원 곡선상의 이산 대수 문제

⊙ 주어진 것

  - 타원 곡선 E

  - 타원 곡선 E 상의 점 G (베이스 포인트)

  - 타원 곡선 E 상의 점 xG(G를 x배 한 점)

⊙ 구해야 할 것

  - 수 x

 

 2) 특징

    ① 다양한 암호 방식 설계가 용이하며, H/W와 S/W로 구현하기가 용이하다. 이런 장점 때문에 스마트카드나 무선 통신 단말기 등과 같이 메모리와 처리 능력이 제한된 응용 분야에 특히 효율적이다.

    ② 타원 곡선 암호는 유한체상에서 E : y² = x³ + ax + b의 형태로 정의되는 타원 곡선상의 점들 간의 덧셈 연산을 통해 키를 산출한다. 그리고 ECC는 유한체 연산을 포함하고 있어 H/W와 S/W로 구현하기가 용이하고 서로 다른 타원곡선을 선택하여 사용할 수 있어 보안을 위해 타원곡선을 주기적으로 바꾸는 것이 가능하다.

    ③ 이에 따라 각종 국제 표준에서 표준화가 활발히 진행되고 있고, 실제로 다양한 보안응용에서도 타원 곡선 암호를 속속 지원하고 있다.

 

* ECC와 RSA 방식의 비교

항목	ECC방식	RSA방식
기반 구조	WPKI(무선)	PKI(유선)
속도	우수	느림
키 크기	상대적으로 작은 키	ECC에 비해 큰 키
적용	소형 Mobile 환경	인프라가 다소 구현된 환경

 3) 타원 곡선 그래프

 

 4) ECDLP 문제

 

(6) 대칭키 방식과 비대칭키 방식의 비교

 

 1) 개요

    ① 대칭키 암호 시스템과 비대칭키 암호 시스템은 병존하게 될 것이며 보안 서비스 분야에서 각각의 역할을 하게 될 것이다. 사실 이 두 시스템은 서로 보완적이다. 한 시스템의 장점이 다른 한 시스템의 단점을 보완하고 있다.

    ② 대칭키 암호 시스템이 기호(문자나 비트)를 대체하거나 전치하는데 기반을 두고 있는 반면에 비대칭키 암호 시스템은 숫자를 이용한 수학적 함수를 응용하는데 기반을 두고 있다.

 

 2) 대칭키 방식과 비대칭키 방식의 비교

항목	대칭키	공개키
키의 상호 관계	암호화키 = 복호화키	암호화키 ≠ 복호화키
인전한 키길이	128비트 이상	2048비트 이상
암호화 키	비밀	공개
복호화 키	비밀	비밀
비밀키 전송	필요	불필요
키 개수	N(N-1)/2	2N
암호화 속도	고속	저속
경제성	높다	낮다
제공 서비스	기밀성	기밀성, 부인방지, 인증
목적	데이터(파일) 암호화	대칭키 교환
전자서명	복잡	간단
단점	키 교환 원리가 없다	중간자 공격에 취약
해당 알고리즘	DES, 3DES, AES, IDEA	RSA, ECC, DSA