python - 使用大 key 的 RSA 解密

标签 python math encryption rsa large-data

我的问题:我已经知道 RSA 系统的私钥和公钥,而且我有一条加密消息,但我无法解密它,因为我的私钥指数约为 1024 位。如果需要详细信息,我的数据如下,但问题是如何在简单的家用 PC 上使用长 key 解密消息。

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

其中c为密文,N为模,ed分别为公开指数和私有(private)指数, pq 是质数(我想是,但很难检查)。

我已经尝试使用在线服务,例如 this和其他几个。 同样在我的电脑上,我使用了 python rsa library但它因错误而失败。 我假设以下公式无处不在(假设 m 代表明文):

m = c**d % N

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

所以也许从数学的角度有更聪明的方法来更快地计算这个m,或者可以解决它的在线服务,或者图书馆。还是只有 super 计算机才能计算出1024位指数的RSA解密?

数据取自CTF上下文picoctf。

最佳答案

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

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

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

哪个给

0x436f6e67726174756c6174696f6e73206f6e2064656372797074696e6720616e20525341206d6573736167652120596f757220666c6167206973206d6f64756c61725f61726974686d65746963735f6e6f745f736f5f6261645f61667465725f616c6c

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

关于python - 使用大 key 的 RSA 解密,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26681374/

相关文章:

java - 是否可以使用 Java 加密体系结构访问 SCrypt?

python - 将 file_name 参数传递给管道以在 scrapy 中导出 csv

c# - 重建相机 "Look At"功能的矩阵变换

python - 将 requests.get() 输出解析为 Pandas 数据框

c++ - 是否存在满足以下条件的哈希函数

algorithm - 如何计算某物是否在某人的视野中

security - AES 与 Blowfish 文件加密

java - 如何强制 CipherOutputStream 完成加密但保持底层流打开?

python - 如何居中 Tkinter 小部件?

python - 在数据框中显示 NER Spacy 数据