使用大密钥进行RSA解密

Question

我的问题:我已经知道RSA系统的私钥和公钥,我有一个加密的消息,但我不能解密它,因为我的私有指数大约是1024位.如果需要详细信息,我的数据会跟随,但问题是如何在简单的家用PC上解密带有长按键的消息.

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

这里c是密文,N是模块,e并d分别为公共和私人指数和p和q是素数(我想是这样,但它是很难检查).

我已经尝试过使用像这样的在线服务和其他几个.另外在我的电脑上我使用了python rsa库,但是它失败了.我想在任何地方使用以下公式(假设m代表明文):

m = c**d % N

要么

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

因此,从数学的角度来看,可能有更聪明的方法来m更快地计算,或者可以解决它的在线服务,或者库.或者只有超级计算机可以计算1024位指数RSA解密？

数据来自CTF上下文picoctf.

Answer 1

首先,我真的希望(a)这不是重要信息,(b)你不会再次使用这个密钥对,因为我现在可以解密这个密文以及发送给你的任何其他加密消息它.

我们可以在python中解码消息(产生十六进制编码的字符串),如下所示:

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

这使

0x436f6e67726174756c6174696f6e73206f6e2064656372797074696e6720616e20525341206d6573736167652120596f757220666c6167206973206d6f64756c61725f61726974686d65746963735f6e6f745f736f5f6261645f61667465725f616c6c

内置pow函数通过平方来使用取幂来有效地计算以整数为模的大功率.如果不通过平方及其变体进行取幂,使用任何依赖于离散对数问题的非对称密钥算法(大多数但不是全部)都是不可行的.它实际上很容易实现,我强烈建议你这样做.阅读维基百科文章了解更多信息.