기말범위: Review of DLP

1. DLP의 정의와 Diffie-Hellman의 기초

Review of DLP (Discrete Logarithm Problem):

• Primitive element $\alpha$와 소수 $p$, 그리고 결과값 $\beta$가 주어졌을 때, 지수인 $x$를 찾아내는 문제입니다. ($a^x \equiv \beta \pmod p$)

• 필기 속 예시($p=47$)처럼 숫자가 작으면 하나씩 다 대입해 보는 Brute-force 방식으로 $x=15$를 찾을 수 있습니다. 하지만 숫자가 커지면 이 방식은 불가능해집니다. $x$가 $15$인 이유는, $5$를 거듭제곱하다가 최초로 나머지가 $41$이 나오는 지수(횟수)가 바로 $15$번이기 때문입니다.

Diffie-Hellman Key Exchange:

• Alice와 Bob이 공통의 비밀 키($K_{AB}$)를 만드는 과정입니다.
• 각자 자신만의 Private Key($a, b$)를 마음속으로 고릅니다.
• 이를 이용해 $\alpha^a \bmod p$, $\alpha^b \bmod p$를 계산하여 Public Key($A, B$)를 만들어 서로 교환합니다.
• 중간에 있는 해커 Trudy는 오직 듣기만 하는 Passive Attacker입니다. 즉, 네트워크에서 $A$와 $B$가 오가는 것은 훔쳐볼 수 있지만, 값을 변조하거나 가로챌 수는 없습니다.

2. Trudy의 한계와 시스템의 안전성 증명

DHP (Diffie-Hellman Problem):

• 해커 Trudy는 네트워크를 통해 $\alpha, p, A, B$를 모두 훔쳐내서 알고 있습니다. 그녀의 목표는 이 공개된 정보들만 가지고 둘만의 비밀 키인 $K_{AB} = \alpha^{ab} \bmod p$를 알아내는 것입니다. 이것이 바로 DHP입니다.

DHP를 푸는 유일한 방법 = DLP 풀기:

• Trudy가 DHP를 풀려면(즉, $K_{AB}$를 계산하려면), 먼저 Alice의 Private Key인 $a$를 알아내야 합니다 (필기의 Step 1).
• $A = \alpha^a \bmod p$라는 식에서 $a$를 찾아내는 역산 과정이 바로 앞서 말한 DLP입니다.

결론 (Computational Hardness):

• 만약 소수 $p$가 충분히 크다면 (필기처럼 $1024$ bits 이상), Step 1인 DLP를 푸는 것은 컴퓨터 연산 능력상 절대 불가능(Computationally very hard)합니다.
• 따라서 DHP를 깨는 유일한 방법이 DLP를 푸는 것뿐이므로, 이 암호 체계는 안전하다(Secure)고 결론 내리는 것입니다.

General DLP

1. NOT proven YET (이론과 현실의 차이)

맨 위 필기는 암호학의 근본적인 맹점을 꼬집고 있습니다.

RSA와 Factoring: RSA가 안전한 이유는 소인수분해(Factoring)가 어렵기 때문입니다. 하지만 "RSA를 깨려면 무조건 소인수분해를 해야만 한다"라고 수학적으로 완벽히 증명된 적은 없습니다. 단지 현재 인류가 아는 가장 좋은 공격 방법(The best way we know BY NOW)이 소인수분해일 뿐입니다.

DHP와 DLP: 방금 전 필기에서 본 내용도 마찬가지입니다. "DHP를 깨려면 무조건 DLP를 풀어야만 한다"는 아직 증명되지 않았습니다. (하지만 현실적으로는 그렇다고 믿고 암호를 만듭니다.)

2. Generalized DLP (GDLP)

이제 DLP를 단순히 "숫자 곱하기"에서 벗어나, 수학적인 그룹(Cyclic group) 전체로 일반화(Generalized)합니다.생성자(Primitive element, $\alpha$)를 $x$번 반복 연산($\circ$)해서 $\beta$를 만드는 과정입니다. 어떤 연산을 쓰느냐에 따라 공식이 바뀝니다.

• 연산이 곱셈(MULT)일 때: $\beta = \alpha^x$ (우리가 아는 기본 DLP)
• 연산이 덧셈(ADD)일 때: $\beta = x \cdot \alpha$ ($\alpha$를 $x$번 더함)

이 덧셈(ADD) 기반의 GDLP가 바로 다음에 배울 타원 곡선 암호의 핵심 원리가 됩니다.

3. Which cyclic groups make good DLP? (기말고사 출제 포인트)

