python - 使用故意弱私钥解密消息无限期挂起

Question

我在从已被故意削弱的私钥生成公钥时遇到问题，并在使用 PyCryptoDome 时尝试加密/解密消息。解密似乎无限期地挂起。

注意：显然这不是我真正的私钥。故意削弱以下键：

以下片段用于读取私钥、派生公钥、加密消息然后再次解密：

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import Crypto.Util
from base64 import *

def encryptMsg(rsakey, message):
    cipher = PKCS1_OAEP.new(rsakey)
    ct = cipher.encrypt(message)
    return ct

def decryptMsg(rsakey, message):
    cipher = PKCS1_OAEP.new(rsakey)
    pt = cipher.decrypt(message)
    return pt

key = RSA.importKey(open('private.key').read())
testpk = key.publickey()
message = b64encode(encryptMsg(testpk, b"test message"))
print(message)
print(decryptMsg(key, b64decode(message)))

这似乎在调用时挂起decryptMsg()。

score 4 · Accepted Answer

您正在给 PyCryptodome 一个带有非常不成比例的素数的私钥，因此这个密钥的安全性基本上被破坏了。您在问题中注意到了这一点，但这里很重要，因为 PyCryptodome 似乎对素数的大小做出了假设。

为了安全起见，RSA 公钥加密通常需要使用两个数量相近的素数：

出于安全目的，整数p和q应该随机选择，并且大小应该相似，但长度应该相差几个数字，以使分解更加困难。

您似乎通过将第二个素数设为一位数值来削弱密钥：

$ openssl rsa -in private.key -text -noout | sed '/prime1:/,/prime2:/!d;/prime2:/q'
prime1:
    29:2b:9a:28:ee:ef:80:1f:0c:86:56:1b:30:c5:06:
    a0:88:08:80:b3:c9:cd:56:18:6a:da:a4:26:99:77:
    19:f4:22:a0:a7:4c:1e:28:d1:20:01:88:5d:23:59:
    5e:7f:0a:b3:cf:38:3a:6a:5b:2a:a6:c7:fd:c4:a1:
    46:7e:3d:10:07:c8:18:79:d1:d1:a1:79:8d:95:fa:
    34:14:b2:36:96:e3:90:ac:d6:5d:01:10:6c:7a:1d:
    8e:94:e5:e5:96:85:c4:a6:54:5b:4f:a4:2d:7a:97:
    dc:7c:50:2f:03:76:72:2b:ee:5c:3a:22:4d:11:b5:
    f8:a3:cd:92:26:85:56:58:40:3d:86:ec:61:28:33:
    81:b2:3f:e5:5e:6a:65:47:a6:78:bd:a0:db:5e:33:
    1c:2f:64:aa:2e:7c:fa:3f:c9:7f:09:44:e5:68:ac:
    83:97:7b:6b:8e:47:3a:64:62:8e:ab:0b:dc:3b:ba:
    81:9d:5f:96:bd:7d:37:0d:f9:48:ce:e4:96:39:b2:
    65:d2:04:19:7c:1c:a7:0e:95:6d:42:ce:74:76:2c:
    7d:13:6a:0e:ce:4d:8a:34:8a:fd:22:f5:ee:5a:4e:
    0c:15:7c:7b:14:bc:c6:a0:cf:a6:74:92:45:a9:d4:
    e5:b4:f3:e3:d0:78:59:38:c4:3f:a0:ac:77:4f:de:
    07
prime2: 5 (0x5)

（p值）是使用 617 位的“适当”大素数，而第二个prime1q素数是单个数字值，因此p大约是 10 ^ 616 倍。使用此密钥会触发 PyCryptodome 处理 RSA 解密的最坏情况。

在解密期间，实现试图通过重复添加第二个素数来使负数为正：

m1 = pow(cp, self._d % (self._p - 1), self._p)
m2 = pow(cp, self._d % (self._q - 1), self._q)
h = m2 - m1
while h < 0:
    h += self._q

上面代码中，_p和_q属性是两个素数，_d是私钥指数

因为您给定的私钥使用了两个如此不成比例的素数（1 位与 616 位）的素数，所以值为m23 ，而m1616 位短。因此，尝试将q (5) 添加到 616 位长的负整数将需要很长时间。在我老化的 Macbook Pro 笔记本电脑上，PyCryptodome 使用的 GMP 包装器可以在大约 6 秒内将一个小整数添加到该大整数 100 万次：

timeit("a + b", "from Crypto.Math._IntegerGMP import IntegerGMP as H; a = H(-529888206800322351142280698970509553244088870105926093960960600839997948364537263924658051221855219286822834908160253952313431263065035892252247530580840707934254014192645042780064071400938165792458671917549294961637063901428635522475550885330295366860440266592481901428697979715456902249133738633092402578072834537512045684962133176512203248846326955899359525113708331947304401283815041620003402445741404924361709787545141518988924507726836779489762118740731196007268258996956015186886831392340919980371282865371496239488099989353283964607756716132847721450221986689589881754517900556993453537792486255692015472770); b = H(5)")
5.970772444999966

要完成该while循环，必须再迭代 10 ^ 609 次，而我的笔记本电脑将花费的总时间将需要 603 位数字来表示所需的数百万年。我不指望宇宙能持续那么久，更不用说我的笔记本电脑了。

它应该只使用模数运算；您可以在while h < 0: h += self._q此处用模运算替换循环：

if h < 0:
    h %= self._q

这是版本 3.9.3Crypto/PublicKey/RSA.py中的def _decrypt(self, cyphertext):第 162 行。有了这个变化，解密几乎又是即时的。

我已将此作为 PyCryptodome 项目（现已关闭为已修复）的错误提交，并且该项目发布了3.9.4 版，其中循环被模数运算取代。

如果您不想更改已安装的 PyCryptodome 副本并且被阻止，您可以切换到使用cryptography项目，因为它没有这个问题。PyCryptodome 自己实现 RSA 算法，同时cryptography将解密委托给openssl库。

python - 使用故意弱私钥解密消息无限期挂起

1 回答 1

Related

Reference