9장-공개키 암호 & RSA

 

대칭키 암호화 시스템 (Symmetric Cryptosystem)

🔹 핵심 개념 (Figure 3.2)

• 암호화와 복호화에 같은 키 K 사용
• 보안 문제: 이 공통 키를 안전하게 전달하는 방식이 필요 (Key Distribution)
• Cryptanalyst는 암호문 Y와 알고리즘을 통해 키 K를 추측하려 시도

---

 

공개키 암호화 도입의 동기 (Public-Key Motivation)

🔹 두 가지 문제 해결을 목표로 등장:

1. Key distribution 문제
   -> 공개키 방식은 공개된 키를 사용하므로 전달 문제를 완화
   -> 비밀 키를 안전하게 전달할 방법 필요
2. Digital signature 필요성
   -> 누가 보냈는지 확인(송신자 인증), 메시지 무결성 확인

🔹 역사적 배경

• 1976년, Diffie-Hellman에 의해 제안됨 (현대 공개키 암호의 시작)

---

공개키 암호 시스템 구성 요소

구성 요소	설명
Plaintext	암호화 전 원본 메시지
Encryption Algorithm	평문에 수학적 변환을 적용
Public Key (PU)	암호화에 사용, 공개됨
Private Key (PR)	복호화에 사용, 비밀 유지
Ciphertext	암호화된 메시지
Decryption Algorithm	암호문과 개인키를 사용해 복호화

 

⇒ 암호화와 복호화에 다른 키를 사용하는 것이 핵심

---

공개키 시스템 동작 방식

(1) 기밀성 모델 (Confidentiality 보장)

: 제3자가 내용을 읽지 못하게 보호

• 송신자 A는 수신자 B의 공개키(PU_b) 를 사용하여 메시지 X를 암호화
  암호문 Y = E[PU_b, X]
• 수신자 B는 자신의 개인키(PR_b) 로 복호화
  복호문 X = D[PR_b, Y]

✔️ 공개키 암호화는 기밀성(confidentiality) 을 보장

 

(2) 인증 모델 (Authentication 보장)

: 메시지가 진짜 송신자로부터 왔는지 검증

• 송신자 A는 자신의 개인키(PR_a) 로 메시지 M에 서명
  서명 S = D[PR_a, M]
• 수신자는 송신자 A의 공개키(PU_a) 로 서명 검증
  M = E[PU_a, S] 라면 -> 유효한 서명

✔️ 개인키 서명 + 공개키 검증 -> 인증 및 무결성 보장

 

(3) 기밀성 + 인증 통합 모델

: 메시지의 내용도 숨기고, 출처도 증명

1. 송신자 A:
   (1) 먼저 서명 생성: S = D[PR_a, M]
   (2) 서명과 메시지를 합쳐 암호화: Y = E[PU_b, (M ‖ S)]
   
2. 수신자 B:
   (1) 복호화: (M ‖ S) = D[PR_b, Y]
   (2) 서명 검증: M = E[PU_a, S]
   

✔️ 이 방식은 기밀성 + 인증 + 무결성을 동시에 만족

 

✅ 관련 표기 방식 예시

• PU_b = Public Key of B
• PR_a = Private Key of A
• E[PU_b, X] = B의 공개키로 메시지 X 암호화
• D[PR_b, Y] = B의 개인키로 암호문 Y 복호화

---

대칭키 vs 공개키 비교 (Table 9.2)

항목	대칭키 암호화	공개키 암호화
알고리즘	암복호화 동일	암호화 ↔ 복호화 별도 알고리즘
키	동일 키 사용	공개/비공개 키 쌍
보안성	키 유출 시 전체 보안 무너짐	키 유출 위험 줄어듬
키 전달	반드시 안전한 채널 필요	공개키는 공개 가능
속도	빠름	느림 (계산량 많음)

---

Figure 9.3: Public-Key Cryptosystem - Authentication

: 메시지가 진짜 송신자(A)가 보낸 것인지 확인하는 인증 구조

동작 과정 요약:

1. 송신자 A는 자신의 개인키(PRₐ) 를 사용해 메시지 X에 대해 서명 생성: Y = E[PRₐ, X] (전자서명)
2. 수신자 B는 송신자 A의 공개키(PUₐ) 를 이용해 Y를 복호화(검증): X = D[PUₐ, Y]
3. 복호화된 메시지가 원래 메시지와 같다면 -> 서명 유효 -> 송신자 인증

📌 이 방식은 기밀성은 보장하지 않고, 오직 송신자 인증만 제공.

위의 인증 구조는 앞서 설명한 디지털 서명(Digital Signature) 방식에 쓰인다 

---

Figure 9.4: Public-Key Cryptosystem - Authentication + Confidentiality

: 인증과 더불어 메시지 내용을 비밀로 보호하는 통합 구조

동작 과정 요약:

1. 송신자 A는 먼저 자신의 개인키(PRₐ) 로 메시지 X에 대해 서명 생성: Y = E[PRₐ, X]
2. 이후, 수신자 B의 공개키(PU_b) 로 Y를 암호화: Z = E[PU_b, Y]
3. 수신자 B는 자신의 개인키(PR_b) 로 먼저 복호화: Y = D[PR_b, Z]
4. 이어서, 송신자 A의 공개키(PUₐ) 로 Y의 서명 검증: X = D[PUₐ, Y]

📌 이 방식은 기밀성 + 무결성 + 인증을 동시에 제공

---

공개키 암호 시스템의 응용 (Applications)

공개키 암호는 크게 3가지 용도로 구분됩니다:

1. Encryption/Decryption
   -> 공개키로 암호화, 개인키로 복호화
2. Digital Signature
   -> 개인키로 서명, 공개키로 검증
