Tags: rsa crypto
Rating:
# One Part! (Crypto)
## RSA notations:
* public key: n = p * q
* public exponent: e
* private key: d
* cipher/encrypted text: m
## A extremly brief explanation of how RSA works:
### To Encrypt a message:
(message ^ e) % n
### To Decrypt a message:
let cipher be the encrypted message, so cipher = (message) ^ e % n
(cipher ^ d) % n = (message ^ ed) % n
Essentially we want ed = 1 % phi(n), where phi is Euler's totient function. So we can write ed = 1 + phi(n) * h, where h is an arbitrary integer.
Thus we can prove that message % n = (message ^ ed) % n:
(message ^ ed) % n
= (message) ^ (1 + phi(n) * h) % n
= (message * message ^ (phi(n) * h) % n
= (message * 1 ^ h) % n = message % n
Since n, e, and m are all displayed publicly, this means that RSA hinges on the fact that one cannot factor n or figure out phi(n) easily (otherwise they can easily figure out d with ed = 1 % phi(n)!).
## Actual Solution
Now, onto the ctf problem! Downloading the file and opening it, we are given the values of dp, e, n and cipher.
e = 65537
dp = 15863941351022675271470498055440018518890999065008090553947887331349060559165417151482111730533900341104699951315612031296744594701865438849657867331942686064408344200992596897731186704102476529429339278690748746609131178367030814132224462991833270965841136411444101247903371020388961422615207080090040311385
Note: dp = d % (p - 1)
n = 13795029341892417374839569348195219432273811499483782737330171543244685968744999323208547919665299783906957825270449006773866123362810477840346497089695409735324208705537006191240439897433032270300293091365930830592120936636584926755229275335158742925495154248094930986582540466282129158682944188080860981812852232204308214285109566958749409476615914322197257558630214751391486659657892675174292657801181344004269336582824495524735592639617122904261904725149320803824393890508587709714045126033113995823573370380507690572913971259051956543607099582177007672826620386223089090352147939487203095545319421169070202568081
cipher = 4577483075923691025614837387199959169275891010490317043142964745465946594734541383793196135840379923558282553847958293921035008363297701769706082343316794998794846094470932254663483885231325059503550992175528744843034602900645069686396280989390227810555558579302943585247037825841710062260608576583049065083988456565702297252837653658501925749752005065311426953256044460166446107914200467201439311812471408454665833883066991637851573154466515181854296188872448618848136386704796559645721088729635821840733708277778529467678390494522595775876496533057623112322654282130317608735511663306372475467872142100508022014379
We have to decrpyt cipher by cracking this rsa using the information of n, e, and dp. I followed this youtube video on how to attack this rsa
with the given information: https://www.youtube.com/watch?v=kYgHBbyF78E, sadly the video is not in english but I'll provide a brief explanation
on how it works.
### More boring (but interesting?) math:
We start with: ed = 1 % phi(n) -> ed = 1 + k * phi(n), where k is some arbitrary integer
ed = 1 + k * phi(n)
ed % (p - 1) = (1 + k * phi(n)) % (p - 1)
ed % (p - 1) = (1 + k * (p-1) * (k-1)) % (p - 1) //Note: For a product of prime numbers: phi(p * q) = (p - 1) * (q - 1)
[e % (p - 1)] * [d % (p - 1)] = (1 + 0) % (p - 1) = 1 % (p - 1)
[e % (p - 1)] * dp = 1 % (p - 1)
e * dp = 1 % (p - 1)
e * dp = 1 + k1 * (p - 1) //where k1 is some arbitrary integer
Having all of this, we can brute force k1 to figure out p and simply verify if p is right by doing n % p == 0 as p * q = n.
Something is missing though... oh right, we need to figure out the bounds of k1 to make the brute force faster.
We could just start testing k1 from 0...all the way up, but we can do better than that.
### Last piece of boring math:
Given this: e * dp = 1 + k1 * (p - 1) and dp = d % (p - 1), we know d < p - 1.
Assuming dp = p - 1
e * (p - 1) > 1 + k1 * (p - 1)
e * (p - 1) - 1 > k1 * (p - 1)
[e * (p - 1) - 1] / (p - 1) > k1
e - 1 / (p - 1) > k1
e > k1 # and very very roughly becomes
Great! Now we know k1 < e and we can brute force k1 to find p!
dp = 15863941351022675271470498055440018518890999065008090553947887331349060559165417151482111730533900341104699951315612031296744594701865438849657867331942686064408344200992596897731186704102476529429339278690748746609131178367030814132224462991833270965841136411444101247903371020388961422615207080090040311385
n = 13795029341892417374839569348195219432273811499483782737330171543244685968744999323208547919665299783906957825270449006773866123362810477840346497089695409735324208705537006191240439897433032270300293091365930830592120936636584926755229275335158742925495154248094930986582540466282129158682944188080860981812852232204308214285109566958749409476615914322197257558630214751391486659657892675174292657801181344004269336582824495524735592639617122904261904725149320803824393890508587709714045126033113995823573370380507690572913971259051956543607099582177007672826620386223089090352147939487203095545319421169070202568081
m = 4577483075923691025614837387199959169275891010490317043142964745465946594734541383793196135840379923558282553847958293921035008363297701769706082343316794998794846094470932254663483885231325059503550992175528744843034602900645069686396280989390227810555558579302943585247037825841710062260608576583049065083988456565702297252837653658501925749752005065311426953256044460166446107914200467201439311812471408454665833883066991637851573154466515181854296188872448618848136386704796559645721088729635821840733708277778529467678390494522595775876496533057623112322654282130317608735511663306372475467872142100508022014379
```python
for k in range(1,65537):
p = (65537 * dp - 1 + k) // k
if (n % p == 0):
print ("K is " + str(k))
print ("P is " + str(p))
print ("Q is " + str(n // p)) # simply getting q along with p, because why not?
```
Now we have p and q:
p = 144039224760594772688606543510580838691127653882437687812979037411280601533114982523785419296758136139509382198582885244540696938622354567177892442689599309587576843156061488346717758801158770339319840441612025575855171797816583328592905878511468146202317893737435863602638296836136237843437631810454554154509
q = 95772726941712640001723837214303342002655355883327084521146440778536040744156583801926753814805595606410443413875301543467626805737472254844755121382615457766647100894815371282833364196117624639846104685189532693331432093753023513388892151349214843110728202212644881166427749140369961129200252767068764047509
Our next step is to find d, so let's figure out phi(n) first:
print ( (p-1) * (q-1))
Then using this very convenient website: https://www.dcode.fr/modular-inverse, we can find the inverse mod of e % phi(n) such that ed % phi(n) = 1 % phi(n)
```python
inverse = 5141062249513715946153800780632620342918589072789293217213972409054552544373832544517533216197038038392717669780512482131389996444959078242406928069925701319492171955140391522572844409339829106761285357332827175586034785791414777165108561893066773535747648616132422820945297592939480332814627292211833752228378560999887798792315294172477699708982744635470448446106713526842510162267181744091394628348249394415336809068773772442831176518573694241613311822362134944149830336638587817606293872623820094954358712702694944464748725461699328762569180235802278317135900918040617602766699607353178525136810867902283307196801
ans = pow (m,inverse,n) # decrypting the message
print (p * q == n) # double checking p and q are right
print(long_to_bytes(ans).decode())
# FwordCTF{i_knew_it_its_not_secure_as_i_thought}
```
Voila! we now have the flag!
