RSA LSB Oracle Attack

rsa_lsb_oracle_attack.py

def lsb_oracle_attack(n, e, c, lsb_oracle):
    '''
    RSA LSB Oracle Attack
    :param lsb_oracle: lsb_oracle(x) == pow(x, d, n) % 2
    :return: m or None if not found
    '''
    l, r, k2 = 0, 1, 1
    while n * l // k2 + 1 < n * r // k2:
        m = l + r
        l <<= 1
        r <<= 1
        k2 <<= 1
        if lsb_oracle(c * pow(k2, e, n) % n) == 1:
            l = m
        else:
            r = m
    m = n * l // k2
    if pow(m, e, n) == c:
        return m
    m = n * r // k2
    if pow(m, e, n) == c:
        return m
    return None


if __name__ == '__main__':
    import random


    def ex_gcd(m, n):
        x, y, x1, y1 = 0, 1, 1, 0
        while m % n:
            x, x1 = x1 - m // n * x, x
            y, y1 = y1 - m // n * y, y
            m, n = n, m % n
        return n, x, y


    def inv(x, p):
        g, y, k = ex_gcd(x, p)
        if y < p:
            y += p
        return y


    def gen_lsb_oracle(d, n):
        def f(x):
            return pow(x, d, n) % 2
        return f


    def test_lsboa(p, q):
        e = 65537
        d = inv(e, (p - 1) * (q - 1))
        n = p * q
        # print("p=%d q=%d n=%d e=%d d=%d" % (p, q, n, e, d))
        decodefun = gen_lsb_oracle(d, n)
        for i in range(1000):
            m = random.randint(0, n - 1)
            c = pow(m, e, n)
            m1 = lsb_oracle_attack(n, e, c, decodefun)
            if m != m1:
                print("Wrong (p, q, n, m)")
                print(p)
                print(q)
                print(n)
                print(m)
                exit(0)
        print(p, q, "OK")


    prime = [3, 5, 7, 11, 13, 127, 229, 5591, 26399, 13044247, 16085599, 506823809, 1555336697, 1000000007, 1000000009]
    for i in range(len(prime)):
        for j in range(i):
            test_lsboa(prime[j], prime[i])
            test_lsboa(prime[i], prime[j])