Tags: common-prime rsa
Rating:
# RSA (crypto, 300p)
In the challenge we get a [sage code](RSA.sagews) with some basic RSA encryption, and [a couple of messages and keys](message.txt).
Each modulus is large, and doesn't seem to be easily factorizable, but since we've a couple of them we can check if they don't share a prime via GCD - and they do.
This means we can use GCD to extract prime factors and recover the private RSA keys and decrypt the messages:
```python
from crypto_commons.rsa.rsa_commons import common_factor_factorization, rsa_printable, modinv
def main():
c1 = 18700320110367574655449823553009212724937318442101140581378358928204994827498139841897479168675123789374462637095265564472109735802305521045676412446455683615469865332270051569768255072111079626023422
e1, n1 = (65537,
23795719145225386804055015945976331504878851440464956768596487167710701468817080174616923533397144140667518414516928416724767417895751634838329442802874972281385084714429143592029962130216053890866347)
c2 = 27979368157170890767030069060194038526134599497456846620984054211906413024410400026053694007247773572972357106574636186987337336771777265971389911503143036021889778839064900818858188026318442675667707
e2, n2 = (65537,
46914096084767238967814493997294740286838053572386502727910903794939283633197997427383196569296188299557978279732421725469482678512672280108542428152186999218210536447287087212703368704976239539968977)
c3 = 24084879450015204136831744759734371350696278325227327049743434712309456808867398488915798176282769616955247276506807739249439515225213919008982824219656080794207250454008942016125074768497986930713993
e3, n3 = (65537,
24543003393712692769038137223030855401835344295968717177380639898023646407807465197761211529143336105057325706788229129519925129413109571220297378014990693203802558792781281981621549760273376606206491)
ciphertexts = [c1, c2, c3]
moduli = [n1, n2, n3]
e = 65537
for na, nb, p in common_factor_factorization(moduli):
index_a = moduli.index(na)
index_b = moduli.index(nb)
print(rsa_printable(ciphertexts[index_a], modinv(e, (p - 1) * (na / p - 1)), na))
print(rsa_printable(ciphertexts[index_b], modinv(e, (p - 1) * (nb / p - 1)), nb))
main()
```
And we get `TMCTF{B3Car3fu11Ab0utTh3K3ys}`
