Tags: rsa
Rating:
# Really Secure Algorithm
30 points - 548 Solves
```
I found this flag somewhere when I was taking a walk, but it seems to have been encrypted with this Really Secure Algorithm!
```
## Solution
In this challenge, we are given the content
```
p = 8337989838551614633430029371803892077156162494012474856684174381868510024755832450406936717727195184311114937042673575494843631977970586746618123352329889
q = 7755060911995462151580541927524289685569492828780752345560845093073545403776129013139174889414744570087561926915046519199304042166351530778365529171009493
e = 65537
c = 7022848098469230958320047471938217952907600532361296142412318653611729265921488278588086423574875352145477376594391159805651080223698576708934993951618464460109422377329972737876060167903857613763294932326619266281725900497427458047861973153012506595691389361443123047595975834017549312356282859235890330349
```
The cryptosystem used here is RSA. The whole point of security in RSA lies how strong the modulus n is. n is ideally the product of two strong primes. If those two primes are known, the whole cryptosystem is broken.
The primes here are `p` and `q` both of them being provided due to the generosity of the creator of this challenge. I ideally use Sage to solve most crypto / math related problems.
To solve it, we essentially need to know the RSA equations. As this is not a RSA 101 Tutorial, the exploration of the equations is left to the reader.
But, our goal here is to decrypt the cipher-text `c` to plain-text thus giving us the flag.
Hence, I code the following, save it as `solve.sage`
```python
p = 8337989838551614633430029371803892077156162494012474856684174381868510024755832450406936717727195184311114937042673575494843631977970586746618123352329889
q = 7755060911995462151580541927524289685569492828780752345560845093073545403776129013139174889414744570087561926915046519199304042166351530778365529171009493
e = 65537
c = 7022848098469230958320047471938217952907600532361296142412318653611729265921488278588086423574875352145477376594391159805651080223698576708934993951618464460109422377329972737876060167903857613763294932326619266281725900497427458047861973153012506595691389361443123047595975834017549312356282859235890330349
phi = (p-1)*(q-1)
n = p*q
d = e.inverse_mod(phi)
p = int(pow(c,d,n))
print hex(p)[2:-1].decode('hex')
```
And after running it as the follow, we will receive the flag
```
$sage solve.sage
```
#### actf{really_securent_algorithm}
