[특강] RSA 예시

바로 전 글에서 살펴본 RSA 암호화 기법에 따른 실제 예시를 살펴볼 것이다. 문제에서 사용된 숫자는 꽤 널리 알려진 모양이다. 구글에 치니까 어떤 책에 실려 있기도 했다. 이번에 살펴볼 예시는 페이스북 수학 그룹에 Min Jang이라는 분이 쓴 글에서 업로드된 jpg 파일에 기초했으며, RSA 암호문을 복호화해볼 것이다. 원칙적으로 RSA 암호 기법을 깨부순 것은 아니고 그냥 하나의 암호문을 복호화 해보았다. 이것이 "숙제"라는 점을 이용해서 말이다...

---

P와 W를 살펴보면 그냥 숫자를 나타내는 방법을 알려줬을 뿐, 암호화 자체에 도움이 되는 제약 조건은 없다는 것을 알 수 있다. 단순히 36진법으로 나타낸 W를 10진법으로 고쳐써서 P로 나타낼 수 있다는 것만 알 수 있다. x0가 0은 아니므로 정답이되는 W는 000000.....00000X 이런 구조는 아니라는 것도 있다. 숙제니까 당연할 것이다....

원칙적으로 RSA 암호를 깨부수려면 N과 싸워야된다. 어떻게든 N을 소인수분해해서 p, q를 구해야한다. 근데 잠시 N을 살펴보면 2진수로 바꿨을때 2048bit나 되는 숫자란 것을 알 수 있다. 소인수분해...는 아마 못하지 싶다. (사실은 어제부터 하는 중이다ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 몇개월이 걸리려나 잘 모르겠다만...)

그래서 나는 C랑 싸우기로 했다. 어떤 원문을 암호화했을때 C와 동일하다면 원문을 알아낸 것이 되기 때문이다. (이러한 원문/암호문 유일성이 지켜지는 것도 RSA암호화 방식의 특징이다.)

숙제라는 점을 이용하면 RSA 암호를 풀라는 것이 아니라 C를 유추해보라는 걸 의미했을 거라고 직감했다. 내 풀이에 확신이 있었기 때문에 이 원리를 이용했다. 아마 우리가 아는 단어들 중에 짧은 단어 하나를 사용했을 것이란 것도 생각해봤다. 아마 수업 과목코드 정도되면, 영문과 숫자를 모두 가지고 있을테니 적절했으리라는 것도 생각해봤지만 나는 과목코드를 알아낼 시간보다는 그냥 코딩하는게 빠를 것 같아서 코딩하기로 했다.

따라서 다음과 같이 프로그래밍했다.

def encrypt(msg=1, n=0, e=0):
    result = 1
    for _ in xrange(e):
        result *= msg
        result %= n
    return result
 
length = 36**7
msg = 1
while msg < length:
    c = encrypt(msg, int_n, E)
    if c == int_c:
        print True, msg
        break
    if msg%1000 == 0:
        print False, msg
    msg += 1
 

int_n 과 E가 공개키 N, e이다. 암호문 C는 int_c로 나타냈다. while에서 정답이 찾아지면 P를 출력하게 돼있다.

대충 1시간에 msg 100,000개 정도 살펴볼 수 있는 속도였다. 어제 돌려놓고 낮에 출근했더니 프로그램이 종료돼있더라. length가 36*7이란 점은 7자리 안에서 찾아내지 않으면 어떻게든 프로그램은 종료될 것이란걸 의미하기도 한다. 그만큼 나는 이 풀이에 확신이 있었다 ㅋㅋ

정답은 7자리까지 갈 필요없이 4자리에서 나왔다. 1039661이란 숫자였고, 이를 36진법으로 나타내서 W로 바꾸니까 MA7H라는 원문이 나왔다. 어느분이 낸 숙제인지는 모르겠지만 역시나 우리가 아는 단어를 조금 변형해서 문제를 낸 것이었다.

---

이외에 N을 소인수분해하려는 시도를 할 수도 있다. 다음 2가지 꼼수를 쓰자.

N은 소수 2개의 곱으로 이뤄져있다.

3보다 큰 홀수는 모두 소수다.

하나는 진실이고 하나는 거짓이지만 상관없다. 속도가 느려질 뿐 p, q는 구할 수 있다.

p = 3
while int_n%p > 0:
    p += 2
print int_n
print '---'
print p
 

이것도 마찬가지로 돌리고 있는 중이다. 결과는 몇개월 뒤에 알려줄 수 있을 것 같다 ㅜㅜ

여기서 알아낸 p를 바탕으로 q를 구할 수 있게 되고 결과적으로 pi(N)도 구하고 d도 구하면 비밀키를 알아 낼 수 있게 된다. 따라서 암호화된 모든 암호문을 풀 수 있게 된다.

---

N = 251959084756578934940271832400483985714292821262040320277771378360

436620207075955562640185258807844069182906412495150821892985591491761

845028084891200728449926873928072877767359714183472702618963750149718

246911650776133798590957000973304597488084284017974291006424586918171

951187461215151726546322822168699875491824224336372590851418654620435

767984233871847744479207399342365848238242811981638150106748104516603

773060562016196762561338441436038339044149526344321901146575444541784

240209246165157233507787077498171257724679629263863563732899121548314

38167899885040445364023527381951378636564391212010397122822120720357

C= 473463379097395072539382495898454906162085639659681879026616405399

495428424451169861087052967202641507260707838025696748306386596983605 617023159825207980919535323747249313079619320923847473538628418896959 924332987550448551320389957960312333459727231630200163526404478615036 000545814295023512771540109722801728543731516146595003846162482291799 055705196472613129901599055808522390957417668596322767896856368879132 056761699370403966369802707137725838745346719636653335034558017593217 972700982640056697620610010799294669918826078072748492675616914943800 1601988621860821660494703813190215928005980318603191982012282039859

e = 65537

P = 1039661

W = MA7H