ElGamal Encryption (엘가말 암호화의 핵심)

이 필기는 Elgamal Encryption(엘가말 암호화)의 작동 원리와 그것이 본질적으로 Diffie-Hellman(D-H) 키 교환과 얼마나 똑같은지를 증명하는 아주 중요한 내용입니다.

"Very similar to D-H, but w/ reordering of steps."
(Elgamal은 D-H와 매우 비슷하지만, 순서만 살짝 바꾼 것이다.)
엘가말 암호화는 기본적으로 Diffie-Hellman Key Exchange의 순서를 재배치(Reordering)하고 암호화 과정을 추가한 형태입니다.

가장 중요한 장점 (Probabilistic Encryption):
동일한 평문(Plaintext)을 암호화하더라도, 매번 난수 $i$를 다르게 선택하면 생성되는 Ephemeral Key가 달라집니다. 결과적으로 암호문(Ciphertext)이 매번 다르게 생성되는 확률적 암호화(Probabilistic Encryption)가 가능해집니다. 이는 블록 암호의 ECB 모드가 가진 취약점을 극복하고 OFB 모드처럼 패턴을 숨겨주는 강력한 이점입니다.

[상단: 원래의 Diffie-Hellman + 암호화 과정]
보통은 D-H로 공통 키($K_{AB}$)를 만든 다음, 그 키를 이용해 AES 같은 대칭키 알고리즘으로 메시지 $x$를 암호화($y = AES_{K_{AB}}(x)$)합니다.
하지만 교수님이 노란색 형광펜으로 칠하신 Encryption 부분을 보면, AES를 안 쓰고 그냥 메시지 $x$에 생성된 키 $K_{AB}$를 곱해버립니다.

• 암호화: $y = K_{AB} \cdot x \bmod p$
• 복호화: $x = y \cdot K_{AB}^{-1} \bmod p$ (키의 모듈러 역원을 곱해서 복구)

[하단: Elgamal 암호화 프로토콜 (D-H의 변형)]
이 과정을 통신 프로토콜로 깔끔하게 정리한 것이 Elgamal입니다.

• Ephemeral Key ($K_E$): 앨리스가 고른 일회용 난수 $i$를 이용해 만든 일회용 키. ($K_E = \alpha^i \bmod p$)
• Masking Key ($K_M$): 밥의 공개키 $\beta$와 난수 $i$를 결합해 만든 실제 암호화/복호화용 키. ($K_M = \beta^i \bmod p$)

1. Bob의 준비 (Key Generation): Bob이 개인키 $d$를 고르고, 공개키 $\beta = \alpha^d \bmod p$를 만들어 Alice에게 줍니다. (D-H에서 Bob이 $B$를 보내는 것과 똑같습니다.)

2. Alice의 암호화 준비 (Encryption):

• Alice는 일회용 개인키 $i$를 고르고, Ephemeral key (일회용 공개키) $K_E = \alpha^i \bmod p$를 만듭니다. (D-H에서 Alice가 $A$를 만드는 것과 똑같습니다.)
• Bob이 준 $\beta$를 이용해 Masking key $K_M = \beta^i \bmod p$를 만듭니다. (이것이 바로 공통 키 $K_{AB}$입니다!)

3. 암호문 전송: Alice는 메시지 $x$에 마스킹 키를 곱해 암호문 $y = x \cdot K_M \bmod p$를 만듭니다. 그리고 Bob에게 암호문 $y$와 일회용 키 $K_E$를 함께 보냅니다. (총 2개를 보냅니다.)

Proof of Correctness (증명)

[Bob의 복호화 과정]
Bob은 Alice에게서 $(y, K_E)$를 받았습니다.
Bob은 자신의 개인키 $d$를 알고 있습니다.

• Bob은 먼저 $K_E$에 자신의 개인키 $d$를 승수하여 마스킹 키 $K_M$을 스스로 복원해냅니다.
  $K_M = (K_E)^d \bmod p$

• 그런 다음, 암호문 $y$에 이 마스킹 키의 역원($K_M^{-1}$)을 곱해서 평문 $x$를 얻어냅니다.
  $y \cdot K_M^{-1} \equiv x \cdot K_M \cdot [(K_E)^d]^{-1} \pmod p$

