연습

SSL 복습 및 RSA 알고리즘 사용 이유

onaeonae1 2024. 5. 14. 23:39

1. SSL 복습: 공부하다가 생긴 의문점 정리

Q1. SSL 인증서 전달과 Handshake 의 순서?

→ 우선 Handshake 의 순서는 다음과 같다.

  1. (Client → Server) Client Hello
  2. (Server → Client) Server Hello - Certificate - ServerHelloDone
  3. (Client → Server) ClientKeyExchange - ChangeCipherSpecFinished
  4. (Server → Client) ChangeCipherSpecFinished

SSL 인증서는 "Certificate" 단계에서 Client 에게 전달됨.

즉, SSL 인증서 전달은 Handshake 과정에 포함된 것이지 서로 어떤 순서를 가지는게 아님

Q2. SSL 통신 과정에서 사용되는 Key 목록과 역할에 대해

지금까지 공부한 결과 TLS/SSL 통신 과정에 사용되는 모든 Key들은 다음과 같다.

  1. CA 공개키/비공개키
  2. Server 공개키/비공개키
  3. Server-Client 간 암호화 통신에 사용할 대칭키(=Session-key)

이때 사용하는 공개키 암호화 알고리즘은 RSA라고 가정하고, 각각의 역할에 대해 설명해보자

  • CA 공개키/비공개키
    • SSL 인증서를 확인할 때 사용 → SSL 인증서는 CA 비공개키로 encode 되어 있음
    • Client는 CA 공개키를 알고 있으므로 SSL 인증서를 decode 가능 → Server 공개키 확보 가능
    • CA 비공개키가 노출되면 CA 담당 회사는 망함 → 인증서의 가치가 없어짐
    • SSL 인증서를 decode 하면서 Server 공개키 확보, 전자 서명등의 기능을 수행함
  • Server 공개키/비공개키
    • Client-Server가 암호화 통신에 사용할 대칭키를 주고 받는 데 사용
    • 실제 SSL 통신에서는 공개키 방식과 대칭키 방식을 혼용 → 공개키 방식이 연산량 많아서
    • 실제 주고받는 데이터의 암호화에는 대칭키 방식을 사용 → 이 대칭키를 Session-Key로 부름
    • 이때 사용할 대칭키를 주고받는 과정에서 공개키 방식을 사용 및 Server 공개키 활용됨
    • 우선 SSL 인증서에 서버 측 공개키가 존재, Client가 이를 파악할 수 있음
    • Handshake 과정에서 Client 와 Server 가 각각 Random-Data를 생성하는 부분 존재
    • ServerHelloDone 에서 Server Random-Data가 Client 에게 Server 비공개키로 encode 되어 전달됨
    • ClientKeyExchange에서 Client는 우선 Server Random-Data를 Server 공개키로 encode, 아까 생성해둔 Client Random-Data와 조합해 pre-master-key를 생성. 이를 Server 공개키로 encode. 이후 Server에 전달(=ChangeCipherSpec) 이로 인해 외부에 노출되지 않고 서로 간의 대칭키를 공유하는데 성공(=Session-Key 로 확정됨)
  • Server-Client 간 암호화 통신에 사용할 대칭키(=Session-Key)
    • Handshake를 거치며 서로 공유됨(이 과정에서 위에서 정리한 대로 Server 공개키/비공개키 사용)
    • 대칭키 암호화 통신에 사용됨
    이제 복습은 충분히 했으니깐 RSA로 넘어가보자

2. RSA 알고리즘

2-1. 공개키 암호화

  • 공개키 암호화는 지금까지 정리한 대로 공개키/비공개키 존재
    • 공개키/비공개키는 서로 Encode-Decode 가 가능한 관계
  • TLS/SSL 통신에서는 Key를 교환하는데 사용한다.
  • 이에 대해서는 다음과 같은 알고리즘들이 존재
    • Diffie-Hellman 계열 (DH, DHE, ECDH, ECDHE) → DH에 타원곡선 암호화가 섞여가는 방식
    • RSA → 비대칭키를 사용, 아주 큰 수의 소인수 분해하는 과정을 사용

2-2. 기본 설명

  • RSA 알고리즘은 MIT 에서 개발됨, 개발한 사람 3명의 이름을 따옴
    • Rivest, Shamir, Adleman
  • 공개키 암호화 방식 중에서는 가장 널리 쓰이고 있음
    • 안정성이 검증됨
    • 구현하기 쉬움
  • 아주 큰 값의 정수에 대해서 소인수 분해가 어렵다는 부분에서 착안해서 만듬

2-3. 일방향 함수

  • 모든 공개키 알고리즘들에서는 일방향 함수 를 사용
    • 한 쪽으로는 계산이 쉬운데 반대쪽은 계산하기가 어려운 함수를 의미
    • 공개키 알고리즘에서는 암호화 과정에서 일방향 함수를 사용
    • 이로 인해 암호화한 결과(=일방향 함수를 거침) 에서 평문을 확인하기 힘듬
    • 이때 만약 Key 가 하나라면 decode 하는 사람도 답이 없음
    • 그래서 Key 가 2개 존재하며 서로 유추할 수 있는 관계라는 것
    • e.g) 120938128317의 소인수 분해를 노가다로 하긴 어렵지만 한 소인수 값 알면 쉽게 가능
  • 상용에서 쓰이는 공개키 알고리즘들의 일방향 함수는 노가다로 가져오기 어렵도록 설계

2-4. Key를 생성하는 방법

