CTF 암호학을 위한 기초적 확률 지식 / Basic Knowledge about Probability for CTF

이번 포스트는 암호학을 배우면서 간단하게 접한 확률에 관한 몇 가지 지식을 소개하고자 한다.

---

1. Birthday Paradox

Birthday Paradox, 즉 생일의 역설은 이후 소개드릴 내용에 비해 잘 알려져 있는 사실이다. 이는 "23명이 모여있으면 그 중 생일이 같은 두 사람이 존재할 확률이 약 50%이다"라는 내용으로 흔히 소개되어 처음 접하면 "생각보다 많이 적네?" 싶은, 조금은 신기한 사실이다.

CTF에서는 몇 가지의 분류가 존재하는 값을 출력하는 확률적 알고리즘에 대해 같은 분류에 속하는 두 가지 출력을 얻고자 할 때 종종 사용된다. md5 해시의 값을 정수로 바꾸어 65537로 나눈 나머지가 같은 두 원본 텍스트 쌍을 찾는 경우 같은 예시가 존재한다.

물론 확률에 기반한 시행이므로 평균적으로 빨리 시행됨을 알려주는 것이므로 시행 시간에는 편차가 존재할 수 있다.

• Recommend to read : 위키백과 - 생일 공격

---

2. Frequency of Prime number

$x$ 이하의 소수의 개수를 의미하는 소수 계량 함수 $\pi(x)$에 대해 $\displaystyle\lim_{x\rightarrow\infty} \frac{\pi(x)}{x/\ln x}=1$이 성립한다.

이는 Big-Theta notation의 정의 $f(x)\in \Theta(g(x)) \Leftrightarrow 0<\displaystyle\lim_{x\rightarrow\infty} \frac{f(x)}{g(x)}<\infty$에 따라 $\pi(x)\in \Theta(x/\ln x)$라는 의미이기도 하며, $x$ 이하의 수를 랜덤하게 골랐을 때 그 수가 소수일 확률이 $\frac{\pi(x)}{x}\approx\frac{x/\ln x}{x}=\frac{1}{\ln x}$임을 의미하기도 한다.

CTF에서는 $n$-bit 정수를 랜덤하게 뽑을 때 소수일 확률이 $1/n$이며, 따라서 uniform하거나 그렇다고 추정되는 $n$-bit number generator을 반복 실행하여 소수를 얻을 실행 횟수의 기댓값이 $n$임을 알려주어 brute force 풀이의 근거가 된다.

대표적인 사용 예시로는 소수인 MD5 해시값을 찾는 경우가 있다. MD5는 32byte=256bit를 출력하는 해시 알고리즘이므로 평균적으로 $\ln{255}\approx177$개의 해시값을 구하면 소수인 MD5 해시값을 얻을 수 있다.

• Recommend to read : 위키백과 - 소수 계량 함수

---

3. Probablity of $\gcd(n,m)=1$

임의의 두 자연수 $n,m$에 대해 두 수가 서로소일 확률을 $P$라고 하자. 임의의 두 자연수의 최대공약수가 $d$일 확률을 $P(d)$라고 하자. 이때, 임의의 두 자연수는 자연수인 최대공약수를 가지므로 $\displaystyle\sum_{d=1}^{\infty} P(d) = 1$이 성립한다.

또한 어떤 두 자연수 $n,m$의 최대공약수가 $d$라 하면 $gcd(n/d,m/d)=1$이다. 바꿔말하자면 두 서로소인 자연수 $a,b$를 이용하여 $da,db$라는 최대공약수가 $d$인 두 자연수 쌍을 만들 수 있다. 임의의 자연수를 고를 때 $d$의 배수일 확률은 $1/d$이므로 $P(d)=P\times(1/d)\times(1/d)=P/d^2$이다.

즉, $\displaystyle\sum_{d=1}^{\infty} P(d) = \sum_{d=1}^{\infty} P/d^2 = P\times\sum_{d=1}^{\infty} 1/d^2 = \frac{\pi^2}{6}P = 1$이다. 따라서 $P=\displaystyle\frac{6}{\pi^2}$이다.