Rating:
## crypto/rsaoutro
>Author: @Gary#4657
>
>154 solves / 377 points
*Note: Below you'll find a guided solution. If interested just in the solve script, click [here](#solve-script-cryptorsaoutro)*
Provided for download are two challenge files: `gen.py` and `output.txt`. When we open `gen.py` we can see the following code:
```python
from Crypto.Util.number import getStrongPrime, isPrime, inverse, bytes_to_long as b2l
FLAG = open('flag.txt', 'r').read()
# safe primes are cool
# https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes
while True:
q = getStrongPrime(512)
p = 2*q + 1
if (isPrime(p)):
break
n = p*q
phi = (p-1)*(q-1)
e = 0x10001
d = inverse(e, phi)
pt = b2l(FLAG.encode())
ct = pow(pt,e,n)
open('output.txt', 'w').write(f'e: {e}\nd: {d}\nphi: {phi}\nct: {ct}')
```
An interesting implementation of RSA with only the public exponent not being written to the output file. And if we take a look into the output file we get exactly what's expected:
```python
e: 65537
d: 53644719720574049009405552166157712944703190065471668628844223840961631946450717730498953967365343322420070536512779060129496885996597242719829361747640511749156693869638229201455287585480904214599266368010822834345022164868996387818675879350434513617616365498180046935518686332875915988354222223353414730233
phi: 245339427517603729932268783832064063730426585298033269150632512063161372845397117090279828761983426749577401448111514393838579024253942323526130975635388431158721719897730678798030368631518633601688214930936866440646874921076023466048329456035549666361320568433651481926942648024960844810102628182268858421164
ct: 37908069537874314556326131798861989913414869945406191262746923693553489353829208006823679167741985280446948193850665708841487091787325154392435232998215464094465135529738800788684510714606323301203342805866556727186659736657602065547151371338616322720609504154245460113520462221800784939992576122714196812534
```
Since we already have the privete exponent d, the only thing we need is n and we'll be able to get the flag by the looks of it.
#### Derieving n
By looking at the code we notice one important thing:
```python
p = 2*q + 1
```
And since we know that:
```python
phi = (p - 1) * (q - 1)
```
We can use this to derieve p or q just by using some simple math. If we have:
$$phi = (p - 1) * (q - 1)$$
$$p = 2*q + 1$$
We can combine these equations like:
$$phi = ((2*q + 1) - 1) * (q - 1)$$
$$phi = 2*q * (q - 1)$$
$$phi = 2 * q^{2} - 2 * q$$
$$2 * q^{2} - 2 * q - phi = 0$$
This is now a basic quadratic equation that we can solve for q. I used [SageMath](https://www.sagemath.org/) to do that:
```python
eq = 2*x^2 - 2*x - 24533942751... == 0
solve(eq, x)
[x == -1107563604..., x == 1107563604...]
```
Now we can just take the positive value for `x` and use it to calculate the values for p and n and then get the flag.
### Solve script (crypto/rsaoutro)
Here we can just take all the values given in the `output.txt` file and the value for q we calculated and code them into the script. Finally we can just use standard RSA to decrypt the flag:
```python
#!/bin/python
from Crypto.Util.number import long_to_bytes
e = 65537
d = 53644719720574049009405552166157712944703190065471668628844223840961631946450717730498953967365343322420070536512779060129496885996597242719829361747640511749156693869638229201455287585480904214599266368010822834345022164868996387818675879350434513617616365498180046935518686332875915988354222223353414730233
phi = 245339427517603729932268783832064063730426585298033269150632512063161372845397117090279828761983426749577401448111514393838579024253942323526130975635388431158721719897730678798030368631518633601688214930936866440646874921076023466048329456035549666361320568433651481926942648024960844810102628182268858421164
ct = 37908069537874314556326131798861989913414869945406191262746923693553489353829208006823679167741985280446948193850665708841487091787325154392435232998215464094465135529738800788684510714606323301203342805866556727186659736657602065547151371338616322720609504154245460113520462221800784939992576122714196812534
q = 11075636043081312130072482386894153179906741704107014422233346592319924162396870630618684638610997030440993794793932027132363928350671662212985373363848339
p = 2 * q + 1
n = p * q
p = pow(ct, d, n)
print(long_to_bytes(p).decode())
```
After running the script we get the decrypted output: `flag{8b76b85e7f450c39502e71c215f6f1fe}`.
