CSCG 2020: Intro to Crypto 1

RSA is defined as:

choose p, q and e
n = p * q
phi(n) = (p-1) * (q-1)
gcd(e, phi(n)) = 1      # no common devisor apart 1
e * d = 1  mod phi(n)

encrypt
m^e % n

decrypt
m^d % n

pubkey is n, e
privkey is p, q, d

First we need to extract the information from the pubkey with openssl.

$ openssl rsa -pubin -in pubkey.pem -text -noout

RSA Public-Key: (2047 bit)
Modulus:
    51:cf:f4:6d:9e:e3:20:96:d6:c8:06:cb:c7:df:2d:
    1d:3b:ea:7e:7b:2f:c4:e8:26:d9:fc:5e:18:79:99:
    12:dc:a1:50:b2:9c:65:c0:f9:e6:64:53:39:6c:e7:
    de:63:1a:0f:9a:67:45:13:8b:61:25:bb:cd:18:5a:
    a1:2e:b0:9a:4a:1b:d8:06:11:8c:97:a8:de:05:ed:
    0b:e6:b4:5f:c1:c9:e9:93:71:92:f5:8b:c4:a5:cc:
    27:67:80:3c:0b:21:34:2a:f5:cb:8f:34:af:fb:1a:
    6e:c2:52:0c:76:5d:87:52:1c:68:48:db:d8:31:81:
    2e:cc:6d:8b:b3:d6:17:33:b0:eb:c3:52:cf:64:d4:
    44:5c:99:55:72:92:2f:49:3d:71:89:95:9d:b2:32:
    1e:1b:ac:59:25:fa:56:dc:69:f6:85:8e:fe:eb:a0:
    a5:a9:d7:6b:a1:98:18:71:53:92:74:24:e5:f7:b6:
    80:98:ab:8c:10:44:2b:73:d1:49:02:7c:fc:37:d0:
    30:05:63:37:c3:e0:f4:21:6c:f4:32:23:96:74:41:
    b6:08:ee:c2:a6:48:e8:ce:85:78:94:c6:65:03:0c:
    01:24:56:29:27:9b:38:7f:cd:bd:c3:5b:61:67:71:
    5b:54:bd:55:56:18:0d:9a:f2:50:4b:52:7a:90:fa:
    e7
Exponent: 65537 (0x10001)

This gives us:

e = 65537
n = 0x51cff46d9ee32096d6c806cbc7df2d1d3bea7e7b2fc4e826d9fc5e18799912dca150b29c65c0f9e66453396ce7de631a0f9a6745138b6125bbcd185aa12eb09a4a1bd806118c97a8de05ed0be6b45fc1c9e9937192f58bc4a5cc2767803c0b21342af5cb8f34affb1a6ec2520c765d87521c6848dbd831812ecc6d8bb3d61733b0ebc352cf64d4445c995572922f493d7189959db2321e1bac5925fa56dc69f6858efeeba0a5a9d76ba198187153927424e5f7b68098ab8c10442b73d149027cfc37d030056337c3e0f4216cf43223967441b608eec2a648e8ce857894c665030c01245629279b387fcdbdc35b6167715b54bd5556180d9af2504b527a90fae7

We try to bruteforce the factor p of n.

for i in range(2, 1000000):
    if n % i == 0:
        print("Factor found: " + str(i))
        break

# Factor found: 622751

We found out that p is 622751. Now we are able to calculate the second factor q and phi(n) with phi(n) = (p-1) * (q-1).

q = n // p
# 16584235167731787847013470803061277015678956556694867873072487447887926204573222554710220299137896151698893829263470795092022504576184748229461509022182668168932373990476110465504678644868916760949835108178505407538822880225906663932043264799941076095252059950113859004542443496612744563482124073298940744796576800151123820336528353672466777346414021097764537645521638337450661718385755338513002335497796149161099248732899206255277182670571055097076123763356692547858422108949105868315872104780985522044066316665393121965734834334905254114025888811325924997427587424504748731773056980012499780203906986519558329

# phi(n) = (p-1) * (q-1)
(p-1) * (q-1)
# 10327832450704970881727638942606410261514070195681728967955891558172206043897974345945789691288124828470486132173826437643557014724819051959897154743564256602202635902568997792393038626092117912881509813618164242544801948660683374963679943154163305138318220333933405695078806687515586676908492766646915348822068202294112359114573032249528685592479331638632865818748600274647399585124729137058972204431252551890074557148412980695473865508098124561704156073630380284178832368348055679493709353252358733852942298703373566704161368082062246999509622257253219792148030068610332272711671234302784238121983075855054948762000

After that we have to calculate e * d = 1 mod phi(n). This is the same as calculating d = modinv(e, phi(n)). I used modinverse.py for the calculation of the modular inverse. Adjusting p, q and e gives us:

d = 7312074487887920547357407982314378688897155150214874408550183381894050085247509187968394062526038604773342639011025019556297137238988724093858858051198277405773872863866235829638784079995640190391718500265236749532001928953960489468769540295606716181973014075934358061120536953182526234166258210971159378447960153599444793977694870018129163853869432351687824801103728470080097361029455604613215592499048146965827844602077640176846473893766162315380210290621322995954923507199746456635306986754191452931573350318698345897326509895291030422162236183172092075555313718716441360663770774854649871810733093056968576873473

Now we are able to decrypt the message m by calculating m^d % n.

pow(4522827319495133992180681297469132393090864882907734433792485591515487678316653190385712678072377419115291918844825910187405830252000250630794128768175509500175722681252259065645121664124102118609133000959307902964132117526575091336372330412274759536808500083138400040526445476933659309071594237016007983559466411644234655789758508607982884717875864305554594254277210539612940978371460389860098821834289907662354612012313188685915852705277220725621370680631005616548237038578956187747135229995137050892471079696577563496115023198511735672164367020373784482829942657366126399823845155446354953052034645278225359074399, 7312074487887920547357407982314378688897155150214874408550183381894050085247509187968394062526038604773342639011025019556297137238988724093858858051198277405773872863866235829638784079995640190391718500265236749532001928953960489468769540295606716181973014075934358061120536953182526234166258210971159378447960153599444793977694870018129163853869432351687824801103728470080097361029455604613215592499048146965827844602077640176846473893766162315380210290621322995954923507199746456635306986754191452931573350318698345897326509895291030422162236183172092075555313718716441360663770774854649871810733093056968576873473, 16584235167731787847013470803061277015678956556694867873072487447887926204573222554710220299137896151698893829263470795092022504576184748229461509022182668168932373990476110465504678644868916760949835108178505407538822880225906663932043264799941076095252059950113859004542443496612744563482124073298940744796576800151123820336528353672466777346414021097764537645521638337450661718385755338513002335497796149161099248732899206255277182670571055097076123763356692547858422108949105868315872104780985522044066316665393121965734834334905254114025888811325924997427587424504748731773056980012499780203906986519558329)

# 30452073505612430994559891836844187348395858508546581868844534804369107940477

After we convert the int into a hex string, strip the "0x" at the beginning and then convert the result into ascii we are able to read the flag.

bytes.fromhex(hex(30452073505612430994559891836844187348395858508546581868844534804369107940477)
[2:]).decode()
# CSCG{factorizing_the_key=pr0f1t}

The writeup for part 2 can be found here.