Public Key Cryptography, PKC (PKC)

참고한 것들

서울대 권태경 교수님 컴퓨터네트워크보안특강 강의 (Spring 2024)

소개

암호화된 통신을 하고자 할 때 대칭키를 participant 에게 모두 뿌리는 것은 아무래도 힘들기 때문에 제시된 것이다.
암복호화에 사용되는 두 키가 다르기 때문에 비대칭키 쌍 (Asymmetric Key Pair) 라고 하며, 간단하게 요약하면
- 공개키 (Public Key): 데이터를 암호화할 때 사용, 암호화밖에 안되기 때문에 공개해도 무방한 Key 이다.
- 개인키 (Private Key, Secret Key): 데이터를 복호화할 때 사용, 따라서 공개되어서는 안되는 secret 이다.
이런 비대칭키 암호학을 넓게 Public Key Cryptography (PKC) 라고 하는 것.

PKC 에 깔린 기본 원리 중 하나는 One-way function 이다.
즉, 한 방향으로의 연산은 쉽지만 반대방향으로의 연산은 쉽지 않은 것을 의미한다.
One-way function 의 예시로 다음을 생각해 보자.
- 소수 17 와 23 을 곱해서 391 를 계산하는 것은 쉽다.
- 하지만 391 로 부터 17 와 23 의 곱이라는 것을 알아내는 것은 위의 곱셈에 비해서는 훨씬 어렵다.
- 이런 것을 one-way function 라고 하며, 위의 예시에서는 숫자가 작아서 좀만 노가다를 하면 역연산이 가능하지만 만일 저 두 소수가 음청나게 큰 수라면 이것을 알아내는 것은 거의 불가능에 가깝다.
PKC 에서 이 원리는 이렇게 적용된다.
- 비대칭키에서는 개인키로부터 얼마든지 공개키를 계산해낼 수 있지만, 공개키로 개인키를 계산해 내는 것은 불가능에 가깝다.
- 데이터를 암호화하는 것은 간단하지만, 이 암호화된 것으로부터 원래의 데이터를 알아내는 것은 불가능에 가깝다.
  - 근데 아무도 복호화를 할 수 없으면 좀 문제가 되겠지?
  - 그래서 “개인키를 가지고 있을 때에만” 복호화가 간단해져야 하고 그렇지 않다면 복잡해야 한다.
  - 이 원리가 그 다음에 나오는 Trapdoor 이다.

위에서 말한 것처럼, PKC 는 기본적으로 one-way function 이되 특정한 조건 하에서는 역연산이 가능할 필요가 있다.
이 “특정한 조건에서는 역연산을 가능하게 해주는 놈” 을 trapdoor 라고 표현한다.
정리해 보면
- 이건 쉬움: $Y = f (X)$
- 근데 이건 어려움: $X = f^{- 1} (Y)$
- 근데 이건 쉬움: $X = f^{- 1} (t r a p d oor, Y)$

SYMBOL	DESCRIPTION
`ku`, `k+`, `kp`	공개키 (Public key)
`kr`, `k-`, `ks`	개인키 (Private key)

위에서 말한 것처럼, 암호화는 공개키로, 복호화는 개인키로 수행한다.
- 암호화: $c i p h er = f (K_{p}, m s g)$
- 복호화: $m s g = f^{- 1} (K_{s}, c i p h er)$
이것은 실전에서는 이렇게 사용될 수 있다:
- 동작구 사는 김씨는 송파구 사는 서씨에게 새벽 세시에 햄버거를 맛있게 먹는 방법에 대해 암호화해서 은밀하게 알려주려고 한다고 해보자.
- 이때 서씨는 자신의 공개키를 김씨한테 알려준다.
  - 공개키는 공개되어도 상관 없기 때문에, 그냥 줘도 된다.
- 그럼 김씨는 이 공개키를 이용해 적어둔 “새벽 세시에 햄버거를 맛있게 먹는 방법” 을 암호화해서 서씨에게 보낸다.
  - 어차피 이것은 암호화되어 있기 때문에, 중간에 강남구사는 오씨가 훔친다고 해도 “김씨의 특허받은 새벽 세시에 햄버거를 맛있게 먹는 방법” 을 알아낼 수는 없다.
- 서씨는 이것을 받아들고, 자신의 개인키를 이용해 이것을 복호화해 비법을 알아내어 새벽 세시에 햄버거를 맛있게 먹게 된다.

새벽 세시에 햄버거를 먹는 놈이 있다고? ^patricks-burger

개인키를 이용해 암호화할 수도 있는데, 이것을 Signature 라고 한다.
- 사실 엄밀히 말하면 암호화는 아니다; 이 Signature 에 공개키를 들이민다고 해서 복호화할 수 있는 것은 아니기 때문이다.
- …하지만 이렇게도 많이 표현한다.
일단 연산을 한번 살펴보자:
- 개인키로 어떤 메세지에 대한 서명을 생성할 수 있다: $s i g na t u re = s i g n (K_{s}, m s g)$
- 그리고 이 서명은 메세지와 공개키를 이용해 검증될 수 있다: $t r u e ∣ f a l se = v er i f y (K_{p}, s i g na t u re, m s g)$
“서명” 이라는 워딩이 말해주는 것처럼, 이것은 Integrity (위조되지 않음) 와 Authenticity (내가 그랬음) 을 증명하는데에 사용될 수 있다.
- 만약에 $m s g$ 가 위조된다면, $v er i f y ()$ 가 실패할 것이다.
- 또한, 서명 생성에 사용되지 않은 공개키를 이용해 검증한다면 마찬가지로 $v er i f y ()$ 가 실패할 것이다.
따라서 검증에 성공했다면,
1. 서명 생성에 사용된 $m s g$ 와 검증에 사용된 $m s g$ 가 일치함 (위조되지 않음)
2. 검증에 사용된 공개키와 쌍을 이루는 개인키가 서명 생성에 사용됨 (즉, 개인키의 소유자가 서명을 생성했음)
- …이 증명되는 것이다.