[정보보호론] Lecture8. Asymmetric Cryptography

※ 이 카테고리의 글들은 knu JY.Lee 교수님의 <정보보호론> 수업을 듣고 나름대로 필자가 정리한 글입니다.

※ 부족한 설명이 있거나, 잘못 알고 작성한 부분이 보인다면 댓글로 알려주시면 감사하겠습니다😊

 

 

목차

1. Key Distribution Problem

2. Key Distribution Techniques

   2-1. Key Distribution Center
   2-2. Diffie-Hellman Key Exchange

3. Public Key Cryptography
   3-1. RSA

---

1. Key Distribution Problem

대칭 키 암호화 방식(Symmetric Cryptography)에서, 보안을 위해 키를 안전하게 분배하는 것이 중요한데, 이 부분이 복잡하고 까다로운 문제로 알려져 있다.

대칭 키 암호화에서, 두 당사자(예: 송신자와 수신자)가 암호화 작업을 수행하기 전에 공유 비밀 키를 반드시 교환해야 한다. 이때, 키가 전송되는 동안 제3자가 키를 탈취하거나 복사할 위험이 발생할 수 있다. 키가 유출되면 해당 키로 암호화된 모든 메시지를 제3자가 해독할 수 있게 되므로 큰 보안 위협이 될 수 있다.

 

이처럼, 대칭 키 암호화 방식에서 사전에 공유 비밀 키를 교환하는 것은 필수이지만, 공격자로부터의 위협을 항상 경계해야 하는 문제가 있다.

 

그렇다면, 안전하게 키를 공유하는 방법을 알아보자.

---

2. Key Distribution Techniques

안전하게 키를 주고 받는 방법 4가지를 알아보자: 1) Face-toFace delivering 2) Use of a trusted courier 3) Use Diffie-Hellman key exchange 4) Use Public key cryptography system

 

 

2.1 직접 대면하여 전달 (Face-to-face delivering):

5명의 사람이 각각 키를 전달해야 한다면 총 10개의 키가 필요함

• 이 방식은 사람들이 직접 만나서 키를 주고받는 것으로, 가장 간단하면서도 직관적인 방식이다. 하지만 현실적으로 실행하기 어려운 경우가 많고, 비효율적이거나 위험할 수 있다.  
• 예를 들어, 모든 직원이 함께 모여서 키를 교환해야 하는 경우, 물리적 제한과 시간적 비용이 많이 들기 때문에 조직이 클수록 비현실적인 방법이다.
• N명이 있는 회사에서 한 사람이 나머지 N - 1명과 각각 통신해야 한다면, 그 사람은 N - 1개의 키를 관리해야 한다.
• 회사 전체의 입장에서 보면, 필요한 키는 N(N - 1) / 2 이다.

 

2.2 신뢰할 수 있는 운송 수단 사용 (Use of a trusted courier):

왼쪽 그림은 face-to-face 전달 방식, 오른쪽은 KDC를 사용한 키 공유 방식이다.

• 신뢰할 수 있는 운송 수단 (Use of a Trusted Courier), 즉 키 분배 센터 (KDC, Key Distribution Center)를 사용한 키 분배 방식이다.

❓KDC란

• 키 분배 센터(KDC)는 모든 사용자 간의 암호화 통신을 위해 중앙에서 키를 관리하고 분배하는 역할을 하는 컴퓨터나 시스템을 의미한다.
• KDC는 모든 사용자(혹은 노드)들의 키를 저장하고 있으며, 사용자가 통신을 원할 때 필요한 키를 KDC에서 요청하여 사용할 수 있다.

❓KDC를 활용한 키 전달 과정

Alice와 Bob이 KDC를 통해 키를 공유하고 있다.

1. Alice가 KDC에 요청:
   • Alice는 Bob과의 통신을 위해 KDC에 세션 키 요청을 보낸다.
2. KDC가 세션 키(K)를 생성:
   • KDC는 Alice와 Bob이 사용할 세션 키(K)를 생성한다.
3. KDC가 Alice에게 암호화된 세션 키(C_A)를 전송:
   • KDC는 세션 키(K)를 Alice의 키(K_A)로 암호화한 후, 암호화된 형태(C_A)로 Alice에게 보낸다.
