RSA破解作业

题目：

Alice decides to use RSA with the public key N = 1889570071. In order to guard against transmission errors, Alice has Bob encrypt his message twice, once using the encryption exponent e1 = 1021763679 and once using the encryption exponent e2 = 519424709. Eve intercepts the two encrypted messages
c1 = 1244183534 and c2 = 732959706. Assuming that Eve also knows N and the two encryption exponents e1 and e2. Please help Eve recover Bob’s plaintext without finding a factorization of N.

由于两次加密，只是公钥的指数e变化，而公钥和私钥的模数N没有变化，此时，就可能出现共模攻击。
共模攻击利用的大前提就是，RSA体系在生成密钥的过程中使用了相同的模数N。
题中的Bob用公钥加密了同一条信息M，就是
c1 = M^e1 % N
c2 = M^e2 % N
此时，Alice可以通过私钥来解密
M = c1^d1 % N
M = c2^d2 % N
得到明文M。
如果攻击者获得了c1，c2，知道密钥中的N，e1，e2，则可以在不知道d1，d2的情况下，解出M。
首先由于e1，e2都是质数，所以两者互质，即
gcd(e1, e2) = 1
此时则有
e1*t1 + e2*t2 = 1
式中，t1、t2皆为整数，但是一正一负。
通过扩展欧几里得算法，我们可以得到该式子的一组解(t1, t2)，假设t1为正数，t2为负数。因为：
c1 = M^e1 % N
c2 = M^e2 % N
所以
(c1^t1 * c2^t2) % N = ((M^e1 % N)^t1 * (M^e2 % N)^t2) % N
根据模运算性质，可以化简为
(c1^t1 * c2^t2) % N = ((M^e1)^t1 * (M^e2)^t2) % N
即
(c1^t1 * c2^t2) % N = (M^(e1^t1 + e2^t2)) % N
又前面提到
e1*t1 + e2*t2 = 1
所以
(c1^t1 * c2^t2) % N = (M^1) % N
(c1^t1 * c2^t2) = M
不过，M是小于N的数值，所以
M = (c1^t1 *c2^t2) % N
就是说，当N不变时，知道n，e1，e2，c1，c2可以在不知道d1，d2情况下，解密得到明文M。
由于t2是负数，而在数论模运算中，要求一个数的负数次幂，与常规方法并不一样。比如此处要求c2的t2次幂，就要先计算c2的模反元素c2r，然后求c2r的-t2次幂。
Python程序解法如下：

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
def main():
    n = int(input("input n:"))
    c1 = int(input("input c1:"))
    c2 = int(input("input c2:"))=
    e1 = int(input("input e1:"))
    e2 = int(input("input e2:"))
    s = egcd(e1, e2)
    s1 = s[1]
    s2 = s[2]
    # 求模反元素
    if s1<0:
        s1 = - s1
        c1 = modinv(c1, n)
    elif s2<0:
        s2 = - s2
        c2 = modinv(c2, n)
    m = (pow(c1, s1, n) * pow(c2, s2, n)) % n #m = (c1**s1)*(c2**s2)%n
    print (m)
if __name__ == '__main__':
    main()

其中，代入数值：
n = 1889570071
c1 = 1244183534
c2 = 732959706
e1 = 1021763679
e2 = 519424709
由此得到最后的明文M为1054592380。