10장-기타 공개키 암호 시스템

Applications for Public-Key Cryptosystems

공개키 암호 시스템의 3가지 주요 응용 분야

1. 암호화/복호화 (Encryption/Decryption)
   • 송신자는 수신자의 공개키로 메시지를 암호화한다.
   • 수신자는 자신의 비밀키로 복호화한다.
2. 디지털 서명 (Digital Signature)
   • 송신자는 자신의 비밀키로 서명하여 메시지의 무결성과 발신자를 인증한다.
3. 키 교환 (Key Exchange)
   • 두 참가자가 안전하게 세션 키를 교환한다 (예: 디피-헬만).

---

Discrete Logarithm (이산 로그 문제)

• 모듈로 19의 거듭제곱 결과를 보여주는 테이블 
• 각 행은 밑수(a), 각 열은 지수(i), 값은 a^i mod 19다.
• 예: 2^3 mod 19 = 8
• 이 테이블은 이산 로그 문제의 어려움을 시각적으로 보여준다. (예: 8 = 2^3 mod 19 이지만, 3 = log₂(8) mod 19를 계산하는 이산 로그 문제는 어렵다.)

---

Diffie-Hellman Key Exchange

• 최초 공개된 공개키 알고리즘 (1976년 발표)
• 기밀한 세션 키를 안전하게 교환 가능.
• 이 알고리즘은 대칭키 암호와 결합해 사용됨.
• 보안성은 이산 로그 문제의 어려움에 기반.

---

Figure 10.1: Diffie-Hellman 키 교환 과정

• 두 사람이 소수 q, 원시근 α를 공유함.
• Alice:
  • 비밀키 X_A로 생성 -> Y_A = α^X_A mod q
• Bob:
  • 비밀키 X_B로 생성 -> Y_B = α^X_B mod q
• 서로의 공개키 Y 값을 교환하고,
  • Alice: K = Y_B^X_A mod q
  • Bob: K = Y_A^X_B mod q
• 결과적으로 공통의 비밀 키 K를 공유하게 됨.

---

RSA vs DH: Forward Secrecy 비교

🟠 개념 설명:

세션이란?

• 두 사용자가 통신을 주고받는 하나의 암호화된 대화 단위
• 예: 우리가 메신저에서 보안 채팅을 하면, 그 한 번의 대화를 “세션”이라 부름

-> 그래서 "세션 키"란 그 한 번의 대화를 암호화하는 데 쓰는 임시 키를 말합니다.

 

Forward Secrecy란?

• 어떤 세션의 키가 유출되어도, 다른 이전/미래 세션의 보안에는 영향이 없어야 한다는 보안 성질.

 

🔹RSA

• 고정된 개인키(d)를 사용해 매 세션마다 새로운 세션 키(K₁, K₂)를 복호화
• 각 세션 키는 공개키로 암호화되어 전송됨

📌 문제점

• 개인키가 유출되면 이전 모든 세션의 키도 복호화 가능
• Forward Secrecy 제공 안됨

🔹Diffie–Hellman (DH)

• 매 세션마다 새로운 비밀값(X_A, X_B)을 생성
• 각 세션이 끝나면 비밀값은 폐기(discard)
• 서로의 공개키를 이용해 공통의 세션 키(K) 생성

📌 장점

• 세션 키 유출되어도 이전 세션은 안전
• Forward Secrecy 제공

🔹 비교 요약표

항목	RSA	DH
세션마다 키 생성	❌ 고정된 개인키 사용	✅ 매 세션마다 새 비밀값 생성
Forward Secrecy	❌ 없음	✅ 있음
키 유출 시 영향	모든 과거 세션 위험	해당 세션만 위험
비밀값 폐기 여부	✖ 폐기 안 함	✔ 폐기함 (Discard X_A, X_B)

 

💡 Forward Secrecy가 중요한 이유

한 번의 공격으로 과거 모든 대화 내용이 해독되는 것을 방지할 수 있음 -> 장기 보안을 위해 필수 기능

---

Figure 10.2: 중간자 공격 (Man-in-the-Middle)

🔹공격 시나리오

