# 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 % nSince 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 SolutionNow, 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 rsawith 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 becomesGreat! Now we know k1 < e and we can brute force k1 to find p!
    dp = 15863941351022675271470498055440018518890999065008090553947887331349060559165417151482111730533900341104699951315612031296744594701865438849657867331942686064408344200992596897731186704102476529429339278690748746609131178367030814132224462991833270965841136411444101247903371020388961422615207080090040311385
    n = 13795029341892417374839569348195219432273811499483782737330171543244685968744999323208547919665299783906957825270449006773866123362810477840346497089695409735324208705537006191240439897433032270300293091365930830592120936636584926755229275335158742925495154248094930986582540466282129158682944188080860981812852232204308214285109566958749409476615914322197257558630214751391486659657892675174292657801181344004269336582824495524735592639617122904261904725149320803824393890508587709714045126033113995823573370380507690572913971259051956543607099582177007672826620386223089090352147939487203095545319421169070202568081    m = 4577483075923691025614837387199959169275891010490317043142964745465946594734541383793196135840379923558282553847958293921035008363297701769706082343316794998794846094470932254663483885231325059503550992175528744843034602900645069686396280989390227810555558579302943585247037825841710062260608576583049065083988456565702297252837653658501925749752005065311426953256044460166446107914200467201439311812471408454665833883066991637851573154466515181854296188872448618848136386704796559645721088729635821840733708277778529467678390494522595775876496533057623112322654282130317608735511663306372475467872142100508022014379  
```pythonfor 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)  ```pythoninverse = 5141062249513715946153800780632620342918589072789293217213972409054552544373832544517533216197038038392717669780512482131389996444959078242406928069925701319492171955140391522572844409339829106761285357332827175586034785791414777165108561893066773535747648616132422820945297592939480332814627292211833752228378560999887798792315294172477699708982744635470448446106713526842510162267181744091394628348249394415336809068773772442831176518573694241613311822362134944149830336638587817606293872623820094954358712702694944464748725461699328762569180235802278317135900918040617602766699607353178525136810867902283307196801ans = pow (m,inverse,n)  # decrypting the messageprint (p * q == n)  # double checking p and q are rightprint(long_to_bytes(ans).decode())# FwordCTF{i_knew_it_its_not_secure_as_i_thought}```Voila! we now have the flag!