# RSA攻击之共模攻击

#### 引子

``````现在，COMPANY将一条相同的消息，同时经过所有公钥加密，发送给所有员工。
``````

``````c1 = m^e1%n
c2 = m^e2%n
``````

``````m = c1^d1%n
``````

``````m = c2^d2%n
``````

``````gcd(e1,e2)=1
``````

``````e1*s1+e2*s2 = 1
``````

``````c1 = m^e1%n
c2 = m^e2%n
``````

``````(c1^s1*c2^s2)%n = ((m^e1%n)^s1*(m^e2%n)^s2)%n
``````

``````(c1^s1*c2^s2)%n = ((m^e1)^s1*(m^e2)^s2)%n
``````

``````(c1^s1*c2^s2)%n = (m^(e1^s1+e2^s2))%n
``````

``````e1*s1+e2*s2 = 1
``````

``````(c1^s1*c2^s2)%n = (m^(1))%n
(c1^s1*c2^s2)%n = m^%n
``````

``````c1^s1*c2^s2 = m
``````

#### 案例

``````n = 1022117
p = 1013
q = 1009
#936
fn = (p-1)*(q-1)
e = 17
d = 180017
m = int("h1".encode("hex"),16)
c1 = m**e%n
e1 = 5
d1 = 816077
c2 = m**e1%n
print n
print e
print e1
print c1
print c2
``````

``````#coding=utf-8
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(raw_input("input n:"))
c1 = int(raw_input("input c1:"))
c2 = int(raw_input("input c2:"))
e1 = int(raw_input("input e1:"))
e2 = int(raw_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 = (c1**s1)*(c2**s2)%n
print m
if __name__ == '__main__':
main()
```
```