mod N での LSB - crypto-writeup-public

InCTF | waRSAwの応用で、 LSBLeakAttackなんだけど、mod 2じゃなくてmod Xのとき

平文 $M$ を $X$ 進数で表す

$M = m_0 + m_1X + m_2X^2 + \dots + m_iX^i + \dots$

暗号文 $C$ を復号して得られるオラクルは $m_0$
暗号文 ${(X^{-1})}^{e}C$ を復号してオラクルを得ると、 $X^{-1}(m_0 + m_1X + \dots) \equiv m_0X^{-1} + m_1 \mod X$ なので、得られたオラクルから $m_0X^{-1}$ を引いて $m_1$
同様に暗号文 ${((X^2)^{-1})}^eC$ を復号すると $X^{-2}(m_0 + m_1X + m_2X^2 +\dots) \equiv m_0X^{-2} + m_1X^{-1} + m_2 \mod X$ だから、ここから $m_0X^{-2} + m_1X^{-1}$ を引くと $m_2$

この手法の嬉しい点として、Mが固定なら、途中でN, e, Cが変わっても問題なく動作する。リクエスト回数は $\log_X(M)$ 回

from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
d = inverse(e, (p-1)*(q-1))
m = getRandomNBitInteger(256)
M = 2020

def oracle(x):
    return pow(x, d, n) % M


c = pow(m, e, n)

i = 1
z = oracle(c)
while True:
    inv = inverse(M ** i, n)
    c2 = (c * pow(inv, e, n)) % n
    o = oracle(c2)

    ith_z = (oracle(c2) - (z * inv) % n) % M
    z = ith_z * pow(M, i) + z
    i += 1
    print(z, m)
    if z >= m:
        print(z == m)
        break