CSCG 2020: Intro to Crypto 2


Message and pubkey are given.

This is almost the same challenge as Intro to Crypto 1. The only difference is how to get the factors of n. In the first challenge, they could be bruteforced, because one factor was small. This time p and q are equal. It was helpful to do this on paper for the first challenge to remember how RSA works. The calculations are the same for this challenge. That's why I won't explain it here in detail. You can look them up in the first challenge.

Instead of that we'll use RsaCtfTool this time. First we run the different attacks using the tool. The tool is able to extract the private key, because p and q are the squareroot of n.

$ RsaCtfTool.py --publickey pubkey.pem --private --verbose
[*] Performing hastads attack.
[*] Performing prime_n attack.
[*] Performing factordb attack.
[*] Performing pastctfprimes attack.
[*] Loaded 71 primes
[*] Performing mersenne_primes attack.
[*] Performing noveltyprimes attack.
[*] Performing smallq attack.
[*] Performing wiener attack.
[*] Performing comfact_cn attack.
[*] Performing primefac attack.
-----BEGIN RSA PRIVATE KEY-----
MIIEoQIBAAKCAQBXyI8cm57UfYRPh7KfRHluF85Hwv4kzBq340QyszUhJGPSOZ0H
RxGABXLqaBLikBICvF8ZDMtJZtVwkEpBaXpjZEiK4UCxtjV/xqa0rM1RenQDu8mW
39ByiV9qmh6o8qbatp2hVXUXf0zvGtuQglu9T+xQAarAGnDooQ4QEzRxOTK+R9Gg
nXDTEVf+JuVTd0+NnlAgmEcryocHkx4rycuSqslEUb5vHlWLk6hoXOmE9IQK+vjS
qK0NRlRUYqkYFRpQ3qGij03x5eaZsAUtpSMFnrIdVrZ8keVqt181vJ9km+p2oTax
cNOmdvUUuciVXq94qQut1Uhbun8SF4sfj+/vAgMBAAECggEASosBHCX6Ri8f//kX
ca/P/fExNjcbYVwBBE51Ryhu4WnpakeKVPfAoJn/75XZE5OL987GYps+tWIhtaiR
peJQD77E60pEiaRU4eBrB9oFsD7v7Yu1r+z3MYv9/qRJjOYhUnDogmvzNrTfO9vu
v1QzWxtXbMk9mkvZvXGmY3grfEk7eHnOoTaPG/MpTdomIw64WDZCJMpRF3I1h3Xw
hXeQGYwa9csqi7tTrpOXsJa8GRkFLbLNb6IdBAvjwH/dsfMBpj3Bhm+KJ7OMKdUo
Xz33TjC8yU0YznKHauRFaXefy8uabnHw+EEdE7piWaP9JtdEILmDstAu8HGrI0IT
/cppQQKBgQCV6JOZjsXg3kI0uZItppy8RtcLcc61738KO0h7iW2KwkIeLN0U0aVu
uDquMraM8A+m5Lz1fyJx2q/OVqOP3Vl2Af+cBvy50NxPNuhq+yAEgHRjuYJywBur
oot4X4j4DJX2IOtMJc14HF+xxKh2rRQKFmKuQSZKT9RQ4BD2Vyu5+QKBgQCV6JOZ
jsXg3kI0uZItppy8RtcLcc61738KO0h7iW2KwkIeLN0U0aVuuDquMraM8A+m5Lz1
fyJx2q/OVqOP3Vl2Af+cBvy50NxPNuhq+yAEgHRjuYJywBuroot4X4j4DJX2IOtM
Jc14HF+xxKh2rRQKFmKuQSZKT9RQ4BD2VyozJwKBgHW/cjg6edlQGua5IEW1SgVl
C0KVCQ3E6Z+KwzstzhogzbhP+vOAXJYkJQtxEAyR/2lS381hKBgP8ul7CgxVjBBy
L2lJ37bAhFvAQDzPte1zTHiMXRdvKAzfpvdM6xQTJrNmVgvA4axHdS73zm8xMb1e
qfI/gCj8nUNNTGWCQPlZAoGAGCXf6OOL0p5a8d1Ww83L/7Q1nd1WXA5ZW4+TLHtF
zw1d0ziM4Hao/H3mzfrTVz6wdsTv/2fcZ5S/rzBbpqgUaiMGRt8FRPV1F7mTlPAh
BzieBxZyAgQaMPq9FsXk7Xgxi/VfkeOhBpEjhSJVtNBKoxlaChHqlhvn6qM9eEEw
Rg8CgYB+zXtz6T7pT2yrjo11bFInu+8cuvHJ1/y0Z0+NPnwFLeYqYt8s7KTbwBsZ
QatNET2LAKLqNPA6QeOuTVKaLv3FlxbKT1XWIKVExTuUjI3f34wXOIkG2nUGJFud
Aj3qyNx3RiLAEWQq1Ofbq9R1VUnqXDY23iA08gjumwdKdpbbhg==
-----END RSA PRIVATE KEY-----

