# Relatively Simple Algorithm
## Challenge:
[RSA](https://files.actf.co/02208dfa3190c917bbcc540d0294dab88def3260ece9f9e56f4f17f4aea8eb27/rsa.txt) strikes strikes again again! [Source](https://files.actf.co/e2f71f1cfbdd339cf985abfe3ffec102b160bbce27ac98eb3ce0729be73e5102/rsa.py)
## Solution:
We're given some code:
```pythonfrom Crypto.Util.number import getStrongPrimef = [REDACTED]m = int.from_bytes(f,'big')p = getStrongPrime(512)q = getStrongPrime(512)n = p*qe = 65537d = pow(e,-1,(p-1)*(q-1))c = pow(m,e,n)print("n =",n)print("p =",p)print("q =",q)print("e =",e)print("c =",c)%```
And our ciphertext:
```pythonn = 113138904645172037883970365829067951997230612719077573521906183509830180342554841790268134999423971247602095979484887092205889453631416247856139838680189062511282674134361726455828113825651055263796576482555849771303361415911103661873954509376979834006775895197929252775133737380642752081153063469135950168223p = 11556895667671057477200219387242513875610589005594481832449286005570409920461121505578566298354611080750154513073654150580136639937876904687126793459819369q = 9789731420840260962289569924638041579833494812169162102854947552459243338614590024836083625245719375467053459789947717068410632082598060778090631475194567e = 65537c = 108644851584756918977851425216398363307810002101894230112870917234519516101802838576315116490794790271121303531868519534061050530562981420826020638383979983010271660175506402389504477695184339442431370630019572693659580322499801215041535132565595864123113626239232420183378765229045037108065155299178074809432%```
The `d =` in our source code is a clue. We don’t use it at all in the encryption, but we can calculate that value for our decryption:
```python>>> n = 113138904645172037883970365829067951997230612719077573521906183509830180342554841790268134999423971247602095979484887092205889453631416247856139838680189062511282674134361726455828113825651055263796576482555849771303361415911103661873954509376979834006775895197929252775133737380642752081153063469135950168223>>> p = 11556895667671057477200219387242513875610589005594481832449286005570409920461121505578566298354611080750154513073654150580136639937876904687126793459819369>>> q = 9789731420840260962289569924638041579833494812169162102854947552459243338614590024836083625245719375467053459789947717068410632082598060778090631475194567>>> e = 65537>>> c = 108644851584756918977851425216398363307810002101894230112870917234519516101802838576315116490794790271121303531868519534061050530562981420826020638383979983010271660175506402389504477695184339442431370630019572693659580322499801215041535132565595864123113626239232420183378765229045037108065155299178074809432>>> d = pow(e,-1,(p-1)*(q-1))>>> hex(pow(c,d,n)).rstrip("L")'0x616374667b6f6c645f6275745f7374696c6c5f676f6f645f77656c6c5f61745f6c656173745f756e74696c5f7175616e74756d5f636f6d707574696e677d'>>> bytearray.fromhex("616374667b6f6c645f6275745f7374696c6c5f676f6f645f77656c6c5f61745f6c656173745f756e74696c5f7175616e74756d5f636f6d707574696e677d").decode()'actf{old_but_still_good_well_at_least_until_quantum_computing}'```
And now we have our flag: `actf{old_but_still_good_well_at_least_until_quantum_computing}`.