Diffie-Hellman(DH) 기반의 암호화 알고리즘 ElGamal 암호화 방식

Diffie-Hellman(DH) 기반의 암호화 알고리즘은 키 교환(key exchange) 방식에서 출발하여, 이후 다양한 방식의 암호화 및 디지털 서명 알고리즘으로 확장되었습니다. 그 중 가장 대표적인 것은 ElGamal 암호화 방식입니다.

---

🔑 Diffie-Hellman 키 교환 (기본 개념)

• 목적: 두 사람이 공유된 비밀 키를 안전하게 생성하는 방법.
• 문제 해결: 통신 전에 키를 미리 공유하지 않아도 안전하게 같은 키를 생성할 수 있음.
• 기반 수학: 이산 로그 문제의 어려움(DLP, Discrete Logarithm Problem).

이 알고리즘 자체는 암호화 기능이 없고, 안전한 키 교환 방식입니다.
이 아이디어를 암호화 기능에 적용한 것이 ElGamal입니다.

---

🔐 ElGamal 암호화 알고리즘

ElGamal 암호화는 1985년 **타헤르 엘가말(Taher ElGamal)**이 제안한 공개 키 암호 시스템으로, Diffie-Hellman 키 교환 원리를 바탕으로 만들어졌습니다.

1. ⚙️ 주요 특징

• 비대칭 키 암호화 방식
• **무작위성(Randomness)**을 사용 → 같은 메시지도 매번 다르게 암호화됨
• 보안성은 이산 로그 문제의 어려움에 기반

---

2. 📌 알고리즘 구성

(1) 키 생성

• 큰 소수 pp, 원시근 gg 선택
• 개인 키 xx는 임의의 수
• 공개 키 y=gxmod  py = g^x \mod p

👉 공개 키: (p,g,y)(p, g, y), 개인 키: xx

---

(2) 암호화

• 메시지를 mm이라고 하자 (보통은 수로 변환)
• 임의의 무작위 수 kk 선택
• c1=gkmod  pc_1 = g^k \mod p
• c2=m⋅ykmod  pc_2 = m \cdot y^k \mod p

👉 암호문은 (c1,c2)(c_1, c_2)

---

(3) 복호화

• 수신자는 개인 키 xx를 이용해 메시지를 복호화:m=c2⋅(c1x)−1mod  pm = c_2 \cdot (c_1^x)^{-1} \mod p여기서 (c1x)−1(c_1^x)^{-1}는 c1xc_1^x의 모듈러 역원

---

3. ✅ 장점과 ❌ 단점

장점 단점

무작위성을 사용 → 안전	암호문 크기가 2배
이산 로그 문제 기반 보안성	RSA보다 느릴 수 있음
디지털 서명 버전도 존재 (ElGamal 서명)

---

4. 🔐 응용 분야

• PGP (Pretty Good Privacy)
• GPG (GNU Privacy Guard)
• 디지털 서명 알고리즘 (DSA는 ElGamal 서명 기반)
• 암호화폐와 블록체인 일부 구조

---

🧬 ElGamal vs RSA 비교

항목 ElGamal RSA

보안 기반	이산 로그 문제	소인수 분해 문제
암호화 구조	무작위성 포함	결정적
암호문 크기	메시지의 2배	메시지 크기와 유사
속도	비교적 느림	상대적으로 빠름

 

 

 

양자역학이 바꾸는 사이버 보안의 미래 – 양자컴퓨터와 암호 기술의 충돌