# RSAyyyy [Reverse 358 points]
### Chall's description```This challenge is designed to give an overviewof the RSA algorithm. If you have a team memberthat is less familiar with RSA that wants to be,give this challenge to them. This might be useful.
nc 3.16.57.250 12345```#### Link[RSA\_link](https://en.wikipedia.org/wiki/RSA_(cryptosystem))
## SolutionThis is a "educational" chall; we enjoyed to do it to `refresh` our RSA knowledge.There are multiple tasks that help you to understand how RSA works (with some math's help)
### Level 1: Calculating```bashp = 2800941491q = 4071798539What is n?```
#### Answer```bash11404869470878281649```#### ExplanationFrom the formula n = p*q
### Level 2: Calculating m
```bashmessage = "hover exculpatory broadminded Bromley constructible"What is m?```
#### Answer```269678299779785121551311846594485190570778179799456098570707555275403511188378404406315707027746721729831218463132835015781
Congratulations! You beat Level 2!
Now, we are going to actually calculate ciphertext.```
#### Explanation(Code)```pythonmessage = "hover exculpatory broadminded Bromley constructible"
''.join([hex(ord(x))[2:] for x in message])             # <--- hex valueint(''.join([hex(ord(x))[2:] for x in message]),16)     # <--- int value```
### Level 3: Calculating c```bash p = 2871875029q = 3482439599What is n?#1              <===
Ayyyyy
e = 65537m = 7089056601674313572What is c?#2              <===
Ayyyyy
Congratulations! You beat Level 3!
In order for RSA to be asymmetrical,the private exponent, d, needs to be calculated.```
#### Answer and Explanation```#1For the formula n = p*qn = 2871875029 * 3482439599  = 10001131324368873371
#2m^e mod(n) = (7089056601674313572 ** 65537) % 10001131324368873371           = 8733466864177587635```
### Level 4: Calculating d```bashp = 3361037497q = 3507131801What is tot(n)?#1              <===
Whoop whoop!
e = 65537What is d?#2              <===
Nice job!
Congratulations! You beat Level 4!
The easiest way to break RSA is factoring n, if it is possible.```
#### Answer and Explanation```#1For the formula tot(n) = (p-1) * (q-1)tot(n) = (3361037497-1)*(3507131801-1) = 11787601483213972800
#2e = 65537tot(n) = 11787601483213972800mulinv(e, tot(n)) = 1841065181228591873```
#### Code from [Wikibooks](https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm)```pythondef xgcd(b, a):    x0, x1, y0, y1 = 1, 0, 0, 1    while a != 0:        q, b, a = b // a, a, b % a        x0, x1 = x1, x0 - q * x1        y0, y1 = y1, y0 - q * y1    return  b, x0, y0
# x = mulinv(b) mod n, (x * b) % n == 1def mulinv(b, n):    g, x, _ = xgcd(b, n)    if g == 1:        return x % n
print(mulinv(65537, 11787601483213972800))```
#### Link[Extended\_Euclidean\_algorithm](https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm)\[Modular\_multiplicative\_inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse)
### Level 5: Factoring n```bashn = 9613631774438905337What is p?```
#### Answer```3536763563
Ayyyyy
Congratulations! You beat Level 5!
Now, let's put everything together and break RSA!```
#### Explanation```[[[on Wolframalpha]]]factor 9613631774438905337
Result:2718200299 x 3536763563 (2 distinct prime factors)
-> 9613631774438905337 / 2718200299 = 3536763563
I think you could use the other number as the answer but I didn't test it.```
#### Link[WolframAlpha](https://www.wolframalpha.com/)
### Level 6: Breaking simple RSA```bashc = 1940747889140053401n = 11191414813257978223e = 65537What is p?#1              <===
That was adequate.
What is q?#2              <===
Way to go!
What is tot(n)?#3              <===
Whoop whoop!
What is d?#4              <===
Ayyyyy
Finally, what is m?#5              <===
Nice job!
Congratulations! You beat Level 6!
Congratulations on finishing this introduction to RSA!I hope this was fun and informative.
Here's your flag:TUCTF{RSA_1$_R34LLY_C00L_4ND_1MP0RT4NT_CRYPT0}```
#### Code and Tools
##### Answer and Explanation```bash#12749593919 (see below how we catch this result)
#2From the formula n = p*q -> q = n/pq = int(11191414813257978223/2749593919) = 4070206417
#3From the formula tot(n) = (p-1) * (q-1)tot(n) = (2749593919-1) * (4070206417-1) = 11191414806438177888
#4e = 65537tot(n) = 11191414806438177888d = mulinv(e, tot(n)) = 9196881566601171041 (we reused the solution #5)
#5[[[on Wolframalpha]]](1940747889140053401^9196881566601171041) mod 11191414813257978223Result: 8244229906027274615```
##### RsaCtfTool (#1)```bash./RsaCtfTool.py -n 11191414813257978223 -e 65537 --verbose --private
RsaCtfTool output and redirect on a file:echo '''-----BEGIN RSA PRIVATE KEY-----MD4CAQACCQCbT+R6XklRbwIDAQABAgh/oeMOwpnQYQIFAPKaa9ECBQCj43k/AgUAmB/asQIEa7KhSwIEQovFpw==-----END RSA PRIVATE KEY-----''' > priv.key```
##### Python code (#1)```pythonfrom Crypto.PublicKey import RSA public_key = RSA.importKey(open('priv.key', 'r').read())print(public_key.p)# Answer 2749593919```
# The Flag:    TF{RSA_1$_R34LLY_C00L_4ND_1MP0RT4NT_CRYPT0}
## Refs Summary[RSA\_link](https://en.wikipedia.org/wiki/RSA_(cryptosystem))\[Wikibooks](https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm)\[Extended\_Euclidean\_algorithm](https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm)\[Modular\_multiplicative\_inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse)