Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.md
RSA.sagews
message.txt

README.md

RSA (crypto, 300p)

In the challenge we get a sage code with some basic RSA encryption, and a couple of messages and keys.

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:

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}

You can’t perform that action at this time.