• 공격자 Darth가 Alice와 Bob 사이에 몰래 개입하여,
  • Alice에겐 자신(Darth)의 공개키를 Bob의 것처럼 전달하고,
  • Bob에겐 자신(Darth)의 또 다른 공개키를 Alice의 것처럼 전달함.
• Alice는 Darth와 공유된 비밀키 K₂를 사용하고,
• Bob은 Darth와 공유된 또 다른 키 K₁를 사용함.
• 결과적으로 Alice와 Bob은 서로 다른 키를 가지며,
• 통신은 Darth를 통해 모두 중간에서 가로채지고 해독될 수 있음.

 

❗ 왜 위험한가?

• Alice와 Bob은 암호화된 통신이라고 믿지만,
• 실제로는 모든 메시지를 Darth가 복호화/조작 가능.
• 즉, 암호화는 되어 있지만, 상대가 누구인지 검증이 안 되었기 때문.

 

🔹해결책: 인증 (Authentication)

• 공개키를 검증할 수 있는 방법이 반드시 필요:
  • 인증서 (Certificate)
  • 디지털 서명
  • 공인된 공개키 디렉토리 등

👉 이를 통해 공개키가 진짜 소유자의 것인지 확인할 수 있음.

 

 

요약

항목	설명
공격 방법	공격자가 두 당사자와 각각 키 교환을 함
문제점	서로 다른 키를 공유 -> 제3자가 모든 메시지를 복호화 가능
해결책	인증 (공개키에 대한 신뢰 확보)

---

Figure 10.3: ElGamal Cryptosystem

🔹기본 개념

• Diffie–Hellman을 기반으로 하는 공개키 암호 시스템
• 이산 로그 문제(DLP)의 어려움에 기반한 보안성

🔹공개키 구성

• q: 큰 소수
• α: q의 원시근 (primitive root)
• X_A: Alice의 비밀키
• Y_A = α^X_A mod q: Alice의 공개키
• 공개키: (q, α, Y_A)

🔐 암호화 (Bob -> Alice)

• 메시지: M
• Bob이 임의의 정수 k를 선택 (매 암호화마다 무작위)
• 계산:
  • K = Y_A^k mod q -> 일종의 일회용 비밀키
  • C₁ = α^k mod q -> Bob이 선택한 k에 해당하는 임시 공개키 계산값
  • C₂ = M * K mod q -> M을 K로 암호화 
• 암호문: (C₁, C₂)

📌 C₁만 있으면 Alice는 동일한 K를 구할 수 있음

 

🔓 복호화 (Alice)

• 받은 암호문 (C₁, C₂)
• Alice는 자신의 비밀키 X_A로 K = C₁^X_A mod q 계산
• 복호화: M = C₂ / K mod q

⚠ 여기서 /는 곱셈 역원 연산(modular inverse)

 

🔹장점

• 무작위성 도입 -> 동일한 메시지도 암호화할 때마다 다른 결과 => foward secrecy 만족 
• DLP 기반의 강력한 보안

🔹한계 및 주의점

• 암호문 크기: 2배 (C₁, C₂) -> RSA보다 큼
• 복호화를 위해 modular inverse 연산 필요
• 속도 측면에서는 ECC/비대칭 암호에 비해 조금 무거울 수 있음

요약

단계	내용
키 생성	Y_A = α^X_A mod q
암호화	C₁ = α^k mod q, C₂ = M * Y_A^k mod q
복호화	M = C₂ / C₁^X_A mod q
보안성	DLP (이산 로그 문제) 기반

---

Elliptic Curve Cryptography (ECC)

• ECC에서의 덧셈 연산은 RSA의 모듈러 곱셈과 유사한 역할을 한다.
• 점 곱셈 (scalar multiplication) = 여러 번 덧셈 -> RSA의 지수승과 유사

🔹ECDLP (Elliptic Curve Discrete Logarithm Problem)

• 수식: Q = k × P (Q, P는 타원 곡선 위의 점, k는 정수)
  • Q는 쉽게 계산 가능 (P와 k를 알고 있을 때)
  • 그러나 Q와 P로부터 k를 찾는 것은 매우 어려움
    ->이 문제를 ECDLP라고 부름

🔹점 곱셈 예시 (binary method)

