공개키 암호

비밀키(대칭키) 암호 방식은 속도가 빠르다는 장점이 있지만, 통신 당사자끼리 키를 안전하게 나눠 가져야 하는 '키 분배' 문제가 있었습니다. 이를 해결하기 위해 등장한 것이 바로 '공개키 암호 시스템'입니다.

1. 공개키 암호 시스템의 기본 개념

공개키 알고리즘은 하나의 키가 아닌, 두 개의 서로 다른 키를 쌍으로 사용합니다.

• 공개키(Public Key): 모든 사람이 접근 가능하도록 외부에 공개하는 키
• 개인키(Private Key): 각 사용자 자신만이 비밀로 소유하는 키
• 핵심 원리: 암호 알고리즘과 암호키(공개키)를 공개하더라도, 복호키(개인키)를 계산해 내는 것은 불가능해야 함
• 통신 과정: A가 B에게 메시지를 보낼 때 B의 공개키로 암호화하면, 오직 B의 개인키로만 이 메시지를 복호화할 수 있음
  •  B의 개인키를 모르는 제3자는 메시지 복호화 불가능

2. 공개키 암호의 두 가지 핵심 응용

공개키 암호는 누구의 키로 암호화하느냐에 따라 크게 두 가지 목적으로 활용될 수 있습니다.

• 기밀성 보장 (암호화): 수신자(B)의 공개키로 평문을 암호화
  •  암호 해독자가 암호문과 공개키를 가로채더라도, 수신자의 개인키가 없으면 평문 획득 불가능
• 전자서명 및 인증 (Authentication): 반대로 송신자(A)의 개인키로 평문을 암호화하여 서명문을 만듬
  •  누구나 A의 공개키로 이를 복호화해볼 수 있어 평문 확인이 가능하지만, A의 개인키를 알 수 없으므로 다른 사람이 위조된 서명문을 작성하는 것은 불가능
• 실제 통신에서는 이 두 가지를 결합하여 기밀 유지와 서명을 동시에 수행하기도 함

3. 공개키 암호 시스템의 종류

공개키 암호는 쉽게 풀 수 없는 '수학적인 난제'를 이용하여 암호화를 수행합니다.

• 소인수 분해의 어려움 기반: 가장 널리 알려진 RSA 알고리즘이 있음
  • RSA는 암호/복호, 디지털 서명, 키 교환이 모두 가능
• 이산대수 문제 기반: 엘가말(El Gamal), 디피-헬만(Diffie-Hellman), 타원 곡선(ECC) 알고리즘 등이 속함

4. 대표적인 알고리즘: RSA

1977년에 개발되어 1978년에 공포된 RSA(Rivest, Shamir, Adleman)는 대표적인 공개키 알고리즘입니다.

• 수식: * 암호화: $C=M^{e}$ mod n
  • 복호화: $M=C^{d}$ mod n
• 키 쌍: 공개키는 $KU=\{e,n\}$ 이고, 개인키는 $KR=\{d,n\}$
• 안전성의 비밀: $n$을 만들기 위해 $10^{100}$ 정도 크기의 두 소수 $p$와 $q$를 선택해 곱함
  • ($n=p^{*}q$). 공개된 $e$와 $n$을 알더라도, 매우 큰 수인 $n$을 소인수분해하는 것은 수학적인 난제이므로 개인키를 알아낼 수 없음

5. 공개키 암호의 요구사항과 한계점 극복

성공적인 공개키 암호 시스템이 되기 위해서는 몇 가지 조건과 방어책이 필요합니다.

• 요구 사항: 키 쌍의 생성이 쉬워야 하며, 암호문 생성과 복호화 과정도 쉬워야 함
  • 반면 공개키나 암호문만으로 개인키와 평문을 복구하는 것은 어려워야 함
• 한계와 방어: 무차별 대입 공격(전사적 공격)에 취약할 수 있어 키의 크기를 크게 만들어 방지하지만, 이 때문에 대칭키 방식보다 상대적으로 속도가 느려짐
  •  또한, 모든 가능한 메시지를 공개키로 암호화해 비교하는 공격을 막기 위해 메시지에 임의의 비트를 추가하여 보호함