PicoCTF - Scrambled: RSA

tags: PicoCTF CTF Crypto

Hint

• Look at the ciphertext, anything fishy, maybe a little bit long?
• What happens if you encrypt the same input multiple times?
• Is RSA deterministic, why would outputs vary?

Recon - 通靈

這一題也是頗有趣但要通靈，可以先亂Try

$ nc mercury.picoctf.net 61477
flag = ...
I will encrypt whatever you give me: b
Here you go: 26990049735578409030682378965549085676344091481060419655306695078226500400679435180914414853843456517959269938025436462371813167477339887511293320498195667717320879617653974074204687042294887795784122711621510485951142842770951325298677811102706200275406899117894241145575602912451443892687252208402011904237
I will encrypt whatever you give me: ba
Here you go: 2699004973557840903068237896554908567634409148106041965530669507822650040067943518091441485384345651795926993802543646237181316747733988751129332049819566771732087961765397407420468704229488779578412271162151048595114284277095132529867781110270620027540689911789424114557560291245144389268725220840201190423748281433709412944662646587136176334777506529508638551296181668932027523016538393747587852449462326357575277427356480410273494280971757044562513629423400967407332448126388859817313684399195291279961899276921240210270110225654310423792352532266414306766344869066386142998118001891330035563388790707576505068944
I will encrypt whatever you give me: bac
Here you go: 482814337094129446626465871361763347775065295086385512961816689320275230165383937475878524494623263575752774273564804102734942809717570445625136294234009674073324481263888598173136843991952912799618992769212402102701102256543104237923525322664143067663448690663861429981180018913300355633887907075765050689449619429085627210113794723864117161956939961066630142420889676674025917593454737310140819887001206562193281145515990410131903949359211712425034234736366286462137700473579439657314154736719868903719111785858132034797052503447042089004862886989401543635700329455353580959453911569277021402998961166474045310601826990049735578409030682378965549085676344091481060419655306695078226500400679435180914414853843456517959269938025436462371813167477339887511293320498195667717320879617653974074204687042294887795784122711621510485951142842770951325298677811102706200275406899117894241145575602912451443892687252208402011904237
...

一開始加密的b是269900...904237，第二個加密的ba是26990...5068944，但如果仔細看其實第一個加密的密文其實也存在其中，他其實是269900...904237+482814...5068944，可以加密第三個bac試看看，也會發現是482814...5068944+961942...3106018+269900...904237 所以我們可以再往這個方向測試一下，我們知道一開始的flag一定是picoCTF{，我們加密p會發現密文其實存在原始的flag密文當中，因此我們可以寫一個腳本，像上一題一樣暴力破解，如果加密的密文有存在原本的flag ciphertext中的話，就代表我們猜對了，反之就繼續找

Exploit - 通靈

from pwn import *
import gmpy2
from tqdm import tqdm

context.arch = "amd64"

r = remote("mercury.picoctf.net", 61477)


flag = r.recvline().strip().decode().split(" ")[-1]
n = r.recvline().strip().decode().split(" ")[-1]
e = r.recvline().strip().decode().split(" ")[-1]

def call_oracle(plaintext):
    r.recvuntil(b"I will encrypt whatever you give me: ")
    r.sendline(plaintext.encode())
    return r.recvline().strip().decode().split(" ")[-1]

current_char = ""
#output_flag = "picoCTF{bad_1d3a5"
output_flag = ""
the_last_cipher = []

#for i in range(1, len(output_flag)+1):
#    output = call_oracle(output_flag[:i])
#    for j in the_last_cipher:
#        output = output.replace(j, "")
#    the_last_cipher.append(output)

while current_char != "}":
    for i in string.printable:
        output = call_oracle(output_flag + i)
        for j in the_last_cipher:
            output = output.replace(j, "")
        if output in flag:
            the_last_cipher.append(output)
            current_char = i
            output_flag += i
            print(output_flag)
            break

::: info Note that: 如果因為連線時間過長導致連線中斷，且沒有找完所有的字元，請把27行和31-35行的註解拿掉，並把已經找到的字元填入output_flag :::

Reference

maple3142 - Scrambled: RSA picoCTF 2021 Scrambled RSA