TAMUctf 2021 Basic RSA

To: Dr Rivest CC: Dr Shamir

We found this code and these numbers. data.txt Mean anything to you?

Sincerely

  • Dr Adleman
cat data.txt 
N = 2095975199372471
e = 5449
gigem{ 875597732337885 1079270043421597 616489707580218 2010079518477891 1620280754358135 616660320758264 86492804386481 171830236437002 1500250422231406 234060757406619 1461569132566245 897825842938043 2010079518477891 234060757406619 1620280754358135 2010079518477891 966944159095310 1669094464917286 1532683993596672 171830236437002 1461569132566245 2010079518477891 221195854354967 1500250422231406 234060757406619 355168739080744 616660320758264 1620280754358135 }

factor 2095975199372471
2095975199372471: 21094081 99363191

We were able to factor the coprime N with the coreutils program factor. This gives us the ability to decrypt anything encrypted with RSA. There is another solution for if the coprime N was actually large enough that we couldn’t factor it, but I won’t go into that.

p,q = 21094081, 99363191
N = 2095975199372471
e = 5449
a = [int(x) for x in '875597732337885 1079270043421597 616489707580218 2010079518477891 1620280754358135 616660320758264 86492804386481 171830236437002 1500250422231406 234060757406619 1461569132566245 897825842938043 2010079518477891 234060757406619 1620280754358135 2010079518477891 966944159095310 1669094464917286 1532683993596672 171830236437002 1461569132566245 2010079518477891 221195854354967 1500250422231406 234060757406619 355168739080744 616660320758264 1620280754358135'.split()]
phi = (p-1)*(q-1)
import Crypto.Util.number
Crypto.Util.number.inverse(e, phi)
384653161849
d = Crypto.Util.number.inverse(e, phi)
b = [pow(x, d, N) for x in a]
b
[82, 83, 65, 95, 115, 51, 99, 117, 114, 49, 116, 121, 95, 49, 115, 95, 52, 98, 48, 117, 116, 95, 112, 114, 49, 109, 51, 115]
bytes(b)
b'RSA_s3cur1ty_1s_4b0ut_pr1m3s'

As you can see, we are able to get the decryption exponent d using the inverse of the encryption exponent e with the value phi, which is just (p - 1) * (q - 1). Because p and q are private, phi is secured by the factorization of integers. The larger the integer, thee more difficult to factor phi. Unfortunately, this is by no means the only known attack against RSA.

The flag is gigem{RSA_s3cur1ty_1s_4b0ut_pr1m3s}