[암호학 기본 04] DLP-based Public-Key Cryptography

이산 로그 문제 (DLP)

암호학의 출발점은 이산 로그 문제(Discrete Logarithm Problem, DLP)라는 수학적 난제이다. 이 문제가 어렵기 때문에 이후의 모든 암호 시스템이 안전할 수 있다.

문제 정의: 순환군 G에서 g와 a가 주어졌을 때, $g^x \equiv a \pmod{p}$를 만족하는 x를 찾는 것은 매우 어렵다.

• 쉬운 방향: g, x, p를 알면 a를 계산하는 것은 쉽다. (지수 연산)
• 어려운 방향: g, a, p를 알면 x를 찾는 것은 매우 어렵다. (이산 로그)
  이는 값을 알았을 때 계산을 하는 것은 쉽지만, 결과를 통해서 어떤 값들을 사용했는지는 알기 힘들다

난이도의 이유: p가 매우 큰 소수일 때, $g^x$의 값들이 예측 불가능한 순서로 나타나기 때문에, x와 a 사이에 규칙적인 관계를 찾을 수 없다.(현재 가장 빠른 알고리즘으로도 해결하는 데 천문학적인 시간이 걸린다.)

Diffie-Hellman 키 교환 (Diffie-Hellman key exchange)

Secure한 channel이 아닌 public한 환경에서 두 사용자가 동일한 비밀키를 공유할 수 있도록 하는 최초의 공개키 암호 시스템이다. Diffie-Hellman 키 교환은 DLP의 어려움을 활용하여 공개키를 교환하고, 이를 통해 비밀키를 생성한다.

1. group 생성 알고리즘 g를 이용해서 순환군 $G$, prime order q, generator g를 생성한다. 그리고 $Z_q$에서 임의의 원소 x를 뽑고, $g^x$ 를 통해 h1을 생성한다.
2. $G, q, g, h_1$을 보낸다.
3. 수신자는 $Z_q$에서 임의의 원소 y를 뽑고, $g^y$ 를 계산해서 $h_2$를 구한다.
4. 그 후, 송신자에게 $h_2$값을 보낸다.
5. 이렇게 되면 두 당사자들은 $(h_2)^x$ , $(h_1)^y$ 를 통해서 $g^{xy}$ 라는 동일한 키를 공유하게 된다.

여기서 위의 그림에서는 $G,q,g$를 그룹 생성 알고리즘에 의해 생성하고 있지만, 실제로는 $G, q, g$와 같은 그룹 매개변수는 통신 시스템 전체의 기반이 되는 공개 값으로, 한 번 설정되면 매 키 교환 세션마다 새롭게 생성할 필요 없이 재사용될 수 있으며, 이는 보안에 영향을 주지 않는다.

도청자는 공개된 $g,g^x,g^y$값을 알지만, DLP의 어려움 때문에 x나 y를 계산할 수 없다. 따라서 공통 비밀키인 $g^{xy}$를 알아내는 것이 불가능하다. 이 문제를 Diffie-Hellman 문제라고 하며, DLP를 해결할 수 있다면 Diffie-Hellman 문제도 풀 수 있다.

El Gamal 암호화

Diffie-Hellman 키 교환을 기반으로 하는 공개키 암호화 스킴을 El Gamal 암호화라고 한다.

키 생성 및 공개키 공유
A (수신자) 측:
먼저 $G,q,g$라는 공개 매개변수를 설정한다. 여기서 G는 순환군, q는 G의 위수(order), g는 생성자(generator)이다.

A는 임의의 개인키 $x$를 선택한다. A는 공개키 $h_1=g^x$를 계산하고, $G,q,g,h_1$을 송신자B에게 전달한다.

메시지 암호화
B (송신자) 측:
B는 A의 공개키 $h_1$을 사용해 암호화를 진행한다.B는 임의의 난수 $y$를 선택한다. B는 $h_2=g^y$와 $k=(h_1)^y$를 계산한다. 여기서 k는 일회성 암호화 키이다.

B는 평문 m에 이 일회성 키 k를 곱해 암호문 $c_2=k⋅m$을 만든다.B는 암호문 쌍인 $h_2와c2$를 A에게 전송한다

메시지 복호화
A (수신자) 측:
A는 B가 보낸 $h_2$와 $c_2$를 받는다.

A는 자신의 개인키 x를 사용해 일회성 암호화 키 k를 계산한다:
$k=(h_2)^x=(g^y)^x=g^{xy}$
이 k는 B가 계산한 $k = (h_1)^y = (g^x)^y = g^{xy}$와 동일하다.
마지막으로, A는 $c_2$를 k로 나누어 평문 $m=c_2/k$를 복원한다.

보안 문제
A가 만약 랜덤값 r을 중복으로 사용하여 메세지를 암호화 하였을 때 생기는 경우이다.

만약 메세지 중 하나가 유출된다면 다른 메세지를 복호화 할 수 있기 때문에 랜덤 키 재사용을 권장하진 않는다.

Reference

1. The Discrete Logarithm Problem, KEVIN S. McCURLEY, Proceedings of the Symposia in Applied Mathematics, vol. 42, 1990, pp. 49-74.
2. New Directions in Cryptography, Whitfield Diffie and Martin E. Hellman, IEEE Transactions on Information Theory, Vol. IT-22, No. 6, 1976, pp. 644-655.
3. A PUBLIC KEY CRYPTOSYSTEM AND A SIGNATURE SCHEME BASED ON DISCRETE LOGARITHMS, Taher ElGamal, IEEE Transactions on Information Theory, Vol. 31, No. 4, 1985, pp. 469-472.