4. KDC가 Bob에게 암호화된 세션 키(C_B)를 전송:
   • 동시에, KDC는 동일한 세션 키(K)를 Bob의 키(K_B)로 암호화하여 암호화된 형태(C_B)로 Bob에게 보낸다.
5. Alice가 세션 키(K)를 복호화:
   • Alice는 KDC로부터 받은 메시지를 자신의 키(K_A)로 복호화하여 세션 키(K)를 추출한다.
6. Alice가 세션 키를 사용해 메시지(M)를 암호화(C):
   • 이제 Alice는 얻은 세션 키(K)를 사용해 자신이 보내려는 메시지(M)를 암호화(C)한다.
7. Alice가 암호화된 메시지(C)를 Bob에게 전송:
   • Alice는 암호화된 메시지(C)를 Bob에게 전송한다.
8. Bob이 세션 키(K)를 복호화:
   • Bob은 KDC로부터 받은 메시지를 자신의 키(K_B)로 복호화하여 세션 키(K)를 추출한다.
9. Bob이 메시지(M)를 복호화:
   • 마지막으로, Bob은 Alice로부터 받은 암호화된 메시지(C)를 세션 키(K)를 사용해 복호화하여 원래 메시지(M)를 얻는다.

❓KDC를 통한 키 분배 방식의 문제점

• 모든 통신에 KDC가 관여해야 함: KDC는 모든 통신에서 키를 제공하는 역할을 하므로, 시스템에 과부하가 걸릴 수 있다.
• KDC의 실패는 전체 시스템의 중단을 의미함: KDC가 다운되거나 문제가 발생하면, 조직 내 모든 암호화 통신이 불가능해지며, 이는 전체 네트워크에 큰 영향을 줄 수 있다.
• 공격의 표적이 될 수 있음: KDC는 네트워크의 중요한 부분을 담당하고 있기 때문에, 해커의 주요 공격 대상이 될 수 있다. 만약 KDC가 공격을 받아서 손상되면 모든 키 정보가 유출될 위험이 있다.

 

2.3 디피-헬만 키 교환 사용 (Use Diffie–Hellman key exchange):

Diffie-Hellman 키 교환 방식의 핵심 개념: 공개된 정보와 비밀 정보를 섞음

• 디피-헬만 키 교환(Diffie–Hellman Key Exchange)은 두  사람이 안전하게 공유 비밀키를 생성할 수 있도록 돕는 초기 공개 키 프로토콜 중 하나이다.

❓디피-헬만 키 교환 방식의 절차 (그림으로 이해)

• Alice와 Bob은 각자 자신만 알고 있는 비밀 색(Secret Color)을 가지고 있다. 이 색은 공개되지 않고 개인이 비밀리에 보관한다.
• 서로 교환한 정보를 이용해 각각의 비밀 색을 더하여 공통의 색(혹은 공통의 비밀 키)을 생성한다.
• 이 과정에서 제3자는 동일한 키를 생성할 수 없다. 제3자가 비밀 색을 모르기 때문에, 교환된 정보만으로는 같은 키를 만들 수 없다.

❓디피-헬만 키 교환 방식의 절차 (수학적 과정)

주요 구성 요소

1. 공개 값:
   • 큰 소수 p와 생성자 g는 공개된 값으로 모든 사람이 알고 있어도 상관없다.
2. 비밀 값:
   • Alice는 자신의 비밀 값으로 a를 가지고 있고, Bob은 b라는 비밀 값을 가지고 있다. 이 값들은 절대 공개되지 않는다.

공개 교환 과정

Alice와 Bob은 각자의 비밀 값과 공개된 생성자 g, 소수 p를 사용하여 다음과 같은 과정을 통해 서로에게 공개 값을 전달한다.

• Alice는 A = g^a mod  p를 계산하여 Bob에게 전달
• Bob은 B = g^b mod  p를 계산하여 Alice에게 전달

이때, 두 값 A와 B는 공개적으로 교환되지만, 각자의 비밀 값 a와 b는 교환되지 않는다.

비밀 키 계산

Alice와 Bob은 상대방으로부터 받은 공개 값을 사용해 공통 비밀 키를 계산할 수 있다.

1. Alice의 계산:
   • Alice는 Bob으로부터 받은 값 B를 사용하여 K = B^a mod  p를 계산한다.
   • B^a mod  p = (g^b)^a mod  p = g^(b*a) mod  p