Q ← O  (무효점에서 시작)
for i ← l to 0:
    Q ← 2Q
    if k_i == 1:
        Q ← Q + P
return Q

---

Elliptic Curve Arithmetic (타원 곡선 연산)

• RSA보다 작은 키로 동등한 보안성을 제공.
• ECC (Elliptic Curve Cryptography):
  • IEEE P1363, IEEE 1609 등의 표준에서 사용.
• 계산 비용이 낮아 모바일, IoT 환경에 적합.

---

Comparable Security Strengths (보안 강도 비교)

• 다양한 암호 방식에 대한 보안 강도 비교 (NIST 기준)
• 예:
  • RSA 2048bit ≈ ECC 224–255bit
  • RSA 3072bit ≈ ECC 256–383bit
• ECC가 훨씬 작은 키 길이로 같은 보안 수준을 제공.

---

Review: Abelian Groups (아벨 군)

• 아벨 군은 다음 조건을 만족하는 이진 연산 집합:
  • Closure, Associative, Identity, Inverse, Commutative
• 교환법칙(Commutativity)이 있는 군 -> 아벨 군.
• 암호학에서는 이런 군 구조가 핵심 기반.

---

Review: Cyclic Group (순환 군)

• 그룹의 모든 원소가 하나의 원소 a의 거듭제곱으로 표현 가능.
• G = ⟨a⟩
• a는 생성자 (generator) 역할을 한다.
• 순환군은 항상 아벨 군이기도 함.
• DH, ElGamal 등은 순환군 구조 활용.

---

Figure 10.4: 타원 곡선 예시

• 타원 곡선: y^2 = x^3 + ax + b
• 곡선 위의 점들로 구성된 군 구조 사용.
• 점 덧셈(Point Addition)과 배수 연산(Scalar Multiplication)이 핵심.
• ECC의 기반이 되는 수학적 구조.

---

 

Figure 10.7 - ECC Diffie–Hellman Key Exchange

🔹공개 파라미터

• E(a, b) : 타원 곡선
• G : 타원 곡선 위의 기준점
• n : 기준점 G의 순환 수

🔹사용자 A의 키 생성

• 비밀키: n_A < n
• 공개키: P_A = n_A × G

🔹사용자 B의 키 생성

• 비밀키: n_B < n
• 공개키: P_B = n_B × G

🔹비밀 키 계산 (공통 키 공유)

• 사용자 A: K = n_A × P_B
• 사용자 B: K = n_B × P_A
• 결과: 같은 점 K를 공유함 (공통 비밀 키)

---

Security of Elliptic Curve Cryptography

• ECC의 보안은 ECDLP의 난이도에 기반한다.
• 현재까지 가장 빠른 공격은 Pollard rho method지만 여전히 어려움
• ECC는 같은 보안 수준에서도 훨씬 작은 키 길이를 사용할 수 있다:
  • 예: 256비트 ECC ≈ 3072비트 RSA
• 따라서 ECC는:
  • 계산량이 적고,
  • 전력 소모도 낮아,
  • 모바일/임베디드/IoT 환경에 적합하다.

---

요약

항목	설명
Diffie–Hellman 키 교환	비밀키 없이 공개키 교환으로 공통 키 생성보안은 이산 로그 문제(DLP)에 기반
ElGamal 암호	DH 기반 공개키 암호화무작위성 추가 -> 비결정적 암호화
순환군	하나의 원소로 모든 원소 생성 가능 (G = ⟨a⟩)암호학에서 생성자 사용
이산 로그 문제 (DLP)	a^k mod p = x는 쉬우나, 역으로 k를 구하기는 어려움
ECC (타원 곡선 암호)	작은 키로 동일한 보안 제공 (256bit ECC ≈ 3072bit RSA)점 덧셈과 점 곱셈 사용
ECDLP	타원 곡선 위에서 Q = kP일 때 k를 찾는 문제는 어려움ECC 보안의 핵심 기반
ECC-DH 키 교환	K = n_A × P_B = n_B × P_A로 공통 비밀키 공유
ECC 장점	짧은 키, 빠른 연산, 낮은 전력소모 -> IoT, 모바일에 적합