redpwnCTF 2020 Crypto

# 4k RSA

This is a classic RSA question where we were given `n`

`e`

and `c`

. In this case to decipher `c`

we need to find `d`

which is the modular inverse of the totient and `e`

.

## Finding the Totient

To find the `Eulers Totient`

we need to find the factors of n. Then we could put it in this equation since we know that all of n's factors are prime

phi = (p0-1)(p1-1)...(pn-1)

To factor a large number like n we could of course use the `Python Crypto`

module but we can search for the number on factordb.

### Prime Factorization

We input `n`

into factordb and indeed it is already FF(fully factored)

primes=[9353689450544968301,9431486459129385713,9563871376496945939,9734621099746950389,9736426554597289187,10035211751896066517,10040518276351167659,10181432127731860643,10207091564737615283,10435329529687076341,10498390163702844413,10795203922067072869,11172074163972443279,11177660664692929397,11485099149552071347,11616532426455948319,11964233629849590781,11992188644420662609,12084363952563914161,12264277362666379411,12284357139600907033,12726850839407946047,13115347801685269351,13330028326583914849,13447718068162387333,13554661643603143669,13558122110214876367,13579057804448354623,13716062103239551021,13789440402687036193,13856162412093479449,13857614679626144761,14296909550165083981,14302754311314161101,14636284106789671351,14764546515788021591,14893589315557698913,15067220807972526163,15241351646164982941,15407706505172751449,15524931816063806341,15525253577632484267,15549005882626828981,15687871802768704433,15720375559558820789,15734713257994215871,15742065469952258753,15861836139507191959,16136191597900016651,16154675571631982029,16175693991682950929,16418126406213832189,16568399117655835211,16618761350345493811,16663643217910267123,16750888032920189263,16796967566363355967,16842398522466619901,17472599467110501143,17616950931512191043,17825248785173311981,18268960885156297373,18311624754015021467,18415126952549973977]

This is the prime factorization of `n`

## Script

To find the totient phi, and find the final plaintext, I wrote a small python script to automate the process. I skipped the RSA values as they take up to much space. They could be sound in the provided txt file.

from Crypto.Util.number import inverse n= #n from provided txt file e=65537 c= #c from provided txt file primes= #the primes listed above. Don't want to showcase twice as there is quite a lot of them. phi=1 for x in primes: phi=phi*(x-1) d = inverse(e,phi) m=pow(c,d,n) print(hex(m))

Essentially, we set phi to one and multiply it to the next prime factor of n minus one. Then we get d by doing the modular inverse of the public exponent and phi. To solve the plaintext, we just need to raise `c`

to the power of `d`

mod `n`

.