RSAaaay

Description

Category: Crypto

Source: TAMUctf 2019

Points: 478

Author: Jisoon Park(js00n.park)

Description:

Hey, you're a hacker, right? I think I am too, look at what I made!

-------------------------------> (2531257, 43)

My super secret message: 906851 991083 1780304 2380434 438490 356019 921472 822283 817856 556932 2102538 2501908 2211404 991083 1562919 38268

-------------------------------> Problem is, I don't remember how to decrypt it... could you help me out?

Difficulty: easy

Write-up

RSA 관련 문제이다. 가장 먼저 주어진 것은 public key pair인 것 같다.

modulus가 그리 크지 않으니 bruteforce로 해도 금방 인수분해를 할 수 있을 것 같고, 실제로도 그렇다. 2531257 = 509 * 4973임을 금세 얻을 수 있다.

modulus를 인수분해 한 다음, phi(n)을 구하고 private exponent를 계산하자. 그런 다음 문제에서 주어진 값들을 복호화 해보면 아래와 같은 값들을 얻을 수 있다.

[103, 105103, 101109, 12383, 97118, 97103, 10195, 83105, 12095, 70108, 121105, 110103, 9584, 105103, 101114, 115125]

거의 다 풀은 걸로 생각했다가 여기서 풀이가 막혔는데, 첫번째 값은 ASCII로 해석이 되지만, 두번째 값 부터는 어떻게 flag로 변환시켜야 할지 감이 오지 않았다. 그래서 일단 여기서 접어두고 다른 문제를 풀었는데, 다른 문제의 flag 형식이 gigem{}으로 시작해서 이 문제도 같은 형식이지 않을까 싶어서 gigem을 ascii decimal로 바꿔 봤더니 [103, 105, 103, 101, 109] 였다.

이로 미루어 이 문제에서 주어진 값들은 flag를 두 글자씩 묶어서 ascii decimal을 연접(concatenation) 한 것임을 유추할 수 있었다.

문제에서 주어진 값들을 모두 연접한 후 printable ascii code들이 나올때마다 chr로 변환하여 출력하는 코드를 작성하여 실행하였더니 flag를 얻을 수 있었다.

Flag : gigem{Savage_Six_Flying_Tigers}