CODEWITHSUNDEEP
pythonmathencryptionrsalarge-data
user2872765
user2872765

Reputation: 33

RSA decryption with large keys

My problem: I already know the private and public key of an RSA system and I have an encrypted message but I can't decrypt it, because my private exponent is about 1024 bit. My data is following if it is needed for details but the question is how to decrypt a message with long keys on a simple home PC.

N = 0xb197d3afe713816582ee988b276f635800f728f118f5125de1c7c1e57f2738351de8ac643c118a5480f867b6d8756021911818e470952bd0a5262ed86b4fc4c2b7962cd197a8bd8d8ae3f821ad712a42285db67c85983581c4c39f80dbb21bf700dbd2ae9709f7e307769b5c0e624b661441c1ddb62ef1fe7684bbe61d8a19e7
e = 65537
p = 0xc315d99cf91a018dafba850237935b2d981e82b02d994f94db0a1ae40d1fc7ab9799286ac68d620f1102ef515b348807060e6caec5320e3dceb25a0b98356399
q = 0xe90bbb3d4f51311f0b7669abd04e4cc48687ad0e168e7183a9de3ff9fd2d2a3a50303a5109457bd45f0abe1c5750edfaff1ad87c13eed45e1b4bd2366b49d97f
d = 0x496747c7dceae300e22d5c3fa7fd1242bda36af8bc280f7f5e630271a92cbcbeb7ae04132a00d5fc379274cbce8c353faa891b40d087d7a4559e829e513c97467345adca3aa66550a68889cf930ecdfde706445b3f110c0cb4a81ca66f8630ed003feea59a51dc1d18a7f6301f2817cb53b1fb58b2a5ad163e9f1f9fe463b901
c = 0x58ae101736022f486216e290d39e839e7d02a124f725865ed1b5eea7144a4c40828bd4d14dcea967561477a516ce338f293ca86efc72a272c332c5468ef43ed5d8062152aae9484a50051d71943cf4c3249d8c4b2f6c39680cc75e58125359edd2544e89f54d2e5cbed06bb3ed61e5ca7643ebb7fa04638aa0a0f23955e5b5d9

where c is ciphertext, N is module, e and d are public and private exponents respectively and p and q are primes (I suppose so, but it is hard to check).

I already tried to use online services like this and several others. Also on my PC I have used python rsa library but it fails with errors. I suppose the following formula is used everywhere (suppose m stands for plaintext):

m = c**d % N

or

m = 1
for i in xrange(d):
    m = (m * c) % N

So maybe there is a more clever way from a mathematical point of view to calculate this m faster, or an online service that can solve it, or a library. Or it is possible only for supercomputers to calculate 1024 bit exponent RSA decryption?

Data is taken from CTF context picoctf.

Upvotes: 3

Views: 8692

Answers (1)

sju
sju

Reputation: 258

First of all, I really hope that (a) this isn't important information and (b) you're not going to ever use this key pair again, because I can now decrypt this ciphertext and any other encrypted message sent to you with it.

We can decode the message in python (resulting in a hex-encoded string) as follows:

m = hex(pow(c, d, N)).rstrip("L")

Which gives

0x436f6e67726174756c6174696f6e73206f6e2064656372797074696e6720616e20525341206d6573736167652120596f757220666c6167206973206d6f64756c61725f61726974686d65746963735f6e6f745f736f5f6261645f61667465725f616c6c

The builtin pow function uses exponentiation by squaring to efficently compute large powers modulo an integer. Without exponentiation by squaring and its variants, the use of any asymmetric key algorithm which relies on the Discrete Logarithm problem (which is most, but not all, of them) is infeasible. It's actually quite easy to implement, and I strongly recommend that you do so. Read the wikipedia article for more information.

Upvotes: 10

Related Questions