DLP를 기반으로 안전한 암호를 만들 수 있는 수학적 그룹 4가지입니다. 교수님이 빨간색으로 V 체크하신 1번과 3번의 차이를 비교하는 문제가 단골로 출제됩니다.

• $\mathbb{Z}_p^*$ (Multiplicative group of a prime field): 지금까지 배운 기본 체계입니다. 충분히 안전하려면 소수 $p$의 크기가 최소 1024 bits 이상이어야 합니다. 연산이 무겁고 키가 깁니다.
• $GF(2^m)$ (Extension field): 하드웨어 구현이 효율적인 갈루아 필드입니다.
• Elliptic Curves (타원 곡선): ★기말고사 무조건 출제★그래프 형태의 "곡선 위의 점(Points on the curve)"들을 덧셈(ADD) 연산하여 암호를 만듭니다. 이 방식의 가장 무서운 점은 키 길이가 160 bits만 되어도 1024 bits짜리 1번 체계와 동일한 보안 레벨을 제공한다는 것입니다. 키가 작으니 계산이 빠르고 메모리를 적게 먹어 현대 암호학의 표준입니다.
• Hyperelliptic curves: 타원 곡선의 심화 버전입니다.

안전성의 기준과 Square-Root Attack

• 기본 전제:
  현대 암호학에서 "안전하다"라고 말하려면, 해커가 암호를 깨기 위해 최소 $2^{80}$ 번의 연산(steps)을 해야만 합니다. (이 정도면 슈퍼컴퓨터로도 풀기 불가능한 횟수입니다.)

• Brute-force Attack (무차별 대입):하나씩 다 대입해 보는 방법입니다. 그룹의 크기가 $n$일 때, 최대 $n$번($O(n)$) 계산해야 합니다. 만약 세상에 이 공격법만 존재한다면, 그룹 크기 $n$을 $2^{80}$ 정도로만 만들어도 충분히 안전할 것입니다.

• Square-Root Attack (치명적인 범용 공격):하지만 수학자들이 Pollard's rho method 같은 '제곱근 공격법'을 찾아냈습니다. 이 공격을 쓰면 그룹 크기 $n$을 다 계산할 필요 없이, $\sqrt{n}$ 번만 계산해도 암호가 깨져버립니다.

  • 문제 발생: $n$을 $2^{80}$으로 만들면, 해커는 $\sqrt{2^{80}} = 2^{40}$ 번만 계산하면 암호를 깰 수 있습니다. ($2^{40}$은 요즘 컴퓨터로 금방 뚫립니다.)

  • 해결책: 해커가 $\sqrt{n}$ 번 계산했을 때 그 횟수가 $2^{80}$이 되게 하려면, 애초에 그룹 크기 $n$을 $2^{160}$으로 키워야 합니다. ($\sqrt{2^{160}} = 2^{80}$)

  • 결론: 이것이 바로 타원 곡선 암호(Elliptic Curves)에서 키 길이가 160 bits가 되어야 하는 수학적 이유입니다. (타원 곡선에 통하는 가장 강력한 공격이 이 Square-Root Attack이기 때문입니다.)

$\mathbb{Z}_p^*$ 방식이 1024 bits나 필요한 이유

• Index-Calculus Attack (인덱스 칼큘러스 공격):타원 곡선에는 안 통하지만, 우리가 아는 일반적인 모듈러 곱셈 그룹($\mathbb{Z}_p^*$)이나 $GF(2^m)$에는 Square-Root Attack보다 훨씬 더 빠르고 강력한 이 공격이 통합니다.
• 결론:이 무시무시한 공격을 버텨내고 최소 $2^{80}$ 번의 연산 복잡도를 강제하려면, 숫자의 크기($p$)를 160 bits 따위가 아니라 무려 1024 bits (혹은 2048 bits) 이상으로 엄청나게 키워야만 합니다.

Application of DLP (암호 알고리즘 총정리 표)

Key exchange (키 교환): 디피-헬먼 가문입니다.

• 일반 모듈러: D-H
• 타원 곡선: ECDH (Elliptic Curve Diffie-Hellman)

Digital signature (디지털 서명): 인증을 위한 알고리즘입니다.

• 일반 모듈러: DSA, Elgamal
• 타원 곡선: ECDSA (비트코인 등에서 쓰는 현대 표준 서명 방식입니다.)

Encryption (암호화): 데이터를 숨기는 알고리즘입니다.

• 일반 모듈러: Elgamal
• 타원 곡선: EC-Elgamal

RSA의 위엄: 표를 보면 RSA는 키 교환, 서명, 암호화 세 가지 기능(V 체크)을 모두 혼자서 다 할 수 있는 만능 알고리즘임을 알 수 있습니다.

---