baby_rsa

Real baby rsa (crypto, 40p, 505 solved)

In the challenge we get source code and ciphertext. The code is pretty trivial:

flag = 'TWCTF{CENSORED}'

# Public Parameters
N = 36239973541558932215768154398027510542999295460598793991863043974317503405132258743580804101986195705838099875086956063357178601077684772324064096356684008573295186622116931603804539480260180369510754948354952843990891989516977978839158915835381010468654190434058825525303974958222956513586121683284362090515808508044283236502801777575604829177236616682941566165356433922623572630453807517714014758581695760621278985339321003215237271785789328502527807304614754314937458797885837846005142762002103727753034387997014140695908371141458803486809615038309524628617159265412467046813293232560959236865127539835290549091
e = 65537

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

It's a classic textbook RSA encryption with large unfactorizable modulus and standard exponent, nothing wrong here. The vuln is pretty obvious -> the flag is encrypted character-by-character without using any random padding.

If e was small (eg. 3) we could just compute integer root to recover the original character. In fact with N of 2038 bits and 7 bit chars, we could manage to do this up until e lower than 291. After that the the result starts to wrap around modulus.

Here e is bigger so we can't do it like that. However, since there is no random padding, each character encrypted looks always the same, a bit like in ECB encryption (with single character as blocks). It's easy to confirm this by looking into the output file. We know the flag prefix is TWCTF{ so 1st and 4th letters are identical, and in the file we have:

9073209977571176486825453267118351996016396235857623493182258724402523182425555398048461088180575997426276026776186441023571190870577545894667546140441145538176352391499376279774875943812941321565506013356240326235158415041323709138860753984228634160552040417002326854872319407516200542564071756611880349380322282130265915072405694912128104078505106072784722670288292878670301302909960910520529391182927036489958388823511447221117040898358990430312656065571576446469592472217394596577973531530126373565564994195530324540432367900449603179849204693929275999798234441199340509474634967526614647348655247823230784374

for both of them.

This means we can create a simple lookup table by encrypting all printable characters, and then decrypt the flag:

import codecs


def main():
    N = 36239973541558932215768154398027510542999295460598793991863043974317503405132258743580804101986195705838099875086956063357178601077684772324064096356684008573295186622116931603804539480260180369510754948354952843990891989516977978839158915835381010468654190434058825525303974958222956513586121683284362090515808508044283236502801777575604829177236616682941566165356433922623572630453807517714014758581695760621278985339321003215237271785789328502527807304614754314937458797885837846005142762002103727753034387997014140695908371141458803486809615038309524628617159265412467046813293232560959236865127539835290549091
    e = 65537
    lookup_table = {str(pow(i, e, N)): i for i in range(256)}
    res = ""
    with codecs.open("output", "r") as input_file:
        for line in input_file:
            res += chr(lookup_table[line[:-1]])
    print(res)


main()

And we get TWCTF{padding_is_important}