코딩 더 매트릭스 - 1장 함수 (2)

필립 클라인의 저서 코딩 더 매트릭스 1장 함수 중 확률

---

1. 확률분포를 되새겨 봅니다.
2. 좋은 암호 체계와 확률분포의 관계를 알아봅니다.

---

확률분포

확률은 가능성의 수학적 개념을 의미하기 위해 사용합니다. 어떤 실험을 한다고 할때 그 결과는 실험 횟수마다 다를 수 있습니다. 이때 확률 분포는 실험결과를 정의역의 원소로서, 각각의 결과의 확률을 공역의 원소로서, 실험결과를 확률에 매핑하는 함수로 볼 수 있습니다. 확률 분포 함수 $Pr(x)$ 이 유한한 정의역 $\Omega$ 에서 음수가 아닌 실수의 집합 $\mathbb{R}^+$ 로 매핑하는 함수라면 다음과 같은 식을 쓸 수 있습니다. $\sum_{\omega \in \Omega}Pr(\omega) = 1$

완벽한 비밀 유지

확률 분포를 단순한 암호체계에 적용해 봅시다. 독일의 한 교수 커크호프는 암호체계의 안정성은 암호체계 자체의 비밀유지에 의존해서는 안되며 오직 사용된 키값의 비밀 유지에만 의존해야 한다는 원칙을 말했습니다. 원칙에 유의하며 밥과 앨리스의 암호 통신을 살펴봅시다. 앨리스와 밥은 0 또는 1로 간단하게 의사를 주고받습니다. 통신 수단은 손전등을 이용한 시각신호로 생각해봅시다. (짧게 깜빡이면 0, 길게 깜빡이면 1) 앨리스와 밥은 서로의 의사를 암호화하기 위해 다음과 같은 암호체계를 만들었습니다.

$p$	$k$	$c$
0	$\clubsuit$	0
0	$\heartsuit$	1
0	$\spadesuit$	1
1	$\clubsuit$	1
1	$\heartsuit$	0
1	$\spadesuit$	0

앨리스와 밥은 집합 $\{\clubsuit, \heartsuit, \spadesuit \}$ 에서 랜덤하게 $k$를 선택합니다. $k$는 둘이 알아야 하지만 그것을 비밀로 유지해야 할 키값입니다. 키값을 사용하여 평문 $p$를 암호화해야 할 필요가 있을 때 위의 표를 참고하여 암호문 $c$를 얻습니다. 하지만 이 방식은 좋지 않습니다. 예를 들어 평문이 0이라고 가정해 보면 암호문은 1/3 의 확률로 0이 2/3 의 확률로 1이 됩니다. 따라서 $c = 1$일 가능성이 두 배 높습니다. 키값을 몰라도 $p = 0$이 될 가능성을 추정할 수 있습니다. 아래 표는 보다 좋은 암호체계 입니다.

$p$	$k$	$c$
0	$\clubsuit$	0
0	$\heartsuit$	1
1	$\clubsuit$	1
1	$\spadesuit$	0