Rivest, Shamir, Adleman 2

Description: Little John has done his homework and tried fixing the issue in his script. Can you still find his secret.

Introduction

Rivest, Shamir, Adleman 2 was a crypto CTF from IRON CTF 2024 organized by Team 1nf1n1ty. It is meant as a sequel to Rivest, Shamir, Adleman 1. We’re not given a script that generates the parameters, simply the public key and the ciphertext.

(N,e,c)=(161643423646746552081298841935498903406728484661198088824380120820649408462211320026846900530120533720144166059852036274757176945943476154740893002954181911201068843959015760064479587114460816364946604976937998011320067074515344961776920419207973234413389567508538119203696918037349918054399980346807879167361, 36675, 59237480729804419902249350038380812764615310700084519548754724856780737977857097616843794684178008858466821286387353080178404910815575872547979820848851425285654302196414305127926468908308102733135120774714553727434912025225828846601760761868067655959956674559148988221195055343304319184971182998654695411365)

Solution

Since N is prime we can just calculate the e-th roots of c to find the plaintext(s)

N, e, c = (161643423646746552081298841935498903406728484661198088824380120820649408462211320026846900530120533720144166059852036274757176945943476154740893002954181911201068843959015760064479587114460816364946604976937998011320067074515344961776920419207973234413389567508538119203696918037349918054399980346807879167361, 36675, 59237480729804419902249350038380812764615310700084519548754724856780737977857097616843794684178008858466821286387353080178404910815575872547979820848851425285654302196414305127926468908308102733135120774714553727434912025225828846601760761868067655959956674559148988221195055343304319184971182998654695411365)

for m in GF(N)(c).nth_root(e, all=True):
    bs = bytes(Integer(m).digits(256)[::-1])
    if b'iron' in bs:
        print('flag:', bs[:bs.index(b'}')+1].decode())
        break

$ flag: ironCTF{th15_TIme_You_c4Nt_f!ND_1t_hop3FUl1Y}

Author: vympel