Skip to content
Beside the Wheel

비대칭암호화

암호학
암호화

  • 비대칭 암호화는 공개 키와 개인 키라는 두 개의 서로 다른 키를 사용하는 암호화 방식이다.
  • 공개 키로 암호화한 데이터는 개인 키로만 복호화할 수 있다.
  • 공개 키는 안전하지 않은 채널로 전송해도 안전하다.
    • n명이 통신하려면 n개의 키 쌍만 필요하다. (대칭 암호화는 n(n-1)/2개)

RSA (Rivest-Shamir-Adleman)

  • 1977년 개발된 최초의 실용적 공개 키 암호 시스템이다.

  • 큰 소수의 곱셈은 쉽지만, 그 결과를 소인수분해하는 것은 계산적으로 어렵다는 원리를 이용한다.

  • 키 생성

    1. 두 개의 큰 소수 p, q를 선택한다.
    2. n = p × q를 계산한다. (공개 모듈러스)
    3. φ(n) = (p-1)(q-1)을 계산한다.
    4. φ(n)과 서로소인 e를 선택한다. (공개 지수, 보통 65537)
    5. d × e ≡ 1 (mod φ(n))를 만족하는 d를 계산한다. (개인 지수)
    • 공개 키: (e, n)
    • 개인 키: (d, n)

  • 암호화: c = m^e mod n

    • 평문 m을 공개 지수 e로 거듭제곱하고 n으로 모듈러 연산한다.

  • 복호화: m = c^d mod n

    • 암호문 c를 개인 지수 d로 거듭제곱하고 n으로 모듈러 연산한다.

관련 수학 개념

  • 오일러 피 함수 φ(n)

    • n 이하의 양의 정수 중 n과 서로소인 정수의 개수를 나타낸다.
    • n이 두 소수 p, q의 곱일 때: φ(n) = φ(p×q) = (p-1)(q-1)
    • 예: φ(15) = φ(3×5) = (3-1)(5-1) = 8

  • 오일러의 정리 (Euler’s Theorem)

    • a와 n이 서로소일 때: a^φ(n) ≡ 1 (mod n)
    • 이는 a^φ(n) + 1 ≡ a (mod n)를 의미한다.
    • RSA의 핵심: m^(ed) = m^(k×φ(n) + 1) ≡ m (mod n)

증명

c^d ≡ (m^e)^d ≡ m^(ed) (mod n)


ed ≡ 1 (mod φ(n)) 이므로
ed = k×φ(n) + 1 (k는 정수)


따라서 m^(ed) = m^(k×φ(n) + 1) = (m^φ(n))^k × m


오일러의 정리에 의해 m^φ(n) ≡ 1 (mod n)
따라서 (m^φ(n))^k ≡ 1 (mod n)


결론: m^(ed) ≡ m (mod n)

예시

p = 11, q = 13
n = 11 × 13 = 143
φ(n) = 10 × 12 = 120
e = 7 (120과 서로소)
d = 103 (7 × 103 = 721 = 6 × 120 + 1)


평문 m = 5
암호화: c = 5^7 mod 143 = 47
복호화: m = 47^103 mod 143 = 5

하이브리드 암호화

  • 하이브리드 암호화는 대칭 암호화와 비대칭 암호화를 결합하여 양쪽의 장점을 활용한다.
  • 비대칭 암호화는 연산이 오래걸리고, 암호화할 수 있는 데이터 길이에 한계가 있기 때문에 이러한 구조가 유용하게 사용된다.
  • 키 캡슐화라고도 한다. 간단하게 말하면 대칭키를 비대칭 암호화하는 방식이다.
    1. 세션 키 생성: 임의의 대칭 키를 생성한다.
    2. 데이터 암호화: 세션 키로 실제 데이터를 암호화한다. (키 하나로 대칭암호화)
    3. 키 암호화: 수신자의 공개 키로 세션 키를 암호화한다.
    4. 전송: 암호화된 데이터와 암호화된 세션 키를 함께 전송한다.
    5. 복호화: 수신자는 개인 키로 세션 키를 복호화하고, 세션 키로 데이터를 복호화한다.
  • 대부분의 실제 시스템(TLS, PGP, S/MIME)에서 사용된다.

참고

관련글
암호화Cipher암호화Diffie–Hellman 키교환암호화대칭암호화암호화서명과 영지식 증명암호화해시와 MAC블록체인Altcoin