Make it Possible

[RSA]Parity Oracle

在CTF密码学中有一种RSA题目,题目通过某种方法提供一个解密机,但是只会返回解密后明文的最后一比特位,既返回解密出明文的奇偶。我们可以用log(N)的复杂度确定m,举例如下:
首先我们有n, e, c,并且有m=c^d\bmod n
我们可以先传入c,服务器算出m,返回m的奇偶性,当然这并没有什么用所以我们考虑下一步。
我们在服务器中传入c* 2^e\bmod n,服务器计算出m’=(c* 2^e)^d\bmod n = 2m\bmod n,我们考虑到如果2m\lt n,那么m’一定是一个偶数;如果2m\geqslant n, 那么m’=2m-n,同时我们注意到n=pqpq都是大质数,所以它们都是奇数,所以n也是奇数,那么m’就一定是个奇数。
我们现在已经可以通过一次查询把m的范围缩小到了n/2,我们是否可以通过二分法确定m的准确的值?以数学归纳法的思想,我们现在已经完成了第一步的证明,现在要完成的是对之后部分的证明。
假设现在已经把m的范围确定到了\frac{xn}{2^i}\leqslant m\lt\frac{(x+1)n}{2^i},那么下面我们查询c* 2^{(i+1)e}\bmod n,服务器会返回给我们m’=2^{(i+1)}m\bmod n=2^{(i+1)}m-kn,那么:
\begin{aligned} &0\leqslant2^{(i+1)}m-kn\lt n\\\\ &\frac{kn}{2^{(i+1)}}\leqslant m\lt \frac{(k+1)n}{2^{(i+1)}} \end{aligned}
并且考虑到初始条件:
\begin{aligned} \frac{xn}{2^i}&\leqslant m\lt\frac{(x+1)n}{2^i}\\\\ \frac{(2x)n}{2^{(i+1)}}&\leqslant m\lt\frac{(2x+2)n}{2^{(i+1)}} \end{aligned}
因为x和k都是整数,要满足原先的条件,k只能取2x(2x+1)
2^{(i+1)}是偶数,n是奇数。所以当m’是奇数的时候,2^{(i+1)}-kn是奇数,k必然是奇数;反之,如果2^{(i+1)}-kn是偶数,k必然是偶数。
如果k是奇数,k只能取(2x+1),m被约束到\frac{(2x+1)n}{2^{(i+1)}}\leqslant m\lt\frac{(2x+2)n}{2^{(i+1)}}
如果k是偶数,k只能取2x,m被约束到\frac{(2x)n}{2^{(i+1)}}\leqslant m\lt\frac{(2x+1)n}{2^{(i+1)}}
这样二分下去直到上下界只差小于1.

#!/usr/bin/python3

def parity_oracle(n, query):
    """input: n: the modulus of the RSA
    query: query is a function which inputs an int i, returns if the m*(2^i)%n is odd
    return: int m
    """
    i = 0
    x = 0
    while n >> i:
        res = query(i+1)
        if res:
            x = 2 * x + 1
        else:
            x = 2 * x
        i += 1
    return (x+1) * n // 2 ** i

if __name__ == "__main__":
    from Crypto.PublicKey import RSA
    from Crypto.Util import number
    key = RSA.generate(2048)
    n = key.n
    m = number.getRandomRange(0, n)
    print(m)
    m2 = parity_oracle(n, lambda x: (pow(2, x, n) * m % n) & 1)
    print(m2)
    print(m2 == m)
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据