이것은 문서의 이전 버전입니다!


The Magic Words are Squeamish Ossifrage

"마법의 주문은 까다로운 수염수리이다" 정도로 해석되는 문장. 유명한 암호문의 해답이다.

이 문장의 원본은 RSA-129라 불리는, RSA시큐리티가 (Martin Gardner를 통해) 1977년 8월 사이언티픽아메리칸에 게시한 퍼즐에 등장하는 숫자로, 이 숫자는 두 커다란(각각 64, 65자리) 소수의 곱인데 암호문을 풀기 위해서는 원래 숫자로부터 소인수를 얻어 와야 하기 때문에 효율적인 소인수분해 알고리즘이 필요한 퍼즐이었다.

기술의 발전으로 지금은 이 정도의 숫자를 소인수분해하는 데 큰 어려움은 없지만, 문제가 풀린 1994년에만 해도 이 암호를 푸는 데 1400대의 컴퓨터가 필요했을 정도로 쉽지는 않은 문제였다. (초창기 그리드컴퓨팅의 예제라 할 만 하다.) 퍼즐이 풀린 뒤 상금 100달러자유 소프트웨어 재단으로 갔다고 한다.

퍼즐의 내용

먼저 세 개의 숫자 r, m, e = 9007을 가정한다. 첫 두 개의 숫자는 다음과 같은 큰 숫자이다.

r =                   1 1438 1625 7578 8886 7669 2357 7997 6146
    6120 1021 8296 7212 4236 2562 5618 4293 5706 9352 4573 3897
    8305 9712 3563 9587 0505 8989 0751 4759 9290 0268 7954 3541

m =                     9686 9613 7546 2206 1477 1409 2225 4355
    8829 0575 9991 1245 7431 9874 6951 2093 0816 2982 2514 5708
    3569 3147 6622 8839 8962 8013 3919 9055 1829 9451 5781 5154

여기서 m은 원문 dRSA 암호 체계로 암호화한 암호문으로, 사용된 공개키는 (r,e)이다. 즉 m \equiv d^e \pmod{r}이 성립한다. 문제는 이 세 개의 숫자만 가지고 d를 알아 내라는 것으로, d는 영문으로 된 문장을 숫자1)로 표현한 것임이 알려져 있고 r은 두 소수 pq의 곱임이 알려져 있다.

비밀키 (p,q,x)는 알려져 있지 않기 때문에 이들의 값을 수동으로 계산해야 하는데, 사실 xex \equiv 1 \pmod{\phi(r) = (p-1) (q-1)}로 계산할 수 있으므로 (확장유클리드알고리즘을 쓴다) pq를 알아 내는 게 관건이었다. 실제로 풀린 비밀키는 다음과 같으며:

p =                                         3490 5295 1084 7650
    9491 4784 9619 9038 9813 3417 7646 3849 3387 8439 9082 0577

q =                                       3 2769 1329 9326 6709
    5499 6198 8190 8344 6141 3177 6429 6799 2942 5397 9828 8533

x =                   1 0669 8614 3685 7802 4442 8687 7132 8920
    1547 8070 9906 6339 3786 2801 2262 2449 6631 0631 2591 1774
    4708 7334 0168 5974 6230 6553 9685 4451 3277 1090 5360 6095

평문과 그에 대응되는 영문 문장은 다음과 같다. (_은 공백을 나타낸다.)

d =                       20 0805 0013 0107 0903 0023 1518 0419
    0001 1805 0019 1721 0501 1309 1908 0015 1919 0906 1801 0705
                           T  H E  _ M  A G  I C  _ W  O R  D S
     _ A  R E  _ S  Q U  E A  M I  S H  _ O  S S  I F  R A  G E

《썸머워즈》

2009년 극장 애니메이션인 《썸머워즈》에서 정확히 똑같은 암호문이 나오는데, 작중 모듈러연산에 대한 언급도 나오고 하는 것으로 봐서 제작자들은 OZ의 암호 시스템이 RSA를 기반으로 한다고 말하고 싶은 것 같다. 물론 여기에는 심각한 문제가 있으니, RSA를 날로 쓰는 경우는 거의 없으며 (보통 PKCS1을 사용해서 패딩도 하고 뭣도 하고 한다) 더군다나 암호화된 데이터라도 그대로 내보내는 것은 자살행위에나 다름이 없는 것이다.2)

작중 주인공은 하룻밤만에(…) 암호를 풀어 낸 뒤 답장을 보내던 중 실수로 (RSA에서 계산 과정에 실수가 났다면 차이가 매우 커진다는 걸 감안한다면) 마지막 한 글자를 e에서 q로 틀려서 잘못된 답을 보내게 된다. 그런데 RSA-129가 아무리 풀렸다고 하더라도 이걸 실제로 풀어 내는 과정이 인간이 하룻밤만에 할 수 있는 정도의 양은 아니라고 본다.3) 거의 클라이막스 부분에서 그 짓을 또 다시 두 번, 그것도 두번째에는 암산으로 하는 건… 그냥 허구 내지 일 뿐이고.

1) 공백은 00, A~Z까지는 01부터 26까지로 변환해서 그걸 죽 이어 붙인 십진수 표기
2) 예를 들어 유닉스 계열의 passwd 파일은 원래 아무나 보이면서 암호화된 암호를 담고 있었지만, 이게 너무 자주 뚫리자 후에 관리자만 볼 수 있는 shadow로 옮겨 갔다.
3) 보통 이 정도 크기가 되면 quadratic sieve나 rational sieve 계열의 알고리즘을 써야 하지만 이건 인간이 할 수 있는 수준이 아니다. 인간이 할 수 있는 최선은 rho알고리즘 정도인데 이 알고리즘은 모든 숫자에 대해 동작하진 않고, 하나 하나 나누는 방법 역시 페르마수 F6의 소인수분해를 생각하면 그다지… 실제로 이 숫자의 경우 스무자리밖에 안 되고, 그마저도 작은 소인수가 이십만 정도 밖에 되지 않았으나 손으로 작업하는 데 몇 년이 걸렸다;

도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2011-05-30 18:25 | 외부 편집기