Rating:
# RSA Mod
##### An encrypted RSA message has been intercepted. Can you find a way to decrypt it?
We have are given a .txt with the following:
```
{'n': '0xa96e6f96f6aedd5f9f6a169229f11b6fab589bf6361c5268f8217b7fad96708cfbee7857573ac606d7569b44b02afcfcfdd93c21838af933366de22a6116a2a3dee1c0015457c4935991d97014804d3d3e0d2be03ad42f675f20f41ea2afbb70c0e2a79b49789131c2f28fe8214b4506db353a9a8093dc7779ec847c2bea690e653d388e2faff459e24738cd3659d9ede795e0d1f8821fd5b49224cb47ae66f9ae3c58fa66db5ea9f73d7b741939048a242e91224f98daf0641e8a8ff19b58fb8c49b1a5abb059f44249dfd611515115a144cc7c2ca29357af46a9dc1800ae9330778ff1b7a8e45321147453cf17ef3a2111ad33bfeba2b62a047fa6a7af0eef', 'e': '0x10001', 'ct': '0x310ffa2576c3f1a193f625010cc41c21dac0022710e9c42916b81f60579738d833700faa94572bfc57eeec8b961ce6b1ec03d659ea9da71293d19419be1f2193a797c4eb933ff5a405443b1f4151fc253d4738c19c7cf0ed39e8624511d777b7fc7a866a3812ab4cc19038ca3a18f8e1f9df46dade804b9a3dc679726ef08a67576351aad20a60666623a26de367d41c56d21ed72c3402e66290e43fd87e277154de4ff2b2490bb599574b296c714afe090dba33f8e1e21b01bafab104f527bca35be930136d8df33fe81e7d87bb1b3b3ee45cc2614cfc61873e162d6521b230d7243748b229fda2d1d4e5f5f3def6349176f76876238ed3d8e1d6378a055767'}
{'n': '0xa96e6f96f6aedd5f9f6a169229f11b6fab589bf6361c5268f8217b7fad96708cfbee7857573ac606d7569b44b02afcfcfdd93c21838af933366de22a6116a2a3dee1c0015457c4935991d97014804d3d3e0d2be03ad42f675f20f41ea2afbb70c0e2a79b49789131c2f28fe8214b4506db353a9a8093dc7779ec847c2bea690e653d388e2faff459e24738cd3659d9ede795e0d1f8821fd5b49224cb47ae66f9ae3c58fa66db5ea9f73d7b741939048a242e91224f98daf0641e8a8ff19b58fb8c49b1a5abb059f44249dfd611515115a144cc7c2ca29357af46a9dc1800ae9330778ff1b7a8e45321147453cf17ef3a2111ad33bfeba2b62a047fa6a7af0eef', 'e': '0x23', 'ct': '0xd646418a1491d8b7c970e3ede9fb997076a0be6b04e42d0ce0d9eb6658c59306a6794154539309708bc86afca5b8258774f644cb5894e7bd04352baf8a7a19b37157cf6cc47659aa3d8dab1b8056067a3cbaba97b6e3316d10eadabe7d14c0ba41c5b55dc8e8bddc88340e47765d12b6537c65f20aca56afc2e586b9b77f7bb43f3ee07fd4549cc591fd22270a3dbe23a158b0048090a5ce62d425299ae17123dd56b8bbf6fce700c61718ae2e723335936fb57b1a6c560a70a637cf5551bd9b9bdef02c0ee7973cb8522441b61e0d46d773fcf4b24ea2f4549e71ff8b2185e215fa00ba6a9f60312e5eee6c7c2b624cf45b65de56c0e4fc00bff55e1529733'}
```
We can see that the n's are the same for both ciphertexts, but the e's are different, this is a **common modulus attack** (i explain it in more depth [here](https://github.com/DoomHackCTF/WriteUps/tree/main/1337CTF/Crypto/Equality)).
```python
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, GCD
from ast import literal_eval
def extended_gcd(a, b):
if a == 0:
return b, 0, 1
else:
gcd, x, y = extended_gcd(b % a, a)
return gcd, y - (b // a) * x, x
n = '0xa96e6f96f6aedd5f9f6a169229f11b6fab589bf6361c5268f8217b7fad96708cfbee7857573ac606d7569b44b02afcfcfdd93c21838af933366de22a6116a2a3dee1c0015457c4935991d97014804d3d3e0d2be03ad42f675f20f41ea2afbb70c0e2a79b49789131c2f28fe8214b4506db353a9a8093dc7779ec847c2bea690e653d388e2faff459e24738cd3659d9ede795e0d1f8821fd5b49224cb47ae66f9ae3c58fa66db5ea9f73d7b741939048a242e91224f98daf0641e8a8ff19b58fb8c49b1a5abb059f44249dfd611515115a144cc7c2ca29357af46a9dc1800ae9330778ff1b7a8e45321147453cf17ef3a2111ad33bfeba2b62a047fa6a7af0eef'
e1 = '0x10001'
ct1 = '0x310ffa2576c3f1a193f625010cc41c21dac0022710e9c42916b81f60579738d833700faa94572bfc57eeec8b961ce6b1ec03d659ea9da71293d19419be1f2193a797c4eb933ff5a405443b1f4151fc253d4738c19c7cf0ed39e8624511d777b7fc7a866a3812ab4cc19038ca3a18f8e1f9df46dade804b9a3dc679726ef08a67576351aad20a60666623a26de367d41c56d21ed72c3402e66290e43fd87e277154de4ff2b2490bb599574b296c714afe090dba33f8e1e21b01bafab104f527bca35be930136d8df33fe81e7d87bb1b3b3ee45cc2614cfc61873e162d6521b230d7243748b229fda2d1d4e5f5f3def6349176f76876238ed3d8e1d6378a055767'
e2 = '0x23'
ct2 = '0xd646418a1491d8b7c970e3ede9fb997076a0be6b04e42d0ce0d9eb6658c59306a6794154539309708bc86afca5b8258774f644cb5894e7bd04352baf8a7a19b37157cf6cc47659aa3d8dab1b8056067a3cbaba97b6e3316d10eadabe7d14c0ba41c5b55dc8e8bddc88340e47765d12b6537c65f20aca56afc2e586b9b77f7bb43f3ee07fd4549cc591fd22270a3dbe23a158b0048090a5ce62d425299ae17123dd56b8bbf6fce700c61718ae2e723335936fb57b1a6c560a70a637cf5551bd9b9bdef02c0ee7973cb8522441b61e0d46d773fcf4b24ea2f4549e71ff8b2185e215fa00ba6a9f60312e5eee6c7c2b624cf45b65de56c0e4fc00bff55e1529733'
n = (literal_eval(n))
e1 = (literal_eval(e1))
e2 = (literal_eval(e2))
ct = (literal_eval(ct1))
ct2 = literal_eval(ct2)
gdc, u,v = extended_gcd(e1,e2)
ct2_inv = (inverse(ct2, n))
m = (pow(ct, u, n) * pow(ct2_inv, -v, n)) % n
print(long_to_bytes(m))
```
```shell
❯ python solve.py
b'Welcome to OFPPT-CTF Event. Congratulations! You just decrypted an encrypted rsa message. Your flag is: OFPPT-CTF{R$4_M0d_4tt4cks_4re_4n0th3r_Cl4ss1c_Vuln3r4b1l17y}'
```