[증명 전개]
교수님 필기의 식을 하나씩 풀어보면 다음과 같습니다.

암호문 $y$ 자리에 원래 식($x \cdot \beta^i$)을 대입합니다.
$\equiv x \cdot \beta^i \cdot [(\alpha^i)^d]^{-1} \pmod p$

$\beta$는 Bob의 공개키였으므로 $\alpha^d$로 바꿔 씁니다.
$\equiv x \cdot (\alpha^d)^i \cdot (\alpha^{i \cdot d})^{-1} \pmod p$

지수 법칙에 의해 앞의 항은 $\alpha^{d \cdot i}$가 됩니다.
$\equiv x \cdot \alpha^{d \cdot i} \cdot (\alpha^{i \cdot d})^{-1} \pmod p$

노란색 형광펜으로 칠해진 부분인 $\alpha^{d \cdot i}$와 $(\alpha^{i \cdot d})^{-1}$은 서로 역원 관계이므로 곱하면 $1$이 되어 완벽하게 상쇄됩니다.$\equiv x \pmod p$

확률적 암호화 (Probabilistic Encryption = NonDeterministic)

결정론적 암호화 (Deterministic) vs 확률론적 암호화 (Probabilistic)

교수님이 가장 강조하시는 엘가말의 핵심 특징입니다. 하단에 빨간펜으로 쓰인 Probabilistic Encryption(확률론적 암호화)이라는 단어는 무조건 외우셔야 합니다.

• 문제 제기: RSA나 초기 설정이 없는 일반 AES의 경우, 똑같은 평문($x_1$)을 암호화하면 항상 똑같은 암호문($y_1$)이 나옵니다 (Deterministic). 해커가 암호문을 보고 "어? 아까 본 패턴이랑 똑같네?" 하고 평문을 유추할 위험이 있습니다.

• 엘가말의 해결책: 엘가말은 암호화할 때마다 송신자(Alice)가 무작위 난수 $i$ 를 새로 뽑습니다.

• 결론 ($y_1 \neq y_2$): 똑같은 메시지($x_1 = x_2$)를 두 번 연속으로 보내더라도, 곱해지는 일회용 키($K_E$)와 마스킹 키($K_M$)가 매번 달라지기 때문에 완전히 다른 암호문($y_1 \neq y_2$)이 생성됩니다. * 비교: 교수님은 이것이 마치 블록 암호의 OFB mode에서 매번 다른 IV(초기화 벡터)를 써서 패턴을 숨기는 것과 완벽히 같은 원리라고 설명하신 겁니다. (아까 우리가 정리했던 OFB 모드의 장점이 여기서 그대로 쓰이네요!)

연산 측면 (Computational Aspects)

그렇다면 1024 bits가 넘는 어마어마한 숫자들을 어떻게 매번 거듭제곱($\alpha^i, \beta^i$)해서 키를 만들어낼까요?

• S-A-M Alg (Square-and-Multiply Algorithm):아무리 지수가 커도 제곱과 곱하기만 반복하면 매우 빠르게 값을 구할 수 있습니다.

• 하드웨어 최적화: 실제로 나중에 실무에서 암호화 가속기나 컨트롤러를 설계하실 때, 이런 모듈러 거듭제곱 연산들은 S-A-M 알고리즘을 활용해 하드웨어 로직(게이트) 단에서 병렬 처리하도록 최적화합니다. 수학적으로는 복잡해 보여도 회로상으로는 매우 효율적으로 돌아가도록 설계할 수 있습니다.

• 우측 상단 수식: $2^3 \cdot 2^{-1} \equiv 2^2 \pmod{11}$ 부분은, 방금 전 우리가 보았던 복호화 증명 과정에서 역원을 곱해 지수를 상쇄시키는 원리가 실제 숫자를 넣었을 때도 똑같이 작동한다는 것을 보여주는 간단한 예시일 뿐입니다.

