real-baby-rsa

Description

Category: Crypto

Source: TokyoWesterns CTF 5th 2019

Points: 42

Author: Jisoon Park(js00n.park)

Description:

Download: real-baby-rsa.7z

Write-up

압축을 풀어보면 problem.py와 output 파일을 찾을 수 있다.

먼저, python 코드를 살펴보자.

flag = 'TWCTF{CENSORED}'

# Public Parameters
N = 36239973541558932215768154398027510542999295460598793991863043974317503405132258743580804101986195705838099875086956063357178601077684772324064096356684008573295186622116931603804539480260180369510754948354952843990891989516977978839158915835381010468654190434058825525303974958222956513586121683284362090515808508044283236502801777575604829177236616682941566165356433922623572630453807517714014758581695760621278985339321003215237271785789328502527807304614754314937458797885837846005142762002103727753034387997014140695908371141458803486809615038309524628617159265412467046813293232560959236865127539835290549091
e = 65537

# Encrypt the flag!
for char in flag:
    print(pow(ord(char), e, N))

꽤 큰 수로 보이는 N이 public modulus e와 함께 주어져 있고, RSA의 암호화 방식으로 flag를 암호화 하여 출력하는 간단한 코드이다.

일단 기계적으로 N에 대한 factorization을 시도해 보았는데 쉽게 되지 않았다.

그 와중에도 solving 수가 계속 올라가고 있어서, 코드를 다시 한번 자세히 보았더니, 암호화 구문에서 암호화를 flag 전체에 대해서 한번 하는게 아니라 각 글자마다 암호화를 하고 있었다 ㅡ_ㅡ;;

printable한 각 문자에 대해서 암호화를 시도하여 (암호문, 문자)로 구성된 dictionary를 만들고 이를 이용하여 output의 각 line에 적혀있는 숫자를 하나의 문자로 대체하여 모았더니 flag를 획득할 수 있었다.

import string

N = 36239973541558932215768154398027510542999295460598793991863043974317503405132258743580804101986195705838099875086956063357178601077684772324064096356684008573295186622116931603804539480260180369510754948354952843990891989516977978839158915835381010468654190434058825525303974958222956513586121683284362090515808508044283236502801777575604829177236616682941566165356433922623572630453807517714014758581695760621278985339321003215237271785789328502527807304614754314937458797885837846005142762002103727753034387997014140695908371141458803486809615038309524628617159265412467046813293232560959236865127539835290549091
e = 65537

d = dict()
for c in string.printable:
    d[pow(ord(c), e, N)] = c

flag_data = map(lambda x: int(x.strip()), open("output").readlines())

r = ""
for i in flag_data:
    r += d[i]

print r

Flag: TWCTF{padding_is_important}