[CTFlearn] Skynet Is (Almost) Taking Over - 암호학 / RsaCtfTool

 

CTFlearn 의 여든여덟번째 문제

 

4연속 Hard 난이도의 문제가 나와서 살짝 쫄았는데

 

이번 문제는 아주 쉽게 풀 수 있었다.

 

반응형

 

문제 설명이 아주 장황하다.

 

양자 컴퓨팅 어쩌고 하면서 나오는데 사실 이 의도를 잘 모르겠다.

 

RSA 에 관련한 문제인데

 

RSA는 지금까지도 아주 많이 사용하는 공개키 알고리즘의 이름이다.

 

개발자인 Rivest, Shamir, Adleman 세명의 이름 앞글자를 따서 RSA 라고 이름을 붙혔다.

 

엄청나게 큰 숫자일수록 소인수분해가 어렵다는것에 착안해서 설계되었다.

 

RSA의 원리는 아래와 같다.

 

1. 두 소수 p, q를 준비한다.

2. p-1, q-1과 각각 서로소(1외에는 공약수가 없는 수)인 정수 e를 준비한다.

3. ed를 (p-1)(q-1)으로 나눈 나머지가 1의 되도록 하는 d를 구한다.(d는 개인키로 공개하지 않는다)

4. n=pq를 계산한 후 n과 e를 공개한다.(이 둘이 공개키)

 

이 알고리즘을 이용해서 공개키-개인키 쌍을 만들고

 

공개키로 암호화했다면 개인키로만 풀 수 있고, 개인키로 암호화했다면 공개키로만 풀 수 있는 그런 알고리즘이다.

 

e: 65537

c1: 5024836662627906750454817701922271080214720765897113783786369197810770999608528443597447448508876214100063962982376037712548944474807897847869334582773452689962992522987755069402952836848501053684233233850594080254869
n1: 10603199174122839808738169357706062732533966731323858892743816728206914395320609331466257631096646511986506501272036007668358071304364156150345138983648630874220488837685118753574424686204595981514561343227316297317899

c2: 130884437483098301339042672379318680582507704056215246672305503902799253294397268030727540524911640778691710963573363763216872030631281953772411963153320471648783848323158455504315739311667392161460121273259241311534
n2: 5613358668671613665566510382994441407219432062998832523305840186970780370368271618683122274081615792349154210168307159475914213081021759597948038689876676892007399580995868266543309872185843728429426430822156211839073

c3: 40136988332296795741662524458025734893351353026652568277369126873536130787573840288544348201399567767278683800132245661707440297299339161485942455489387697524794283615358478900857853907316854396647838513117062760230880
n3: 43197226819995414250880489055413585390503681019180594772781599842207471693041753129885439403306011423063922105541557658194092177558145184151460920732675652134876335722840331008185551706229533179802997366680787866083523

 

문제에서 주어지는 Skynet.txt 파일의 내용이다.

 

e 값이 65537 로 고정되어 있고

 

n과 c 값이 각각 3개씩 주어져 있다.

 

문제풀때는 RsaCtfTool 이라는 도구를 사용했다.

 

 

git clone [github 주소] 명령어를 통해 다운로드 받을 수 있다.

 

다운로드 받고나서 cd RsaCtfTool 명령어로 해당 폴더에 들어가보면

 

RsaCtfTool.py 라는 파이썬 파일이 보이게 된다.

 

 

./RsaCtfTool.py 라고 입력하면 실행이 가능한데

 

이렇게 No module named 'Crytpo' 라는 에러가 나게되면

 

 

pip install pycrypto 명령어로 다운로드 받아주면 된다.

 

 

다운받으면 이렇게 잘 실행이 된다.

 

이제 옵션을 줘서 툴을 실행시키면 된다.

 

 

./RsaCtfTool.py -n n값 -e e값 --uncipher c값 으로 옵션을 넣어주면

 

툴이 계산을 시작한다.

 

우선 n1, c1 에 대해서만 먼저 계산을 해봤는데

 

바로 플래그가 나와버렸다..

 

가짜 플래그인줄 알고 시험삼아 넣었는데 문제가 풀렸다.

 

n2/c2, n3/c3 에 대해서도 툴을 돌려봤는데

 

뭔가 복잡해서 그런지 실행되다가 kali가 재부팅 되어버렸다.

 

어쨌든 문제는 풀렸으니 뭐..