2. Bob의 계산:
   • Bob은 Alice로부터 받은 값 A를 사용하여 K = A^b mod  p를 계산한다.
   • A^b mod  p = (g^a)^b mod  p = g^(a*b) mod  p

결국, 두 사람 모두 같은 비밀 키 K = g^(a*b) mod  p를 얻을 수 있다. 이 키는 외부에 공개되지 않으며, 안전한 통신에 사용할 수 있다.

보안성 (공격자 Eve의 공격 가능성)

Eve가 g^(a*b) mod  p를 계산할 수 있는가?

• 공개된 값인 g^a mod  p와 g^b mod  p만으로 g^(a*b) mod  p를 계산하는 것은 이산 로그 문제(Discrete Logarithm Problem)에 해당된다.
• 이산 로그 문제는 수학적으로 계산하기 매우 어렵다고 여겨지기 때문에(지수적 복잡도), 현재의 컴퓨팅 기술로는 현실적으로 불가능하다.

 

2.4 공개 키 암호화 시스템 사용 (Use Public key cryptography system):

• 공개 키 암호화는 비대칭 암호화라고도 불리며, 각각의 공개 키와 비밀 키 쌍을 사용하여 암호화와 복호화를 수행하는 암호화 방식이다.

공개 키 암호화의 핵심 개념

• 키 쌍 생성:
  • 암호화 시스템은 두 개의 키 쌍을 생성한다. 하나는 공개 키 (Public Key)이고, 다른 하나는 비밀 키 (Private Key)이다.
  • 공개 키는 주로 암호화에 사용되고, 비밀 키는 복호화에 사용된다.
• 보안성:
  • 공개 키 암호화의 보안은 비밀 키를 안전하게 보관하는 것에 달려 있다. 공개 키는 자유롭게 배포해도 보안에 문제가 발생하지 않는다.
  • 공개 키가 널리 퍼져 있더라도, 비밀 키를 모르면 암호화된 메시지를 복호화할 수 없다.

키 쌍 생성 방식

• 일방향 함수 (One-way Function):
  • 공개 키와 비밀 키 쌍은 일방향 함수라는 수학적 알고리즘을 기반으로 생성된다.
  • 일방향 함수는 계산하기는 쉬워도, 역으로 계산하는 것은 매우 어려워서 보안성을 제공한다.
  • 예를 들어, 공개 키를 사용해 암호화된 데이터를 비밀 키 없이 복호화하는 것은 일방향 함수의 특성 때문에 매우 어렵다.

암호화와 복호화의 원리

• 암호화:
  • 공개 키로 암호화된 메시지(암호문)는 비밀 키가 없으면 복호화할 수 없다. 따라서, 누구나 공개 키로 메시지를 암호화할 수 있지만, 복호화는 비밀 키를 소유한 사람만 할 수 있다.
• 복호화:
  • 공개 키로 암호화된 암호문은 오직 해당 공개 키와 쌍을 이루는 비밀 키로만 복호화가 가능하다. 따라서, 메시지의 보안이 보장된다.

---

3. RSA

RSA는 1977년에 Ron Rivest, Adi Shamir, Leonard Adleman에 의해 개발되었으며, 세 사람의 성을 따서 RSA라고 불린다.

RSA의 작동 원리

• RSA는 두 개의 큰 소수의 곱을 이용하여 모듈러 거듭제곱(exponentiation modulo) 연산을 수행함으로써 암호화와 복호화를 수행한다.
• RSA의 보안성은 매우 큰 수를 인수분해하는 것이 어렵다는 수학적 문제에 기반하고 있다. 즉, 큰 소수를 곱하여 생성된 값으로부터 원래의 두 소수를 찾는 것이 매우 어려워서 RSA가 안전한 암호화 방식으로 여겨진다.

RSA의 응용

• RSA는 주로 키 교환 (Key Exchange)과 디지털 서명 (Digital Signature)에 사용된다.
  • 키 교환: 안전한 통신을 위해 두 당사자가 공유 비밀을 설정할 때 활용 가능.
  • 디지털 서명: 데이터의 무결성과 인증을 제공하기 위해 사용.

RSA와 AES의 속도 비교

