이 포스팅은 CourseraStanford University Cryptography I - Dan Boneh 강의를 바탕으로 제작되었습니다. Cryptography를 공부하시고자 하는 분들을 위해 조금이나마 기여할 수 있을까하여 포스팅을 지속하기로 결정하였습니다. 

이번 강좌는 본래 04강과 05강으로 이루어져있으나, 동일한 주제를 다루고 있기에 끊지않고 하나의 포스팅으로 연결해서 작성합니다.


지난 세월동안 사용되었던 많은 암호기법들이, 시간이 흐를수록 결코 안전하다고 말할 수 없다는 것이 속속들이 밝혀졌습니다. 그러한 이유로 현대의 암호학에서는 새로운 암호기법을 설계할 때 굉장히 엄격하고 정밀한 방식으로 보안성을 증명해내야만 그 권위를 인정하고 있습니다. 이러한 과정에서 사용되는 도구가 바로 ‘이산 확률(Discrete Probability)'입니다. 이번 강좌에서는 이산확률에 대한 전체적인 overview를 진행합니다. 이 강좌에서 모두 다루지 못하는 세부사항은 Wiki Books를 참조하시면 좋습니다. 

이산확률에서 사용되는 기본적인 용어 정리부터 시작하겠습니다. 무한한 집합 U를, 0과 1의 조합을 가지는 n - bit의 스트링이라고 정의하겠습니다. 예를들어 {0,1}^2가 있다면 2비트로 된 0과 1의 원소 집합을 떠올리시면 됩니다. {00, 01, 10, 11} 이 되겠지요? 원소의 개수는 4개입니다. n개의 bit를 가지면서 각 bit가 2가지의 경우의 수를 갖기 때문에, 집합의 원소의 개수는 2^n 입니다.

그리고 여기에서 사용되는 확률 분포(Probability distribution)를 P로 정의하겠습니다. 모든 P(x)의 확률을 더하면 1이 되어야만 합니다. 즉, 확률에서 빈틈이 생기는 경우의 수는 없다고 가정합니다. 


자주 사용되는 두가지 예시를 보여드리겠습니다. 

첫째, 균등 분포(Uniform distribution)은 집합 U에 속한 모든 x가 동일한 P(x) 값을 가지는 경우를 말합니다. {00, 01, 10, 11}의 예시에 따르면 각 원소들이 동일하게 1/4의 확률을 가지는 것입니다. 즉, P(x) = 1 / (U의 크기) 가 됩니다. 


둘째, 점 분포(Point distribution)은 집합 U에 속한 특정 x의 P(x)만 1의 확률을 가지고, 그외 나머지는 모두 0의 확률을 가지는 경우를 말합니다. {00, 01, 10, 11}의 예시에 따르면 {10}만 1이고, 나머지는 항상 0의 확률을 갖게되는 경우입니다. 이를통해 특정한 하나의 원소만을 집어내고 싶을 때 점 분포가 유용하게 사용됩니다. 


다음으로 Distribution Vector를 설명드리겠습니다. 이는 각각의 확률분포 P(x)를 일련의 값들로 묶어서 일종의 배열(array) 또는 벡터(vector)로 표현한 것입니다. 3bit의 경우라면 총 경우의 수는 8가지인데, 이를 ( P(000), P(001).. P(111)) 로 표현한 것과 같습니다. 이렇게 하여 컴퓨터로 처리할 때 8개의 원소를 가지는 배열로써 각각의 확률에 대한 실수(Real Number)값을 할당하면 됩니다.

다음으로 정의할 내용은 사건(Event)입니다. 사건이란 표본공간의 부분집합을 의미합니다. 전체집합 U의 일부분인 A를 정의할 때 특정한 조건을 줄 수 있습니다. 예를들어 U = {0,1}^8이라면, 8bit 길이의 0, 1을 배치할 수 있을 것입니다. 이 때 lsb2(x) =11 이라함은 좌측 가장 끝(least significant bits)비트 2자리가 11인 경우를 뜻합니다. 확률이란 기본적으로 전체 경우의 수 대비 해당 이벤트로 계산되므로, 전체 경우의 수는 2^8 = 256이고, 끝의 2자리를 1로 고정한 경우 나머지 경우의 수는 2^6이 됩니다. 따라서 확률은 2^6 / 2^8 = 1/2^2 = 1/4 이 되겠습니다.

다음은 확률의 Union bound입니다. 각 이벤트의 확률의 덧셈을 계산하는 것과, 이벤트의 합집합의 확률을 계산하는 것에서 약간의 차이점이 있습니다. 왜냐하면 교집합(intersection)이 중복되어 계산되기 때문입니다. 때문에 교집합이 없는(disjoint) 배반사건의 경우에서는 Pr(A) + Pr(B) = Pr(A U B) 가 성립하고, 보통의 경우 합집합이 더 작으므로 부등호를 사용해 표현하는 것이 일반적입니다. 따라서 Pr[lsb2(x) = 11 or msb2(x) = 11] 은 이것을 각각 계산한 1/4 + 1/4 보다 작거나 같습니다.

다음으로 설명드릴 개념은 확률 변수(또는 랜덤변수, Random variables)입니다. 확률변수 X란, U -> V로 매핑시킵니다. 예를들어 X(y) = lsb(y)라 할때 x=0과 x=1이 가능하며, 이로인해 U를 각각의 V집합으로 매핑시킬 수 있습니다. 집합 U에서 어떠한 원소든지 무작위로 선택하더라도 V집합의 0 혹은 1에 1/2의 확률로 모두 소속됩니다.

