663. ElGamal 및 DSA (디지털 서명 특화) 알고리즘

핵심 인사이트: RSA가 전 세계를 휩쓸며 "암호화"와 "전자 서명" 두 가지를 혼자 다 해먹고 있을 무렵, 학자들은 RSA의 소인수분해 방식이 나중에 털릴까 봐 불안했다. 그래서 전혀 다른 수학인 '이산대수'라는 새로운 수학 공식을 들고나왔다. 여기서 파생되어 보안 통신의 또 다른 축을 세운 두 개의 알고리즘이 ElGamal과 전자 서명 특화용 DSA다.

Ⅰ. 또 다른 수학적 난제: 이산대수 문제 (DLP)

RSA가 두 소수를 곱하는 '소인수분해'를 썼다면, 이번에 다룰 두 알고리즘은 **이산대수 문제(Discrete Logarithm Problem)**를 씁니다.

• $y = g^x \mod p$ 라는 공식에서 $g, x, p$를 알면 $y$는 구하기 쉽지만, 결과값 $y$와 밑 $g$, 모듈로 $p$를 알아도 지수(Exponent)인 $x$를 알아내는 것은 숫자가 커지면 물리적으로 불가능하다는 수학적 원리입니다.

Ⅱ. ElGamal (엘가말) 알고리즘

1985년 이집트의 암호학자 타헤르 엘가말(Taher Elgamal)이 이산대수 원리를 이용해 발표한 공개키 암호 알고리즘입니다.

1. ElGamal의 특징 (랜덤성)

• RSA와 달리 엘가말은 암호화를 할 때마다 **난수(Random Number)**를 공식 안에 끼워 넣습니다.
• 효과 (의미론적 안전성): "안녕하세요"라는 평문을 100번 암호화해도, 난수가 계속 바뀌기 때문에 나오는 암호문 100개가 매번 완전히 다르게 튀어나옵니다. 해커가 암호문들을 훔쳐보고 패턴을 분석하는 무차별 대입 통계 공격이 원천 차단되는 강력한 장점을 지닙니다.

2. 치명적인 단점 (Ciphertext Expansion)

• 난수를 섞는 부작용으로 인해, 평문을 암호화하고 나면 암호문의 크기가 원본 데이터의 딱 2배로 뚱뚱하게 부풀어 오릅니다(메시지 확장 현상).
• 통신 대역폭을 2배로 갉아먹기 때문에, 네트워크 트래픽 환경에서 메인으로 쓰기에는 RSA보다 불리하여 널리 대중화되지는 못했습니다. (대신 나중에 전자 서명 기술의 뼈대가 됨)

Ⅲ. DSA (Digital Signature Algorithm) - 전자 서명 특화 🌟

미국 정부(NIST)가 RSA의 독점을 막고 "국가 공식 전자 서명 표준"을 제정하기 위해, 앞서 말한 엘가말 알고리즘을 개조하여 1991년에 만든 표준 알고리즘입니다.

1. 오직 '도장(서명)'만을 위한 설계

• 핵심 차이: RSA는 앨리스에게 비밀 편지를 암호화해서 보낼 때(기밀성)도 쓸 수 있고, 도장(전자서명)을 찍을 때도 쓸 수 있는 양방향 만능입니다.
• DSA: 오직 "내가 썼다"는 것을 증명하는 전자 서명(Digital Signature) 생성과 검증, 오직 단 하나의 기능만 수행하도록 설계되었습니다. 메시지 내용을 암호화해서 숨기는 기능은 아예 지원하지 않습니다.

2. DSA의 장점

• 전용 서명 알고리즘답게, 전자 서명을 '생성'하는 속도가 RSA보다 훨씬 빠릅니다.
• 이 뛰어난 효율성 덕분에, 훗날 모바일 스마트폰에 맞게 용량을 다이어트시킨 **ECDSA(타원곡선 전자서명)**로 업그레이드되어 전 세계 비트코인 송금의 도장과 HTTPS 인증서의 표준으로 군림하게 됩니다.

📢 섹션 요약 비유: RSA가 편지 내용을 못 보게 검은 봉투에 숨길 수도 있고(기밀성), 편지 봉투에 내 빨간 도장을 꽝 찍을 수도 있는(전자 서명) '다기능 만능 스위스 아미 나이프'라면, DSA는 내용물을 검은 봉투에 숨기는 기능은 아예 떼어버리고, 오직 서명 도장 하나만 기가 막히고 빠르게, 그리고 잉크 번짐(위조) 없이 쾅쾅 찍어내는 '초정밀 전자동 스탬프 기계'입니다.