Introduction
Shared Key Cryptography, 즉 대칭키 암호화는 가장 고전적인 암호화 방식 중 하나로, 발신자와 수신자가 같은 키를 공유하고, 이를 통해 수신자만이 암호문을 바탕으로 본문을 해석할 수 있도록 암호화하는 방식이다. 고전적인 대칭키 암호화의 예시를 하나 들자면, 스키테일 암호의 키는 막대기가 될 것이다.
Shannon Cipher
암호학은 수학이다. 즉, 대상들이 명확히 수학적으로 정의되어야 한다. Shannon Cipher은 대칭키 암호화를 수학적으로 명확히 정의한 개념이다. Shannon Cipher은 두 함수 $E$와 $D$, 세 집합 $C$, $K$, $M$으로 이루어진다.
$K$는 key들의 집합이다. $C$는 가능한 암호문의 집합이며, $M$은 암호화의 대상이 되는 본문의 집합이다.
$E$는 암호화 함수로, key $k$와 plaintext $m$을 입력으로 받아 ciphertext $c$를 반환한다.
$D$는 복호화 함수로, key $k$와 ciphertext $c$를 입력으로 받아 plaintext $m$을 반환한다.
적절한 암호가 되기 위해선, 복호화 결과가 동일해야 한다 : 즉 $D(k, E(k, m)) = m$이어야 한다.
xor, 치환 등의 암호화가 예시가 될 수 있다.
Perfect Security
암호가 '안전하다' 라는 것을 수학적으로 어떻게 입증할까? key 값을 모르는 공격자의 입장에서 보았을 때, 주어진 ciphertext $c$를 바탕으로 본래의 plaintext $m$을 유추해내기 힘들면 안전할 것이다. 유추해내기 힘들다는 것은 무엇을 의미할까?
주어진 $c$에 대해, $c$가 plaintext $m_1, m_2$ 중 하나의 암호화라 하자. $E(k, m_1) = c$인 k와 $E(k, m_2) = c$인 k의 비율이 7 : 3이라고 하면, 상대적으로 $m_1$이 더 본문과 가까울 것이라고 유추할 수 있다. 이를 통해, '안전하다'의 수학적 정의를 도출해낼 수 있다.
PERFECT SECURITY
k를 $K$에서 uniformly distributed하게 뽑은 random 변수라고 생각하자. 다음을 만족하면 암호화는 perfect secure하다.
for all $m_0, m_1 \in M$, and all $c \in C$, $Pr[E(k, m_0) = c] = Pr[E(k, m_1) = c]$
이는 앞서 언급한 것처럼 임의의 plaintext에 대해 가능한 key $k$의 비율이 동일한 경우이다. 이러한 환경에서, $c$만을 알 때 해당 암호화 알고리즘 방식을 알더라도 perfect secure한 경우라면 절대 plaintext $m$을 유추할 수 없다 : 어떤 plaintext건 본문일 확률이 동일하기 때문이다.
Shannon's theorem
xor과 같은 암호화 기법은 perfect security이다. 세상 모든 암호화 기법이 perfect secrue하다면 왜 매번 특정 암호의 취약점이 발견되었다는 소식이 들려올까? 사실 그 암호들이 perfect secure하지 않고, 할 수도 없기 때문이다.
Shannon's theorem
Shannon cipher이 perfect secure하다면, $|K| \ge |M|$이다.
pf) $|K| \lt |M|$일 때 불가능함을 보이자. any message $m_0$과 any key $k_0$을 잡고, $E(k_0, m_0) = c$라 하자. 또한, $c$가 될 수 있는 message 집합 $S$를 다음과 같이 정의하자.
$S = {D(k_1, c) | k_1 \in K}$
자명히 $|S| \le |K|$이므로 $|S| \lt |M|$. 따라서 Exist $m \in M - S$가 존재한다. 이 $m$에 대해 $Pr[E(k, m) = c] = 0$이므로 모순.
이러한 Shannon's theorem에 의해, perfect secure을 얻기 위해선 message의 길이만큼 key의 길이가 길어야 한다. 즉 우리가 1GB 파일을 암호화하기 위해 1GB의 키를 공유해야 한다는 것이다. 이러한 현실적 불가능으로 인해, 두 가능성이 모두 같은 것이 아닌 작은 차이만을 가지도록 하는 수정된 security 정의를 도입한다.