Rating:
## NSA Backdoor (500 pts)
> I heard someone has been sneakily installing backdoors in open-source implementations of Diffie-Hellman... I wonder who it could be... ;)
>
> - gen.py
> - output.txt
The script uses the same prime generation functions as the one from **Very Smooth** problem. But, unlike that problem, the `c` here uses the flag as the exponent instead of the base, and there is no `e` that is coprime with `p-1` and `n-1`. Also, this is a bad Diffie-Hellman implementation because the modulus `n` is not a prime. This is the [backdoor](https://www.cryptologie.net/article/360/how-to-backdoor-diffie-hellman-quick-explanation/) of the implementation.
```text
n = d63c7cb032ae4d3a43ecec4999cfa8f8b49aa9c14374e60f3beeb437233e44f988a73101f9b20ffb56454350b1c9032c136142220ded059876ccfde992551db46c27f122cacdd38c86acb844032f8600515aa6ccb7a1d1ac62d04b51b752476d2d6ee9f22d0f933bebdd833a71fd30510479fcc7ba0afb1d4b0a1622cdc2a48341010dffdcfc8d9af45959fb30b692dc2c9e181ac6bcd6a701326e3707fb19b7f9dfe1c522c68f9b0d229d384be1e1c58f72f8df60ca5172a341a7ee81428a064beedd6af7b89cc6079f2b6d3717f0d29330f0a70acca05bf67ab60c2e5cb0b86bfca2c9b8d50d79d24371432a1efb243f3c5f15b377ccc51f6e69bfbf5ecc61
c = 51099773fd2aafd5f84dfe649acbb3558797f58bdc643ac6ee6f0a6fa30031767966316201c36be69241d9d05d0bd181ced13809f57b0c0594f6b29ac74bc7906dae70a2808799feddc71cf5b28401100e5e7e0324b9d8b56e540c725fa4ef87b9e8d0f901630da5f7f181f6d5b4cdc00d5f5c3457674abcb0d0c173f381b92bdfb143c595f024b98b9900410d502c87dfc1633796d640cb5f780fa4b6f0414fb51e34700d9096caf07b36f4dcd3bb5a2d126f60d3a802959d6fadf18f4970756f3099e14fa6386513fb8e6cdda80fdc1c32a10f6cdb197857caf1d7abf3812e3d9dcda106fa87bac382d3e6fc216c55da02a0c45a482550acb2f58bea2cfa03
```
The `c` was calculated as `3 ^ flag mod n`. So `g` in this Diffie-Hellman exchange is 3.
What I need to do first is to set `d` and `e` such that `d = 5 ^ e mod n`
Since `n` is not a prime number, I needed to make use of [Pohlig-Hellman algorithm](https://risencrypto.github.io/PohligHellman/) to recover the flag.
After numerous trials, I got the [script](https://github.com/leeyonjae/CTF_writeups/blob/main/picoCTF2022/solutions/nsa-backdoor.py) to solve this problem.
1. Since `n = p * q`, I found the Pohlig-Hellman values for `p` and `q`.
2. Then I reduced the latter to the remainder of dividing by `(q - 1) / 2`.
3. I used the [Chinese Remainder Theorem](https://brilliant.org/wiki/chinese-remainder-theorem/) to calculate the value of the flag.
4. Finally, I decoded the hexadecimal form of the flag to ASCII string.
**Flag: `picoCTF{1ca93858}`**
