# DLP-based Public-Key Cryptography
{% hint style="warning" %}
**목표 : 이산 로그 문제(Discrete Log Problem, DLP)가 무엇이고 왜 어렵다고 말하는지 이해한다.**\
**DLP 위에서 동작하는 대표 프로토콜인 Diffie–Hellman 키 교환과 ElGamal 암호의 흐름을 익힌다.**
{% endhint %}
많은 zkp 프로토콜들은 $$g^x = h$$에서 $$h$$를 알 때 $$x$$를 알아내기 어렵다는 **이산로그 문제(DLP)**의 어려움에 의존한다. 이 글에서는 DLP 자체와, 그 위에서 동작하는 Diffie-Hellman 키 교환과 ElGamal 암호를 살펴보고, 이후 zkp에서 반복해서 등장하는 **지수 연산 구조와 난이도 가정**에 대한 직관을 쌓는다.
## DLP-based Public-Key Cryptography
### Discrete Log Problem (DLP)
많은 암호 시스템들은 이산 로그 문제 (DLP) 를 기반으로 보안성을 보장하고 있다.
DLP 는 다음과 같이 정의할 수 있다.
$$\begin {aligned} &\text {Given group G is cyclic, with G } = \langle g \rangle \text { and } a \in G \ \ & g^x \equiv a \ (mod \ p) \quad \text {It is easy to find “a” given (g, x, p)} \ \ & ind\_ga \equiv x \ (mod;p) \quad \text{But it is hard to find “x” given (g, a, p)} \end {aligned}$$
$$g$$가 그룹의 원시근이고 그룹 원소$$a$$에 대해 $$g^x \equiv a \ (mod \ p)$$ 에서 $$g, x, p$$가 주어졌을 때 $$a$$를 구하는것은 쉽지만 $$g, a, p$$가 주어지고 이를 만족하는 $$x$$를 찾기 어렵다는 문제이다.\
\
$$x$$를 구하기 위해 로그의 형태를 씌워서 $$ind\_ga \equiv x \ (mod ;p)$$ 의 형태로 만들어지기 때문에 이산 로그 문제라고 불린다.
왜 이 문제를 풀기 어렵나고 하면 먼저, 원시근의 성질로 그룹안에 있는 원소들은 합동이 아니다.
즉 $$g^0, g^1, \dots, g^{p - 2} ; mod ; p$$ 의 값은 모두 다른값이 나온다.\
따라서 $$g^x$$의 값인 $$a$$는 그룹안에 하나만 존재한다.\
또한 $$a < b, ; g^a \nless g^b ;(mod ;p)$$ $$a, b$$의 대소가 있어도 $$g^a, g^b$$의 대소가 달라져 결과 값에 규칙이 없는 상태이다. \
그러기 때문에 $$p$$의 값이 커지면 $$g^x \equiv a$$ 를 만족하는 $$x$$를 구하기 위해 모든 경우를 대입해봐야 한다.
$$p$$ 에 2048bit 소수를 사용하면 대입할 수 있는 경우의 수가 $$2^{2048}$$ 이다.\
현재 가장 빠른 알고리즘인 Pohlig-Hellman algorithm을 사용해도 시간 복잡도가 $$O(\sqrt n)$$ 이기 때문에 $$10^{300}$$ 정도의 연산이 진행된다.
따라서 DLP가 풀기 어렵다고 하는 이유는, 암호에서 사용하는 $$p$$가 매우 큰 소수일 때 가능한 지수 $$x$$ 의 경우의 수가 천문학적으로 많아지지만, 현재로서는 이를 빠르게 줄여 주는 알고리즘이 알려져 있지 않기 때문이다.
### Diffie-Hellman(DH) 키 교환
대칭키 암호(AES 등)를 쓰려면 양쪽이 **같은 비밀키**를 알고 있어야 한다.\
과거에는 이 키를 직접 만나서 종이에 적어 전달하거나 별도의 안전한 채널을 이용해 공유 해야 했다. \
하지만 이건 인터넷 시대에는 거의 불가능한 방식이다.
Diffie–Hellman(DH) 키 교환은 이런 문제를 해결하기 위해 등장한, 공개 채널 위에서 비밀키를 합의하는 방법이다
DH 키 교환 방법은 공개키를 이용하여 동일한 비밀키를 만든다.
이를 통해 대칭키 암호화 방식의 문제점인 비밀키 교환을 하지 않고 공개키를 교환하여 비밀키를 만든다.
### 암호화 과정
* **공개 파라미터 선택**
* Alice와 Bob은 모두가 알고 있어도 되는 $$(p,g)$$를 공유한다.
* $$p$$: 큰 소수
* $$g$$: $$\mathbb{Z}\_p^\times$$ 의 생성자
* **Alice의 비밀 선택 및 전송**
* Alice는 비밀 값 $$x$$ 를 랜덤하게 선택
* $$A = g^x mod ;p$$ 를 계산하여 Bob에게 전송
* **Bob의 비밀 선택 및 전송**
* Bob은 비밀 값 $$y$$ 를 랜덤하게 선택
* $$B = g^y ;mod ;p$$를 계산하여 Alice에게 전송
* $$y$$는 Bob만 알고 있는 값이다.
* **공유키 계산**
* Alice는 받은 $$B$$로부터
$$K=B^x=(g^y)^x=g^{xy}; mod; p$$
* Bob은 받은 $$A$$ 로부터
$$K = A^y = (g^x)^y = g^{xy} ; mod ; p$$
* 결과적으로 둘 다 동일한 공유키 $$K$$ 를 얻게 된다.
* **대칭키로 사용**
* 이때 얻은 $$K$$를 AES 등의 대칭키로 사용한다.
공격자는 네트워크를 전부 엿볼 수 있다고 가정해도, 볼 수 있는 값은 다음뿐이다.
* 공개 파라미터: $$p, g$$
* Alice가 보낸 값: $$A=g^x$$
* Bob이 보낸 값: $$B = g^y$$
하지만 공격자는 $$x, y$$를 모르기 때문에
$$K=g^{xy}$$
를 계산하기 위해서는
* $$g^x$$ 에서 $$x$$를 찾거나
* $$g^y$$ 에서 $$y$$를 찾아야 한다.
이 두 작업 모두 DLP를 푸는 것과 동일한 수준의 어려움을 갖는다고 믿고 있으며, 적절한 파라미터에서는 현실적으로 불가능하다고 가정한다.
$$\begin {aligned} g^{xy} ;\text {from knowledge of } g, g^x \text{ and } g^y \text { should be intractable.} \end {aligned}$$
위의 문제가 Diffie-Hellman Problem 으로, DLP를 해결 할 수 있다면 Diffie-Hellman Problem을 풀 수 있다.
### ElGamal Encryption
ElGamal 암호는 DH의 아이디어를 이용해 만든 **공개키 암호 시스템이**다.\
핵심 특징은 다음과 같다
* 공개키 암호이지만, 내부 구조는 “한쪽만 키를 고정한 DH”와 비슷
* 안전성은 **DLP/Decisional Diffie–Hellman(DDH) 가정**에 의존
* 랜덤 값 $$r$$ (nonce)을 반드시 매 암호문마다 새로 뽑아야 한다.
### 암호화 과정
송신자 A 가 B 에게 메시지 M 을 보낼 때의 과정이다.
1. 송신자 A 는 랜덤 정수 r 을 선택합니다. (매 암호문마다 새로 뽑음)
2. B의 키 생성: $$Key\_{priv} = x,; Key\_{pub} \equiv g^{x} ; (mod ;p)$$
3. A의 메세지 암호화 (B의 공개키를 이용해서)$$K \equiv (g^x)^r; (mod; p) \quad c\_1 \equiv g^r; (mod; p) \quad c\_2 \equiv K \cdot M; (mod; p)$$
### 복호화 과정
B의 암호문 복호화\
$$c\_1^x \equiv (g^r)^x \equiv K ;(mod; p)$$ K를 구한후 K의 역원을 구해 아래 식 계산을 한다
$$c\_2 \cdot K^{-1}; (mod ;p) \equiv M$$
### 랜덤 값 재사용 문제
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.
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://upsidezkp.gitbook.io/upside-zkp-docs/step-0/prerequisite/dlp-based-public-key-cryptography.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.