MCMC 암호 뽀개기

HaugMCMC_BayesModelling.pdf

다음은 MCMC를 이용하여 암호를 디코딩하는 예를 한번 보여 주겠습니다. 경향신문에 “인공지능으로 사멸 위기 언어 보존한다”하는 기사가 있어서 거기에 나오는 내용을 이해하는데 도움이 될까 씁니다.

 

 

이 예제는 위의 첨부한 파일에 있으니까 자세한 내용은 이 파일을 참조하시면 됩니다.

 

실제로 있었던 이야기인 것 같습니다.

 

한 교도소에 근무하는 심리학자가 죄수가 쓴 암호문을 가지고 스탠포드 대학 통계 컨설팅 연구소를 찾아와 이 암호문을 좀 풀어 달라고 한 모양입니다. 암호문의 내용은 다음과 같습니다.

    

이 문제를 MCMC를 이용하여 풀었습니다. 방법은 다음과 같습니다. 영어의 한 문자가 나올 확률은 오로지 이전의 문자에 영향을 받는다고 가정을 했습니다. 즉 마코프 체인을 가정한 것이죠.

 

그 다음 ‘전쟁과 평화’라는 소설에서 이 마코프 체인의 확률을 구합니다. 그냥 빈도를 구해서 확률로 바꾸면 되는 것이죠.

 

즉 Pr(b|a): a 문자가 나온 후 b 문자가 나올 확률,

Pr(c|a): a 문자가 나온 후 c 문자가 나올 확률, ...

Pr(a|z): z 문자가 나온 후 a 문자가 나올 확률

 

문자 외에 blank, 부호 이런 것 다 생각하면 한 30*30 전이확률 행렬를 만들 수 있습니다.

 

 

그 다음 암호 디코딩 하는 함수를 생각해야 합니다. 즉 위의 암호문의 이상한 문자를 기호1, 기호2, 기호3,... 이렇게 표시한다고 하면 디코딩 함수는 기호를 영어 문자와 매칭시키는 방법이 됩니다.

 

디코딩 함수1=(기호1=a, 기호2=b, 기호3=c, 기호4=d...)

디코딩 함수2=(기호1=b, 기호2=a, 기호3=c, 기호4=d... )

디코딩 함수3=(기호1=c, 기호2=b, 기호3=a,...)

 

이렇게 디코딩 하는 함수, 즉 암호문의 기호와 영어 철자와 일치시키는, 즉, 매칭시키는 함수는 수도 없이 많이 나올 수 있습니다. 여기서 우리는 전쟁과 평화라는 소설에서 나오는 정보를 가지고 가장 가능성이 높은, 즉 확률이 높은 디코딩 하는 함수를 구하는 것이 목적입니다.

 

그럼 각 디코딩 함수에서 확률은 어떻게 구해지는가?

 

예를 들어 암호문이 (기호1, 기호2, 기호1, 기호3, 기호4, 기호2, 기호2,...) 이렇게 되어 있으면

 

디코딩 함수1=(abacdbb...) 이렇게 되고 디코딩 함수2=(babcdaa...) 이렇게 되겠죠.

 

그럼 디코딩 함수1의 확률은 Pr(a)*Pr(b|a)*Pr(a|b)*Pr(c|a)*Pr(d|c)*Pr(b|d)...

 

디코딩 함수2의 확률은 Pr(b)*Pr(a|b)*Pr(b|a)*Pr(c|b)*Pr(d|c)...

 

뭐 이렇게 될 겁니다. 그래서 구한 확률이 디코딩 함수1이 함수 2보다 높으면 디코딩 함수1이 더 바람직한 디코딩 함수이고 함수 2가 함수1보다 확률이 높으면 함수2가 더 바람직한 디코딩 함수가 될 겁니다.

 

이렇게 해서 가장 확률이 높은 디코딩 함수를 찾으면 됩니다. 그래서 나온 결과를 보고 약간 수정을 하면 됩니다. 즉 함호문을 해석하니 LOVI가 나왔으면 이건 LOVE로 수정을 해서 다시 한번 이 정보를 가지고 한번 더 위의 작업을 하면 될 겁니다.

 

그런데 문제는 디코딩 하는 함수가 너무 많다는 것이죠. 그래서 모든 디코딩 하는 함수를 다 고려해서 작업하는 것은 무리라는 것이죠. 물론 컴퓨터가 수백만개가 있다면 무식하게 해도 됩니다. 병렬 알고리즘이니까요. 그러나 이렇게 우리의 자원이 풍부하지 않죠.

여기서 MCMC 방법, 정확하게 이야기하면 Metropolis 방식과 비슷한 방식이 등장합니다.

    

 

먼저 이 작업을 하기 전에 주변체제(Neighborhood system)를 구축해야 합니다. 이 개념은 매우 중요합니다. 주변은 우리가 중고등학교 때 배운 개구간(open set)과 같은 개념이라 생각하시면 됩니다. 해석학에서 연속이나 수렴 개념들 사실 다 이 개구간 개념을 이용해서 정의하는 것입니다. 또 위상수학의 위상(topology)의 정의가 개구간(open set)의 모임을 이야기하고, 이 개구간을 가지고 개념화 할 수 있는 성질을 공부하는 것이 위상 수학입니다.

 

하여간 이쪽 공부에서는 이 주변체제가 매우 중요한 개념입니다.

 

어떤 디코딩 함수 f가 있다고 하죠. 그럼 이 f의 주변은 디코딩하는 방법에서 두 개만 위치를 살짝 바꾸는 것이라 하죠. 즉

 

f가 디코딩 함수1이라고 하죠. 즉 f=(기호1=a, 기호2=b, 기호3=c, 기호4=d...)는 이렇게 되죠.

 

