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

Question

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

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

以下代码段用于读取私钥、导出 public 密钥、加密消息然后再次解密：

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() 时挂起。

Answer 1

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

为了安全起见，RSA public 密钥加密通常需要使用两个质数 that are close in magnitude:

For security purposes, the integers p and q should be chosen at random, and should be similar in magnitude but differ in length by a few digits to make factoring harder.

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

$ 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)

prime1（p值）是一个'proper'大素数，使用617位，而第二个q素数是个位数，所以p大约大10^616倍。然后使用此密钥会触发 PyCryptodome 处理 RSA 解密的最坏情况。

解密过程中的实现是trying to make a negative number positive by repeatedly adding the second prime number:

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 位），m2 的值是 3，而 m1 是一个 616 位的短字符。因此，尝试将 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

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

我已将此 as a bug with the PyCryptodome project (now closed as fixed) and the project released version 3.9.4 的循环替换为取模运算。

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

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

Decrypting message with purposefully weak private key hangs indefinitely

python

rsa

pycryptodome