$ RsaCtfTool.py --key privkey --dumpkey
[*] n: 11081631875903145989449935723431993312048263659503073501368579288661507666926127398551161494057149306128113773163942639308834214121175806650609216999457699806761832905200688030797211656004392019494461369905299150414106039926917206543955359193966893148964232596310365304968051716316421386564037673515738090636958039103706945349258789436043666088184674948218539196263599899299117746103356732914111330139176914363944699056706536973601851519543254647327613986429683489937828404640743341705415177790924588759219148196121101333618974290049804819348181073769764832469557718828674823915162708288827812462173689965257895702511
[*] e: 65537
[*] d: 9410180160180690001142374885643793457163281339986039130539453660872335088267281718482219806632413341847228095642457478413953059863461494906994585416693164313989189691933239090741511254405243216334372402733871070064937811221337509782019373023828456254118398346733363595405374278902627264065517564223230483850592366063040480660958730662578092189582641027965094064929775606941457340069428080012051766251996104704048924482207136210364067936572301797816103110415210782314747226572568199436255716765759027107976803081087027553033172218140961638177296684269917936981903114352839394576852159111093965803370195924016297568577
[*] p: 105269330176947292996638200435938306898008923026214454261833875185727477089897046111427146733705930821830266909665628457524081078905360676252447567252776868229878866771906188152589974886284283170888631961882151644823439854179072943695999068501018297820499189273623372907923121271707038222250931356234064574969
[*] q: 105269330176947292996638200435938306898008923026214454261833875185727477089897046111427146733705930821830266909665628457524081078905360676252447567252776868229878866771906188152589974886284283170888631961882151644823439854179072943695999068501018297820499189273623372907923121271707038222250931356234064474919

Now we are able to decrypt the message by calculating m^d % n and 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.

plain = pow(6213639477312598145146606285597413094756028916460209994926376562685721597532354994527411261035070313371565996179096901618661905020103824302567694878011247857685359643790779936360396061892681963343509949795893998949164356297380564973147847768251471545846793414196863838506235390508670540548621210855302903513284961283614161501466772253041178512706947379642827461605012461899803919210999488026352375214758873859352222530502137358426056819293786590877544792321648180554981415658300194184367096348141488594780860400420776664995973439686986538967952922269183014996803258574382869102287844486447643771783747439478831567060, 9410180160180690001142374885643793457163281339986039130539453660872335088267281718482219806632413341847228095642457478413953059863461494906994585416693164313989189691933239090741511254405243216334372402733871070064937811221337509782019373023828456254118398346733363595405374278902627264065517564223230483850592366063040480660958730662578092189582641027965094064929775606941457340069428080012051766251996104704048924482207136210364067936572301797816103110415210782314747226572568199436255716765759027107976803081087027553033172218140961638177296684269917936981903114352839394576852159111093965803370195924016297568577, 11081631875903145989449935723431993312048263659503073501368579288661507666926127398551161494057149306128113773163942639308834214121175806650609216999457699806761832905200688030797211656004392019494461369905299150414106039926917206543955359193966893148964232596310365304968051716316421386564037673515738090636958039103706945349258789436043666088184674948218539196263599899299117746103356732914111330139176914363944699056706536973601851519543254647327613986429683489937828404640743341705415177790924588759219148196121101333618974290049804819348181073769764832469557718828674823915162708288827812462173689965257895702511)

# 158116205599014035015539814216353479551457528480024633288497747803743952933679380933147605963639746465759112829

bytes.fromhex(hex(plain)[2:]).decode()

# CSCG{Ok,_next_time_I_choose_p_and_q_random...}

The writeup for part 3 can be found here.