그럼 이 f의 주변(neighborhood) 디코딩 함수는

 

g1=(기호1=b, 기호2=a, 기호3=c, 기호4=d...),

g2=(기호1=c, 기호2=b, 기호3=a, 기호4=d...),

g3=(기호1=d, 기호2=b, 기호3=c, 기호4=a...),

g4=(기호1=a, 기호2=c, 기호3=b, 기호4=d...),

 

이렇게 매칭하는 방법에서 2개만 살짝 바꾸는 방법을 생각해도 상당히 많은 디코딩 함수가 생겨납니다. 이 N(f)={g1, g2, g3, g4, g5,...}을 디코딩 함수 f의 주변이라 합니다. 모든 디코딩 함수에 대해 생기는 이 주변을 다 모은 것을 주변체제(Neighborhood System)이라 생각하시면 됩니다.

 

 

그럼 이 문제는 다음과 같이 하면 해결할 수 있습니다.

 

1. 임의의 디코딩 함수 f를 설정한다.

 

2. 이 임의로 설정한 디코딩 함수 f의 주변 N(f)에서 하나의 디코딩 함수 g1을 뽑는다.

 

3. 만약 새로 뽑힌 디코딩 함수 g1의 확률이 원래 디코딩 함수 f의 확률보다 크면 이젠 g1을 선택한다. 이 g1을 가지고 주변 N(g1)에서 새로운 디코딩 함수 h1를 생성해서 g1의 확률과 h1의 확률을 비교한다.

 

4. 만약 g1의 확률이 f보다 낮아도 일정 확률 p를 가지고 g1을 선택한다. 즉 (1-p)의 확률로 f를 계속 유지한다. 만약 g1이 선택되면 위의 3의 방식으로 N(g1)에서 새로운 h1을 뽑아 비교하고, f가 계속 유지되면 f의 주변 N(f)에서 새로운 g2을 뽑아 다시 f와 g2의 확률을 비교하여 선택한다.

 

위의 방식을 계속하여 확률값이 별로 개선되지 않으면 최종 디코딩 함수로 선택한다.

 

그래서 여기서 특징은 2가지가 있습니다.

 

1) 전체 디코딩 함수를 생각하지 않고 특정 디코딩 함수 하나를 설정하고 이 함수 주변에서 괜찮은 놈이 없나 찾아보고 있으면 거기로 점프해서 또 거기서 또 주변에 괜찮은 놈이 없나 찾아 보고 이런식으로 local search를 한다는 점입니다.

 

2) 위 방식에서 특이한 점은 4입니다. 즉 새로 뽑힌 디코딩 함수 g1이 원래 디코딩 함수 f보다도 확률값이 낮은데도 g1을 선택한다는 것이죠. 이렇게 하는 이유는 local maximum에 빠지는 것을 막기 위해서입니다. 이건 다음에 여행하는 세일즈 맨 문제에서 조금 자세히 설명하겠습니다.

 

 

 

g1이 f보다 확률값이 낮아도 확률 p 값으로 g1을 선택한다고 하였는데 이것 하는 방법은 매우 쉽습니다. p값이 0.35이라고 하죠. 그럼 0과 1 사이에 난수를 하나 뽑습니다. 이 난수 x가 0.35보다 작으면 새 디코딩 함수 g1을 선택하고 x가 0.35보다 높으면 이전 디코딩 함수 f를 계속 유지해서 알고리즘을 계속 실행합니다.

 

 

위 방법은 앞의 글에서 이야기한 여행하는 세일즈맨 문제를 푸는 방식과 거의 동일합니다. Metropolis 방식은 Gibbs 분포를 이용하고 이 분포에서 온도 T를 천천히 낮추는 annealing 방식을 사용합니다. 그리고 p 값도 천천히 낮추고요.

 

 

만약 우리가 비밀번호를 인간이 자신도 모르게 약간의 규칙성을 가지고 사용한다면 비밀번호의 약간의 정보만 있으면 위의 방식을 응용하면 암호를 무식하게 brutal breaking 하는 방법보다 훨씬 빨리 디코딩을 할 수 있을 겁니다.

 

 

위의 예는 영어 철자의 경우인데 이 철자를 단어를 바꿔서 이용할 수 있을 겁니다. 번역할 때도 사용할 수 있을 것이고요. 이게 경향신문에서 나온 기사 내용입니다. 물론 단어를 사용할 때는 단어가 어마어마하게 많기 때문에 전이 확률 행렬의 크기도 어마어마하게 커겠죠.

 

 

주변체제는 매우 중요한 개념입니다. 마코프 랜덤 필드에서 어떤 확률변수 X(k)는 X(k)의 주변 N(X(k))에만 영향을 받습니다. 그래서 Gibbs Sampler에서

 

Y(k) ~ f(X(k)|X1, X2,..., X(k-1), X(k+1), ,,,X(n))에서 뽑아야 하는데 이렇게 하지 않고

 

Y(k) ~ f(X(k)| N(X(k))

 

이렇게 X(k)의 주변에 해당하는 변수들의 조건부 확률분포만 구하면 되는 훨씬 간단한 조건부 확률분포에서 Gibbs Sampler를 할 수 있다는 이야기입니다.

 

 

이건 흔히 DAG이라는 불리는 Bayesian Belief Network 모형에서 Gibbs Sampler를 이용할 때 똑같이 적용될 수 있습니다.

 

인공지능에서 Graph 이론 배우는 분을 위해서 간단히 언급했습니다.

 

 

 

 

 

 

 

 

 

 

 

HaugMCMC_BayesModelling.pdf

1.3MB

HaugMCMC_BayesModelling.pdf

1.3MB