任意modのLSB Leak Attack考 - crypto-writeup-public

$X = f_1 * f_2 * \dots * f_n$ としておいて、

$X^{-1} = f_1^{-1} * f_2^{-1} * \dots * f_n^{-1}$ か？ → $GCD(f_1, f_2, \dots, f_n) = 1$ ならYes

で、ある $f_i$ について

$Dec \left(C\right) = M \equiv m_0 \mod f_i$

（ただし $M = m_0 + m_1f_i + m_2 f_i^2 + \dots$

続いて、

$Dec\left((X^{-1})^eC\right) = X^{-1}M = (f_1f_2\dots)^{-1}(m_0 + m_1f_i + m_2f_i^2 + \dots)$

$= X^{-1}m_0 + (f_1f_2\dots f_{i-1}f_{i+1}\dots)^{-1}m_1 + (f_1f_2\dots f_{i-1}f_{i+1}\dots)^{-1}f_im_2 + \dots$

$\equiv X^{-1}m_0 + (f_1f_2\dots f_{i-1}f_{i+1}\dots)^{-1}m_1 \mod f_i$

なので、 $X^{-1}m_0$ 引いて $f_1f_2\dots f_{i-1}f_{i+1}\dots$ 掛ければよい

$X^{-1}m_0 は \mod n$ で $f_1f_2\dots f_{i-1}f_{i+1}\dots$ かけるのも $\mod n$

その次は

$((X^2)^{-1})^eC \equiv X^{-2}m_0 + X^{-1}(f_1f_2\dots f_{i-1}f_{i+1}\dots)^{-1}m_1 + (f_1f_2\dots f_{i-1}f_{i+1}\dots)^{-2}m_2 \mod f_i$

なので、 $X^{-2}m_0 + X^{-1}(f_1f_2\dots f_{i-1}f_{i+1}\dots)^{-1}$ 引いて $(f_1f_2\dots f_{i-1}f_{i+1}\dots)^2$ 掛ければ良い。実装的には $m_0 + f_im_1$ を持ってるはずなので $(m_0 + f_im_1)X^{-2}$ 引けばよくなる

……という理論に基づいて書いてみたけどうまく動かない↓

from Crypto.Util.number import *


p = getPrime(256)
q = getPrime(256)
n = p * q
e = 65537
d = inverse(e, n - p - q + 1)

primes = [659, 809, 719, 647, 809, 653, 691, 911, 677]

m = getRandomNBitInteger(128)
c = pow(m, e, n)
M = primes[0]

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

X = 1
for p in primes:
    X *= p

Y = 1
for p in primes[1:]:
    Y *= p

z = oracle(c)
print(z, m % M)
for i in range(1, 10):
    inv = inverse(X ** i, n)
    c2 = (c * pow(inv, e, n)) % n

    o = oracle(c2)
    ith_z = ((o - z*inv) * pow(Y, i, n) % n) % M

    z = ith_z * (M ** i) + z
    mm = m
    for _ in range(i):
        mm = mm // M

    print([z, m % (M ** (i + 1))], [ith_z, mm % M])