복호화의 마법 (Fermat's Little Theorem)

Bob이 복호화($x = y \cdot K_M^{-1}$)를 하려면 마스킹 키의 모듈러 역원인 $K_M^{-1}$을 구해야 합니다. 원래 역원을 구하려면 복잡한 EEA (Extended Euclidean Algorithm, 확장 유클리드 호제법)를 써야 하는데, 교수님은 페르마의 소정리(Fermat's Little Theorem)를 이용해 연산을 획기적으로 최적화합니다.

• Fermat's Little Theorem: $a^{p-1} \equiv 1 \pmod p$ (소수 $p$에 대해, 어떤 수의 $p-1$ 승은 무조건 $1$이 됩니다.)

• 증명 과정:
  $K_M^{-1} \equiv (K_E^d)^{-1} \cdot 1 \pmod p$ (여기에 1을 곱해도 값은 같습니다.)
  여기서 $1$ 대신 페르마 소정리 공식인 $K_E^{p-1}$을 대입합니다.
  $\equiv (K_E)^{-d} \cdot K_E^{p-1} \pmod p$
  $\equiv \mathbf{K_E^{p-d-1} \pmod p}$

• 결론 (왜 이 짓을 했는가?): 역원($^{-1}$)을 구하는 어려운 수식이, 단순한 거듭제곱($p-d-1$ 승) 수식으로 바뀌었습니다! 즉, 복잡한 EEA 알고리즘을 짤 필요 없이 우리가 앞서 배운 S-A-M (Square-and-Multiply) 알고리즘 하나만 재활용하면 복호화까지 초고속으로 끝낼 수 있다는 뜻입니다. (하드웨어 구현 관점에서 엄청난 이점입니다.)

기본 공격 (Passive Attacker)

네트워크를 도청만 하는 해커(Trudy)가 엘가말을 깨려고 시도하는 내용입니다.

• Trudy가 암호를 풀려면 Bob의 개인키 $d$나 Alice의 일회용 키 $i$를 알아내야 합니다.
• 하지만 식을 보면 $d = \log_\alpha \beta$ 이고 $i = \log_\alpha K_E$ 입니다.
• 즉, 해커는 또다시 DLP (Discrete Logarithm Problem)라는 수학적 통곡의 벽을 마주하게 됩니다. 소수 $P$가 $2^{1024}$ 이상으로 충분히 크다면 이 공격은 절대 불가능합니다.

치명적인 실수 (일회용 키 재사용 공격) ★기말 단골 문제★

앞서 엘가말은 매번 난수 $i$를 뽑아 일회용 키($K_E$)를 만들기 때문에 안전하다고(Probabilistic Encryption) 했습니다. 그런데 만약 개발자가 귀찮아서 $i$ 값을 재사용한다면?

• 상황: 난수 $i$를 재사용하면, $K_E$가 똑같이 만들어지고, 결과적으로 마스킹 키 $K_M$도 동일하게 고정됩니다.

• Known Plaintext Attack (알려진 평문 공격):
  해커가 수많은 암호문($y_1, y_2 \dots$)을 가로채던 중, 우연히 첫 번째 암호문 $y_1$의 원본 평문이 $x_1$이라는 사실을 하나 알아냈다고 가정합시다. (예: 이메일 헤더 등 뻔한 데이터)

• 해커의 계산:해커는 $y_1 = x_1 \cdot K_M$ 이라는 식을 이용해, $K_M = y_1 \cdot x_1^{-1}$ 을 계산하여 비밀 마스킹 키 $K_M$을 통째로 알아내 버립니다.

• 결과:이제 해커는 다른 모든 암호문($y_2$)에 알아낸 키의 역원($K_M^{-1}$)을 곱해서 모든 평문($x_2, x_3 \dots$)을 다 뚫어버릴 수 있습니다. ($x_2 = y_2 \cdot y_1^{-1} \cdot x_1 \pmod p$)

핵심 키워드: "Elgamal에서 Ephemeral key $i$를 재사용하면 Known Plaintext Attack에 의해 시스템이 완전히 붕괴된다." (이건 우리가 앞서 OFB 모드에서 IV를 재사용했을 때 벌어진 Two-Time Pad 공격과 본질적으로 완벽히 똑같은 치명타입니다!)