3. Key Exchange (키 합의)
   -> 두 당사자가 세션 키를 안전하게 교환

---

알고리즘별 적용 가능성

알고리즘	Encryption	Signature	Key Exchange
RSA	Yes	Yes	Yes
Elliptic Curve	Yes	Yes	Yes
Diffie–Hellman	No	No	Yes
DSS	No	Yes	No

---

공개키 암호의 요구사항 (Public-Key Requirements)

공개키 암호 알고리즘은 다음 조건을 만족해야 한다:

1. 키 생성이 쉬워야 함
   • 공개키 PU와 개인키 PR 쌍 생성이 효율적이어야 함
2. 암호화가 쉬워야 함
   • 공개키와 평문으로 암호문 생성이 쉬워야 함
3. 복호화도 쉬워야 함
   • 개인키와 암호문으로 평문 복원이 가능해야 함
4. 역산이 어려워야 함 (보안)
   • 공개키만 보고 개인키를 유추하기 어려움
   • 공개키와 암호문으로 평문을 유추하기 어려움

---

RSA 알고리즘

• 1977년 MIT의 Rivest, Shamir, Adleman이 개발
• 가장 널리 사용되는 범용 공개키 암호 방식
• 메시지와 암호문은 모두 정수로 표현되며, 연산은 모듈러 연산 기반

---

Figure 9.5 – RSA 알고리즘 과정

🔹 키 생성

1. 두 소수 p, q 선택
2. n = p × q
3. 오일러 함수 계산: φ(n) = (p−1)(q−1)
4. e 선택: 1 < e < φ(n), gcd(e, φ(n)) = 1
5. d 계산: d ≡ e⁻¹ mod φ(n)
6. 공개키: (e, n), 개인키: (d, n)

🔹 암호화 (Bob이 Alice에게 보낼 때)

• C = Mᵉ mod n

🔹 복호화 (Alice가 복호화)

• M = Cᵈ mod n

-> 오일러 정리: Mᵉᵈ ≡ M mod n (M이 φ(n)과 서로소일 때)
위 슬라이드에 이에 대한 증명이 나와있다 

---

Figure 9.6 – RSA 예제

• 공개키: (e=7, n=187), 개인키: (d=23, n=187)
• 평문 88을 암호화 -> 88⁷ mod 187 = 11
• 복호화: 11²³ mod 187 = 88 -> 원래 메시지 복원

---

Figure 9.7 – RSA 블록 처리 & 하이브리드 암호화

• RSA는 큰 메시지를 블록 단위로 암호화해야 함
• 하이브리드 암호 방식:
  • Bob이 랜덤 세션 키 K를 생성해 RSA로 암호화 (C = Kᵉ mod n)
  • 실제 메시지는 대칭키로 빠르게 암호화 (AES-CTR 등)
  • Alice는 K = Cᵈ mod n으로 세션 키 복원 -> 평문 복호화

✔️ RSA는 키 교환, 대칭키는 데이터 암호화 -> 속도와 보안 둘 다 확보

---

RSA 암호화 vs 디지털 서명

• 암호화: 공개키로 암호화 -> 개인키로 복호화
• 서명: 개인키로 서명 -> 공개키로 검증

🔹이 슬라이드는 RSA 암호화를 보여준다

• Encryption by Bob with Alice’s Public Key
  -> Bob이 메시지 M을 Alice의 공개키 (e,n)를 이용해 C=M^e mod  n으로 암호화
• Decryption by Alice with Alice’s Private Key
  -> 암호문 C를 Alice가 자신의 개인키 d로 복호화: M=C^d mod  n

---

Figure 9.7 – RSA 디지털 서명 예시

🔹서명 생성

• Alice가 메시지 M에 대해 S = Mᵈ mod n 계산 (개인키 사용)

🔹서명 검증

• Bob은 Sᵉ mod n 계산해서 원래 메시지와 비교 (공개키 사용)

✔️ 서명은 메시지를 위조하지 않았다는 증거가 됨

 

⇒ 위의 RSA 암호화와 키의 사용 순서가 반대가 반대다

---

모듈러 연산에서의 지수승 계산

• RSA 연산은 모두 (a^b) mod n 형태
• 연산량이 많기 때문에 효율적인 계산법 필요

🔹 중요한 성질: (a mod n × b mod n) mod n = (a × b) mod n

---

Figure 9.8 – 빠른 모듈러 지수승 계산

Square-and-Multiply: (a^b) mod n 형태의 매우 큰 거듭제곱을 효율적으로 계산하는 알고리즘

 

🔹 알고리즘: Square-and-Multiply (왼→오 방향)

• b를 이진수로 표현 (예: b = 100011000)
• 왼쪽(MSB)부터 오른쪽(LSB)으로 비트를 하나씩 보며:
  • 제곱 (f = f² mod n): 항상 수행
  • 곱셈 (f = f × a mod n): 해당 비트가 1일 때만 수행

✔️ 매우 큰 지수를 빠르게 처리할 수 있어 RSA에 필수

 

계산과정

---

요약 정리

항목	설명
대칭키 암호	하나의 공유된 키를 사용하며 속도는 빠르지만 키 분배에 취약
공개키 암호	공개키로 암호화, 개인키로 복호화하며 기밀성, 인증, 키 교환 가능
RSA 암호화	공개키로 암호화 C = M^e mod n, 개인키로 복호화 M = C^d mod n
RSA 서명	개인키로 서명 S = M^d mod n, 공개키로 검증 M = S^e mod n
보안 기반	큰 소수의 곱셈, 오일러 정리, 지수 연산의 역산 어려움
연산 최적화	Square-and-Multiply 알고리즘을 활용한 지수승 mod 계산 최적화