Sophie Wilson

This is a writeup of the crypto challenge Sophie Wilson from the CyberHeroines(https://cyberheroines.ctfd.io/) CTF

Level: Easy/Medium, Score: 200

Premise

Sophie Mary Wilson CBE FRS FREng DistFBCS (born Roger Wilson; June 1957) is an English computer scientist, who helped design the BBC Micro and ARM architecture. Wilson first designed a microcomputer during a break from studies at Selwyn College, Cambridge. She subsequently joined Acorn Computers and was instrumental in designing the BBC Micro, including the BBC BASIC programming language whose development she led for the next 15 years. She first began designing the ARM reduced instruction set computer (RISC) in 1983, which entered production two years later. - Wikipedia Entry

Chal: Help this designer of microprocessors solve this RSA challenge.

Author: Prajakta

Challenge files:

n = 784605825796844081743664431959835176263022075947576226438671818152943359270141637991489766023643446015742865872000712625430019936454136740701797771130286509865524144933694390307166660453460378136369217557779691427646557961148142476343174636983719280360074558519378409301540506901821748421856695675459425181027041415137193539255615283103443383731129040200129789041119575028910307276622636732661309395711116526188754319667121446052611898829881012810646321599196591757220306998192832374480348722019767057745155849389438587835412231637677550414009243002286940429895577714131959738234773350507989760061442329017775745849359050846635004038440930201719911010249665164009994722320760601629833907039218711773510746120996003955187137814259297909342016383387070174719845935624155702812544944516684331238915119709331429477385582329907357570479058128093340104405708989234237510349688389032334786183065686034574477807623401744101315114981390853183569062407956733111357740976841307293694669943756094245305426874297375074750689836099469106599572126616892447581026611947596122433260841436234316820067372162711310636028751984204768054655406327047223250327323182558843986421816373935439976256688835521454318161553726050385094844798296897844392636332777
e = 5
c = 268593521627440355433888284074970889184087304017829415653214811933857946727694253029979429970950656279149253529187901591829277689165827531120813402199222392031974802458605195286640398523506218117737453271031755512785665400604866722911900724895012035864819085755503886111445816515363877649988898269507252859237015154889693222457900543963979126889264480746852695168237115525211083264827612117674145414459016059712297731655462334276493

Observations

In this challenge, we have a RSA encrypted message.

Luckliy for us, the e in this RSA crypto is very small, which enables us to perform a Coppersmiths Attack

Solution

An example implementation of the attack in python could look like the following:

import gmpy2
from gmpy2 import iroot
import libnum
from libnum import *

N = 784605825796844081743664431959835176263022075947576226438671818152943359270141637991489766023643446015742865872000712625430019936454136740701797771130286509865524144933694390307166660453460378136369217557779691427646557961148142476343174636983719280360074558519378409301540506901821748421856695675459425181027041415137193539255615283103443383731129040200129789041119575028910307276622636732661309395711116526188754319667121446052611898829881012810646321599196591757220306998192832374480348722019767057745155849389438587835412231637677550414009243002286940429895577714131959738234773350507989760061442329017775745849359050846635004038440930201719911010249665164009994722320760601629833907039218711773510746120996003955187137814259297909342016383387070174719845935624155702812544944516684331238915119709331429477385582329907357570479058128093340104405708989234237510349688389032334786183065686034574477807623401744101315114981390853183569062407956733111357740976841307293694669943756094245305426874297375074750689836099469106599572126616892447581026611947596122433260841436234316820067372162711310636028751984204768054655406327047223250327323182558843986421816373935439976256688835521454318161553726050385094844798296897844392636332777
e = 5
orig = 268593521627440355433888284074970889184087304017829415653214811933857946727694253029979429970950656279149253529187901591829277689165827531120813402199222392031974802458605195286640398523506218117737453271031755512785665400604866722911900724895012035864819085755503886111445816515363877649988898269507252859237015154889693222457900543963979126889264480746852695168237115525211083264827612117674145414459016059712297731655462334276493

c = orig
while True:
    m = iroot(c, e)[0]
    if pow(m, e, N) == orig:
        print("pwned", n2s(int(m)))
        break
    c += N

Running this code prints out the following: pwned b'chctf{d3516n3d_4c0rn_m1cr0_c0mpu73r}'

Giving us our flag

chctf{d3516n3d_4c0rn_m1cr0_c0mpu73r}

Tools used:

• Python