现在假定存在一个将使用以下命令解密给定密文$ C $的预言家：私钥$ d $并检查解密密码的奇偶校验。也就是说，如果解密的密码分别为偶数或奇数，它将返回true或false。
如果攻击者截取了加密的明文$ C = P ^ e \ mod N $，则可以将其乘以$ 2 ^ e \ mod N $（实际上是将原始明文加倍）并将其发送到oracle。 oracle将解密并找到$ 2P \ mod N $。现在，如果$ 2P> N $，则余数将为奇数，因为$ N $为奇数。如果$ 2P
这就是我受困的部分，因为显然，您可以通过某种方式迭代地应用此原理，并通过迭代地缩小$ P $的范围，可以在$ \ log_ {2} N $迭代中完全恢复$ P $。我无法看到迭代的工作方式。
如果可能的话，我宁愿使用提示而不是完全写出的解决方案，因为我会自己做些事情。我只需要向正确的方向轻轻一点。非常感谢。
#1 楼
这是迭代的下一步，应该很容易理解：让我们在2P和4P上调用oracle：
答案（偶数，偶数）表示$ P
（奇数，奇数）表示$ 3 / 4N \ le P
如果继续将P的因子乘以2，您将获得下一轮迭代，其中“奇数”表示间隔的上半部分，而“偶数”表示间隔的下半部分。
评论
$ \ begingroup $
我们知道P
$ \ endgroup $
– David天宇黄
16年4月16日在15:57
$ \ begingroup $
啊，找出原因:)以奇数次进行第二次迭代，您没有使用4P，而是使用2（2P-N），因为我们已经有了2P> N
$ \ endgroup $
– David天宇黄
16年4月16日在16:45
#2 楼
解决问题的方法确实如@tylo所建议。最初我们知道目标纯文本$ P $在范围$ [0，N] $内，其中下限$ LB = 0 $和上限$ UB = N $。现在我们重复以下算法$ log_ {2} N $次从原始截获的密文$ C $
$ C'=（2 ^ {e} \ mod N）* C $
if (Oracle(C') == even)
UB = (UB + LB)/2;
else
LB = (UB + LB)/2;
评论
你读过例如Fischlin和Schnorr的“用于RSA和Rabin比特的更强大的安全证明”？只是一个小小的注：N不是素数（第4段），很奇怪。应该是“ ..余数将是奇数，因为N是奇数，所以2P是偶数，而2P <2N”。
@tylo你是完全正确的，改变了错误。就像您在回答中建议的那样，昨天我能够解决它。为了完整性，我还将添加最终的方法，但是您对此表示赞同。