Key를 생성하는 방법은 아주 간단하다.

  1. 서로 다른 임의의 소수 p, q 를 선택 (클수록 좋음)
  2. p 와 q 를 곱한 값인 n 을 생성
  3. ϕ(n) = (p-1) * (q-1) 을 구함
  4. ϕ(n) 과 서로소의 관계에 있는 e 를 구함. 즉 GCD(e, ϕ(n)) = 1
    • 단 1 < e < ϕ(n) 임
  5. 동시에 (e * d) mod (ϕ(n)) =1 을 만족하는 d를 구함
    • 단 1< d < ϕ(n) 임
  6. 비공개키는 n,d 공개키는 n,e 로 생성 완료!

2-5. 아니 이게 뭔 소리야

우선 저 과정에 가까워지기 위해 수학적인 내용들을 하나씩 살펴 보자

  1. 오일러 파이 함수 ϕ?
    • 오일러 파이 함수는 1~(n-1) 까지 양의 정수 중 n과 서로소의 관계인 정수들의 갯수를 의미
    • 다음과 같은 특별한 경우가 존재
      1. n이 소수(prime number) 라면 ϕ(n) = n-1
      2. 양의 정수 n이 두 개의 소수 p와 q의 곱으로 이루어져 있다면 ϕ(n) = (p-1)*(q-1)
    • 그러니깐 ϕ(n) =(p-1)*(q-1) 이 왜 나왔는지 알 수 있다
  2. 법(modulus)
    • 어떤 형식이 반복되는 경우에 그 반복되는 경계점을 의미 (나머지 연산 딱임)
    • 시계를 예로 들면 60분을 경계로 다시 1분으로 돌아감. 이때 이 60이 모듈러스가 되는 것
      • 이를 시계의 분은 60인 모듈러스를 따른다고 하는 것
      • 모듈러스의 정의에 의해 80분에 대해 다음과 같은 수식으로 표현 80 ≡ 20 (mod 60)
        • 80은 법 60에 대해 20과 합동이다
    • RSA에서 이 법이라는 개념을 사용하는 이유는 일방향 함수를 위해서이다.
      • 200 mod 60, 140 mod 60 모두 값이 20임은 쉽게 계산됨
      • 그러나 그 반대는 어려움
        • 20, 140, 200 모두 mod 60 시 20 나오는 건 쉽게 추정할 수 있다고 쳐보자
        • 그런데 mod 하는 값이 60이 큰 값이면 아주 어려워짐 그래서 p q 큰 값 쓰는거
  3. 오일러 정리
    • 법의 특수한 경우를 공식으로 만든 것
    • 두 양의 정수 a 와 n 이 서로소의 관계 (=GCD(a,n) = 1) 일때 다음이 성립
      • a ^ ϕ(n) ≡ 1 (mod n)
      • 이는 다음과 같이 정리됨: a ^ϕ(n) mod n = 1

이제 어느정도 감을 잡았으니 예시를 한번 들어보자

2-6. 연습

서버 측에서 Key를 만드는 과정을 따라해보자

  1. 우선 n 에 필요한 소수 p,q 를 선택: 11, 13 으로 선택해보자
  2. 따라서 n은 143
  3. ϕ(n) = (11-1) * (13-1) = 120
  4. GCD(e, 120) = 1 을 만족하는 e 의 후보는 아주 많음 일단 보류
  5. (e * d) mod 120 = 1 을 만족하는 d를 구함
  6. 이를 구하기 위해 e * d 의 값을 적당히 721 정도로 잡아주면 7 *103 으로 좁혀짐
  7. 뭘 e로 사용하던 GCD(e,120)을 만족하니깐 공개키는 (143, 7). 비공개키는 (143,103)

아마 이렇게 대충 만들진 않을 것 같은데 일단 수학적인 부분은 알겠다.

2-7. Encode 및 Decode

  • 힘들게 생성한 Key 들로부터 Encode, Decode를 진행
    • 공개키 N, e
    • 비공개키 N,d
  • 평문을 M 이라고 하고 이는 M<n을 만족
  • Encode는 다음과 같음
    • C = M ^ e (mod n)
  • Decode는 다음과 같음
    • M = C ^d (mod n)
  • 공개키 암호화니깐 그 반대도 만족하는 관계일 것이다

2-8. 예시

  • 아까 2-6에서 구한 N, e, d 를 바탕으로 연습해보자
    • N = 143
    • e = 7
    • d = 103
  • 평문은 어떤 방식을 거쳐 숫자로 바뀌는 것 같지만 일단은 2 정도로 잡아보자
    • M = 2
  • 공개키로 Encode - 비공개키로 Decode
    • [Encode] C = 2 ^ 7 (mod 143) = 128
    • [Decode] M = 128 ^ 103 (mod 143) = 2 (계산량이 진짜 개많다)
  • 비공개키로 Encode - 공개키로 Decode
    • [Encode] C = 2 ^ 103 (mod 143) = 63
    • [Decode] M = 63 ^ 7 (mod 143) = 2
  • 둘다 Encode, Decode 가 가능함을 확인가능 !!!!

실제 통신 과정에서 정확하게 통신하는 방법이 많이 궁금한데 일단은 대충 파악했다

수론 특징을 사용해서 공개키, 비공개키를 만들고 이게 노가다로 돌리기는 어렵다로 요약

그리고 연산이 아주 많은 부분 (c ^d (mod n)) 같은 부분은 직접 계산하면 컴터가 터짐

따라서 다음과 같은 방식을 사용

 

3. 참조