균등 확률 변수(Uniform Random Variable)는 위에서 살펴본 Uniform distribution을 기억하시면 이해가 쉽습니다. Pr[r=a] 의 확률이 모두 1 / | U| 로 같은 경우입니다. 어떤 확률변수를 갖더라도 모두 같은 값을 가집니다.

예제를 살펴보겠습니다. r이 {0,1}^2인 uniform random variable입니다. 이때 X = r1 + r2라면, Pr[X=2]는 무엇일까요? uniform이라고 했으므로, {00, 01, 10, 11} 이 모두 1/4로 같은 확률을 가질 것입니다. 그렇다면 이때의 X는 각각 0, 1, 1, 2가 되므로 중복원소를 제거한 {0, 1, 2}가 될 것이며, 확률로는 각각 1/4, 1/2, 1/4 이 될 것입니다. 따라서 Pr[X=2] 는 1/4 이 정답입니다.

다음으로 소개드릴 것은 확률적 알고리즘(Randomized algorithms)입니다. 이를 이해하기위해서는 먼저 결정론적(Deterministic) 알고리즘을 설명드리겠습니다. 결정론적 알고리즘은 예측한 그대로만 작동합니다. 어떠한 입력 m이 들어왔을때 그 결과가 항상 동일한 y=A(m)를 도출해냅니다. 


반면에, 확률적(Randomized) Algorithms에서는 m과 함께 r이라는 값이 함께 input으로 작용합니다. 이 r값은 수행할 때마다 매번 다르게 생성되므로, 같은 m값을 입력했더라도 매번 다른 y 값이 도출됩니다. 


정리하자면 A라는 함수에 m을 input으로 넣되, k라는 확률변수를 적용시키는 것이고, 이것을 암호학적인 관점으로 해석하자면 m이라는 메시지를 암호화할 때 k라는 key를 사용하는 것과 같습니다. 이렇게하면 동일한 메세지에 대해서도 다른 늘 다른 결과값을 보여주기 때문에 역추론이 어렵게됩니다.

독립(independent) event에 대해 설명하겠습니다. 독립사건이란 서로 다른 사건 A와 B가 서로가 일어날 확률에 영향을 주지 않는 경우를 뜻합니다. 이때 A의 확률과 B의 확률을 곱하면, A와 B가 동시에 일어날 확률과 같습니다.예를들어 {00, 01, 10, 11}이 전체 집합 U이고, X는 첫째자리, Y는 마지막자리라고 가정해봅시다. 이때 첫째자리가 0일 확률 Pr[X=0] 과 끝자리가 0일 확률 Pr[Y=0]은 각각 1/2 이며, 이를 곱하면 1/4이 됩니다. 이는 전체에서 {00}인 사건의 확률이 1/4인 것과도 일치합니다.

다음으로는 XOR에 대한 설명입니다. XOR는 암호학 전반에 걸쳐 중요하게 다루어지므로, 반드시 숙지하셔야합니다. XOR의 진리표(Truth table)은 좌측과 같습니다. 쉽게 이해하자면, 입력값 X와 Y의 값이 같으면 결과는 0, 다르면 1이 됩니다. 오른쪽의 예제를 풀어볼까요? 그렇다면 정답은 1101101이 됩니다.

Y가 {0,1}^n의 확률변수이고, X 또한 그러하며 각각 독립인 경우라 할 때 Y xor X를 한 결과 또한 반드시 {0,1}^n에 대해 균등(uniform)합니다. 증명은 위를 참조하세요. 암호학에서 XOR가 중요한이유가 바로 위와같은 성질 때문입니다.

생일 역설(birthday paradox)란 고전적인 확률 문제입니다. 임의의 사람이 특정한 모임에 모였다고 했을 때, 그 중에 생일이 같은 두사람이 존재할 확률을 구하는 것입니다. 생일의 가능한 가짓수는 365개(윤년을 포함하면 366)이므로 만약 367명 이상의 사람이 모여있다면 비둘기집 원리(Pigeonhole principle)혹은 디리크렛의 상자 원리(Dirichlet’s box principle)에 따라 생일이 같은 두 명이 반드시 존재할수밖에 없습니다. 공식으로 나타내면 n=1.2 * |U|^1/2 이며, 생일 문제를 수치적으로 계산해보면 22.9259.. 즉, 23명 이상만 모여도 그 안에서 생일이 같은 사람이 존재할 확률은 1/2을 넘습니다. (자세한 증명에 관한 링크, 1.2 라는 숫자는 sqrt(2*ln2)에서 온 것입니다.)


(동일한 원리로, U = {0,1}^128이라면, 2^64번만 샘플링했을때  그 결과가 같은 쌍이 존재할 확률은 50%를 육박하게 될 것입니다. GUID 등을 배분하는 문제에서 충돌확률이 50%라면 매우매우매우 높은수치여서, 실무에서 사용하기 곤란할 정도가 됩니다.)

위의 그래프는 백만명에 대한 생일 충돌 통계 샘플입니다. 사람 수가 1300명정도만 되어도 이미 확률이 50%를 넘어서며, 2100명정도 모였을때는 90% 확률을 보여줍니다. 인원이 많을수록 빠르게 확률이 1에 수렴하는 것을 보실 수 있습니다. 이 생일역설 문제는 잘 기억해두시면, 추후에 해쉬함수 등의 분야에서 다루게 될 것입니다.



여기까지 확률변수에 대한 설명을 마치겠습니다. 다음시간부터는 암호학 시스템에 대한 첫 수업을 진행하도록 하겠습니다.

CPUU님의 창작활동을 응원하고 싶으세요?