Chapter 4 - Cryptography (Public key algorithm)

Asymmetric key cryptography

대칭키 암호화 알고리즘은 호스트의 수를 N이라고 했을 때, 키 생성 시간이 O(n^2)이 걸리는 단점이 있었다.

 

이에 대해 공개키 암호화 알고리즘은 키를 공유하지 않고, 각 호스트가 Public Key와 Private Key를 생성한다.

 

public key는 모두에게 공개되어있는 키이고, private key는 오직 자신만 알고 있는 키이다.

따라서 키를 생성하는 시간 복잡도는 O(n)으로, 대칭키 암호화 알고리즘의 단점을 해결해준다.

 

방식

1. Encryption

Alice가 Bob에게 보낼 때, Bob의 공개키로 암호화하여 전송

Bob은 자신의 개인키로 복호화

2. Digital signature

Bob이 Alice에게 자신의 개인 키로 암호화 해서 전송.

Alice는 Bob의 공개키로 복호화.

 

그런데, 비대칭 키 암호화 알고리즘은 많은 계산적 자원이 필요하다..

(매번 통신할 때마다 공개키/개인키를 사용하여 암/복호화 과정 진행)

 

그래서 session key를 사용하는 방식 + MD(msg digest)를 사용하는 방식으로 해결할 수 있음

 

Establishing "Symmetric key (Session key)"

비대칭 암호화 알고리즘을 사용하여 대칭 키를 안전하게 전달하는 방식이다.

 

작동 방식

1. Alice는 Session key(대칭키)를 생성

2. Bob의 공개키로 세션 키를 암호화 하여 Bob에게 전송한다.

3. Bob은 자신의 개인 키로 복호화하여 세션 키를 얻는다.

4. 이후, 보내고자 하는 메시지를 세션키로 암호화하여 서로 통신한다.

Message Digest Signing

비대칭키 암호화 알고리즘을 사용하여 데이터의 무결성을 보장하고, 서명자의 신원을 인증할 수 있는 방식

이 과정은 주로 디지털 서명을 생성하는 데 사용된다.

긴 message를 hash함수를 사용하여 암호화 하여 작은 크기의 Message Digest를 생성한다. 이를 암호화하여 전송하는 방식.

작동 방식

1. Bob이 긴 메시지를 hash 함수를 사용하여 암호화 한다. (Message Digest 생성)

2. 이를 Bob의 개인 키로 암호화하여 Alice에게 전송해준다.

3. Alice는 message digest를 생성하고, Bob의 공개키를 통해 Bob의 서명을 복호화 한 뒤, 둘이 같은지 검증

 

 

그래서 CA에서 공개키를 발급해줄 때의 과정까지 포함하면 다음과 같다.

 

1. CA에서 자신의 개인키로 Bob의 공개키를 암호화하여 Bob에게 전송해준다.

2. Bob은 CA의 공개키로 복호화하여 자신의 공개키를 얻는다.

3. Alice에게도 CA의 개인키로 암호화된 Bob의 공개키를 전송하여 안전하게 Bob의 공개키를 공유한다.

4. Alice는 session key를 생성한 뒤, Bob의 공개키로 암호화 하여 Bob에게 전송한다.

5. Bob은 자신의 개인키로 복호화하여, Session key를 공유하게 된다.

6. Alice는 보내고자 하는 message를 session key로 암호화 하여 Bob에게 보내고, Bob은 이를 복호화 하여 Message를 얻는다

7. 이후 Alice는 Message를 해시화 한 뒤, 자신의 개인키로 암호화 하여 Bob에게 보낸다.

8. Bob은 session key를 복호화하여 얻은 message를 직접 해시화 한다. 그리고 Alice의 공개키로 7번에서 얻은 암호문을 복호화 한다.

9. 둘을 비교하여 같은 지 체크. (무결성 검증)

 

 

 

Diffie-Hellman

최초의 공개 키 암호화 알고리즘이다.

두 사용자가 암호화된 통신을 하기 위해 공유할 비밀 키를 안전하게 생성하는 방법

두 사용자가 공개적인 네트워크 상에서 비밀 키를 교환하지 않고도 동일한 비밀 키를 공유할 수 있도록 해줌.

 

작동 방식

 

• 공통 값 설정: 먼저 두 사용자는 공통적으로 사용할 두 개의 값 g와 p를 선택합니다. 여기서:
  • p: 매우 큰 소수 (prime number)
  • g: p보다 작은 수
  위 p와 g는 공개적으로 알려져도 상관이 없는 값들이다.
• 비밀 키 생성:
  • 각 사용자는 공개되지 않은 자신만의 비밀 키를 선택한다.
    예를 들어, 사용자 A는 비밀 키 x를 선택하고, 사용자 B는 비밀 키 y를 선택했다고 하자.
    
    • 사용자 A는 g^x mod p 값을 계산하고, 사용자 B는 g^y mod p 값을 계산한다.
    • 이 두 계산의 결과는 서로 교환되며, 이 중간 값은 안전하지 않은 네트워크를 통해 교환할 수 있음
• 공유 비밀 키 생성:
  • 사용자 A는 B에게 받은 값, 사용자 B는 A에게 받은 값에 자신의 비밀키로 제곱해준다.
    • A -> (g^y mod p) ^ x
    • B -> (g^x mod p) ^ y 
  • 수학적으로, 두 사용자가 계산한 결과는 동일하다. 이 값은 두 사용자만이 알 수 있는 공유 비밀 키가 된다.
    • g^(xy) mod p

RSA 알고리즘

1977년에 개발된 비대칭키 암호화 알고리즘으로, 현재까지 널리 사용되는 공개키 암호화 기법 중 하나이다.

RSA는 키 생성, 암호화, 서명 검증 등의 기능을 제공하며, 주로 데이터 암호화와 디지털 서명에 사용된다.

RSA의 보안은 매우 큰 소수의 곱을 소인수분해하는 것이 계산적으로 어려운 것에 기반함.

 

작동 방식

1. 키 생성

1. 두 개의 큰 소수 p와 q 선택

2. n = p x q

3. ϕ(n) (오일러 함수) = (p-1) x (q-1) 계산

4. (1 < e < ϕ(n) && e와 ϕ(n)) 조건을 만족하는 e를 계산한다.

5. e x d = 1 % ϕ(n) 을 만족하는 d를 계산한다.

 

수신자 => 공개 키 : (e, n) / 개인 키: (d,n)로 구성 됨.

 

2. 암호화

Alice가 Bob에게 메시지를 보내는 상황일 때, Alice는 Bob의 공개키 (e,n)을 통해 암호화

C = M^e mod n (암호화된 메시지)

3. 복호화

Bob은 자신의 개인 키인 (d,n)을 통해 C를 복호화

C^d mod n = M^ed mod n = M

 

증명

키 생성 단계의 5번 과정에서 e x d = 1 + kϕ(n) 수식이 도출된다.

M^ed mod n = M^1 + kϕ(n) mod n = M * M ^ kϕ(n) mod n

 

* 오일러 정리에 따르면 M ^ϕ(n) mod n = 1이다.

 

따라서 M mod n 이 나오므로 M을 복호화 할 수 있다.