# <https://git.lain.faith/BLAHAJ/writeups/src/branch/writeups/2021/corctf/4096>
# 4096
by [haskal](https://awoo.systems)
crypto / 360 pts / 219 solves
>I heard 4096 bit RSA is secure, so I encrypted the flag with it.
provided files: [source.py](https://git.lain.faith/BLAHAJ/writeups/src/branch/writeups/2021/corctf/4096/source.py) [output.txt](https://git.lain.faith/BLAHAJ/writeups/src/branch/writeups/2021/corctf/4096/output.txt)
## solution
inspecting the source you can see the provided source implements RSA. the weakness is it uses manysmall primes instead of 2 large primes. this makes it extremely easy to factor the number(factoring the public key in RSA leads to recovery of the private key)[^1]
```pythonm = bytes_to_long(flag)primes = [getPrime(32) for _ in range(128)]n = prod(primes)e = 65537print(n)print(pow(m, e, n))```
i turned to my trusted factoring tool, [yafu](https://sourceforge.net/projects/yafu/) and _quickly_discovered that in 2021 yafu is very crashy (at least on my system... i assume this is some glibc orgmp ABI incompatibility)[^2]
yafu provides a shell in which you can invoke the `factor` operation```factor(50630448182626893495....)```
this should complete in a few seconds even on old machines. it produces a list like```...P10 = 3991834969P38 = 66683226414537879762507759703783429499C20 = 15613277632742914627P10 = 3959814431P10 = 3943871257P10 = 2602521199P10 = 3177943303P10 = 3625437121P10 = 2707095227P10 = 3346647649P10 = 2572542211P10 = 2753147143P10 = 3488338697P10 = 2525697263P10 = 3291377941P10 = 4141964923...```
some of the output was not factored enough, there are still some composite numbers and incorrectlyidentified primes -- we know from the source that all the primes are 32 bit so we're looking for all`P10` lines. the solution is simple just run `factor(...)` again on any non-P10 outputs... and thisis where i wrote a quick script to do this automatically except for some reason yafu consistentlycrashed when run under python (;___;) so i ended up doing it by hand (time wasted that could bespent pwning but whatever)
anyway once you have all the primes you just need to calculate the private key and do decryption.the private key is computed by `65537^{-1} mod phi`, where `phi` (the easier one to calculate) isthe product of all the primes minus 1. then do `{encrypted message}^d mod n` and you have the flag
```python[ins] In [1]: import math
[nav] In [2]: factors = [int(x) for x in open("factors")]
[nav] In [3]: phi = math.prod([x - 1 for x in factors])
[nav] In [4]: [n, enc] = [int(x) for x in open("output.txt")]
[ins] In [5]: d = pow(65537, -1, phi)
[ins] In [6]: dec = pow(enc, d, n)
[ins] In [7]: dec.to_bytes(dec.bit_length()//8+1,"big")Out[8]: b'corctf{to0_m4ny_pr1m3s55_63aeea37a6b3b22f}'```
[^1]: i assume we are familiar with RSA but if not, wikipedia is a good reference:  <https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Operation>
[^2]: time to get a new factoring tool of choice probably