• AES와 비교했을 때, RSA는 연산 과정이 복잡하기 때문에 상대적으로 느린 편이다.
• 예를 들어, AES-256 비트 암호화는 RSA 15,360 비트 암호화와 비슷한 수준의 보안성을 제공한다. 즉,  RSA의 키 길이가 훨씬 길어야 AES와 유사한 보안 수준을 제공할 수 있음을 의미한다.

RSA와 대칭 키 암호 방식(3TDEA, AES) 간의 보안 강도 비교를 보여줌

• 112 비트 보안: 3TDEA에 해당하며, RSA는 2,048 비트가 필요.
• 128 비트 보안: AES-128에 해당하며, RSA는 3,072 비트가 필요.
• 192 비트 보안: AES-192에 해당하며, RSA는 7,680 비트가 필요.
• 256 비트 보안: AES-256에 해당하며, RSA는 15,360 비트가 필요.

---

RSA의 핵심개념 (1) Modular Arithmetic

1. 모듈러 연산 (Modulo)

• 모듈러 연산은 한 숫자를 다른 숫자로 나눴을 때 나머지를 구하는 연산이다.
  • 예: 14 mod 12 = 2
  • 즉, 14를 12로 나누면 나머지가 2이기 때문에 14 mod  12의 결과는 2이다.

2. 동치 모듈러 (Congruent Modulo)

• 동치 모듈러는 두 숫자가 특정 값으로 나눴을 때 동일한 나머지를 가지면 서로 동치임을 의미한다.
  • 예: 14 ≡ 26 (mod 12) (14와 26을 12로 나눈 나머지가 같다는 뜻)
  • 수식으로는 a ≡ b (mod n) 는 a mod  n = b mod  n과 같은 의미입니다.

3. 기본 성질 (Basic Properties)

• 항등성 (Identity):
  • (a mod  n) mod  n = a mod  n
  • 이 식은 a를 n으로 나눈 나머지를 다시 n으로 나누더라도 결과가 변하지 않는다는 것을 의미한다.
• 분배법칙 (Distributive):
  • 덧셈에 대한 분배법칙: (a+b) mod  n=[(a mod  n)+(b mod  n)] mod  n
  • 곱셈에 대한 분배법칙: (a×b) mod  n=[(a mod  n)(b mod  n)] mod  n
  • 즉, 두 수의 덧셈이나 곱셈 후 모듈러 연산을 하는 것과 각각의 모듈러 연산을 먼저 수행한 뒤 결과를 다시 모듈러 연산하는 것은 동일하다.

모듈러 역원이란? (Modular Inverse)

1. 모듈로 곱셈 역원 (Modulo Multiplicative Inverse)

• 어떤 정수 a와 n에 대해, a×□ mod  n=1을 만족하는 숫자 □를 찾는 것이 모듈로 곱셈 역원이다.
  • 예: a=1, n=6일 때 1×1 mod  6. 따라서 □ = 1.

---

2. 항상 역원이 존재할까? (Does the inverse always exist?)

• 답은 NO 이다. 모든 숫자에 대해 모듈로 역원이 존재하진 않는다.
• 예시: mod 6 환경에서의 계산:
  1. 1: 역원이 존재 (1×1mod  6=1), □=1.
  2. 2: 역원이 없음 (gcd⁡(2,6)=2≠1).
  3. 3: 역원이 없음 (gcd⁡(3,6)=3≠1).
  4. 4: 역원이 없음 (gcd⁡(4,6)=2≠1).
  5. 5: 역원이 존재 (5×5mod  6=1), □=5.

---

3. 패턴 발견 (Patterns?)

• 모듈로 곱셈 역원은 a와 n이 서로소일 때만 존재한다.
  • 즉, gcd⁡(a,n)=1일 때 역원이 정의된다.
  • 여기서 gcd⁡는 두 수의 최대공약수(Greatest Common Divisor)를 뜻한다.

---

4. 실생활과 암호학의 활용

이 개념은 RSA 암호화에서 중요한 역할을 한다. RSA 키 생성 시 역원 계산이 필요하며, 이 과정을 통해 공개 키와 비밀 키를 생성한다. 모듈로 곱셈 역원은 또한 수학적 퍼즐이나 알고리즘에서 자주 사용된다​.