选择密文攻击教科书RSA

Question

我在尝试对RSA神谕进行选择性密文攻击。我有c作为我想解密的密文，e和n。我已经知道我可以选择一个数字r，计算r^e \cdot c，使oracle解密，并返回r\cdot m。

问题是，这个特定的甲骨文会检查m \bmod mo = 0，其中m是我发送的解密密文，mo是我想要得到的原始消息。如果它等于0 (比如rn__)，它不会打印m，所以我不能使用该攻击。

我真不知道该怎么办。

n非常大(1024位)，所以我不能将它分解。也许对提到的攻击有一个小小的调整，但我真的被困住了。如果有人能给我个提示，我会很喜欢的。

Answer 1

在@kelalaka的帮助下，我找到了一个解决方案。

The idea

我的漏洞是基于这样一个事实(我不知道它是否总是正确的)，如果r \cdot mo < n神谕不会打印任何东西，否则它会打印一些数字，不幸的不是r \cdot mo。

因此，\lfloor \frac{n}{mo} \rfloor^e \cdot (mo^e \mod n)不会产生任何答案(\lfloor \frac{n}{mo} \rfloor \cdot mo < n)，而\lfloor \frac{n}{mo} + 1\rfloor^e \cdot (mo^e \mod n)会生成一个答案，即使不正确。

解决方案

首先，我选择一个比原始消息r更小的数字mo。然后，在甲骨文做出响应之前，我一直在发送r\cdot 2^i，每一步都通过1增加i。

当甲骨文做出回应时，这意味着我找到了一个数字s = r\cdot 2^{i-1}，所以

s < mo

2s > mo

让k:=\frac{s}{2}。我迭代以下过程，直到k > 0：

1. 我派s+k去。
2. • 如果甲骨文作出响应，它的意思是s+k > mo,，所以我指定k:=\lfloor k/2 \rfloor
   • 如果甲骨文没有响应，它意味着s+k < mo,，所以我指定s:=s+k

最后，s应该是mo。

我提出的“算法”(不好意思)应该在mo中得到O(\log_2 n)，所以它是可处理的。