Tags: cryptography-rsa
Rating:
**Description**
Another message encrypted with RSA. It looks like some parameters are missing. Can you still decrypt it? Message
**Files**
*clue.txt*
```
e = 65537
n = 499607129142614016115845569972309954865466642986629586633467546172800056547903083303297314393486719922392114168964815069281475244480336720618108262665997707387594045170650286331094075335771255196970298123339129317833157961011527832876727076344754954725939644758068479530394261225267979368085014589570504346427
dp = 10223330953817363123811922583649696214606550602104286204220891355717604605964870127334598738896285490397615099445491494493968669242516576783690807635432479
c = 153408111238083132625075217386160278201089187923862024676103784080001237826514301713735771160917544373591779610748265147756784683926730761236534493663419614238905006609729514145435055984994364128927411759418067871721495104602569203564450508769250852903921152143258615277062069536567367247248160384585690407058
```
**Solution**
This was a really fun problem to work through! The first thing we have to notice is that `e` and `dp` are modular inverses of each other `mod (p - 1)`. Because of this, if we take any number `a`, `a^(e * dp) ≡ a mod p`. This cracks the entire problem for us, since if we subtract from both sides, we're left with `a^(e * dp) - a ≡ 0 mod p`, making `a^(e * dp) - a` a multiple of `p`. Now, if we take the GCD of `N` and `a^(e * dp) - a`, we're at a *very* small likelyhood of getting anything other than `p`. Then, if we just divide by `p`, we get `q`, and we can calculate `d` and decrypt the message~
```
>>> from sympy import *
>>> from sympy.core.numbers import igcdex
>>> e = 65537
>>> n = 499607129142614016115845569972309954865466642986629586633467546172800056547903083303297314393486719922392114168964815069281475244480336720618108262665997707387594045170650286331094075335771255196970298123339129317833157961011527832876727076344754954725939644758068479530394261225267979368085014589570504346427
>>> dp = 10223330953817363123811922583649696214606550602104286204220891355717604605964870127334598738896285490397615099445491494493968669242516576783690807635432479
>>> c = 153408111238083132625075217386160278201089187923862024676103784080001237826514301713735771160917544373591779610748265147756784683926730761236534493663419614238905006609729514145435055984994364128927411759418067871721495104602569203564450508769250852903921152143258615277062069536567367247248160384585690407058
>>> p = gcd(n, pow(2, e*dp, n) - 2)
>>> q = n // p
>>> d = long(igcdex(e, (p-1) * (q-1))[0]%n)
>>> hex(pow(c,d,n))[2:-1].decode('hex')
'flag{wow_leaking_dp_breaks_rsa?_47689841281}'
```
And, sure enough, `wow_leaking_dp_breaks_rsa?_47689841281` is the flag! This was one of my favorite challenges in this CTF.
