RSA LSB Oracle Attack

翻看crypto attacks时发现的一种攻击，稍微研究了下。

原版脚本只支持模2情况下的oracle，这里我们考虑一个模k的oracle。

给定一份密文c，允许我们每次选取密文oracle，返回的值是这个密文用同样的密钥解密后模k的结果—— 我们把明文写成k进制展开的形式： 首先我们直接把c送回去可以拿到。因为返回的结果是模k的，所以下一步应该考虑如何拿，这样在k进制下一步步oracle出来所有位。 想拿到需要保证送进去的解密后从一次项挪到常数项里，基本的思路就是在c上乘个什么让里出现个的项，把上的k给消去。设乘的这个数字为x，那么最理想的情况下，我们希望它满足： 而，所以取x为即可满足要求。 这样拿到的oracle结果在上减去之后即是，后面的各项同理，不再赘述。

一份简要的poc：

c = 
n = 
e = 
counter = 0
plaintext = 0
i = 0
while True:
    inv = inverse(NUM_MOD,n) # pow(NUM_MOD,-1)
    c_ = (c * pow(inv,e*i,n)) % n
    p = Oracle(c_) # the Oracle function implemented in the problem
    print(p)
    a_ = (p - (a*inv) % n) % NUM_MOD
    print(a_)
    if a_ == 0:
        counter += 1
        if counter == 32: # reach the end
            break
    a = a*inv + a_
    plaintext = NUM_MOD**i*a_ + plaintext
print(long_to_bytes(plaintext))