> For the complete documentation index, see [llms.txt](https://dev2ero.gitbook.io/notes-cs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dev2ero.gitbook.io/notes-cs/cyber-security/xin-xi-an-quan-yuan-li/crypto/gong-yao-mi-ma/rsa/gong-mo-gong-ji.md).

# 共模攻击

假设 有一条信息m，用公钥加密信息(使用了相同的模数n)：

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

可以利用密钥d1，d2来解密：

```
m = c1^d1 mod n
m = c2^d2 mod n
```

此时如果有一个攻击者，得到了密文`c1`、`c2`，因为公钥公开，而模数相同，攻击者姐可以破解密文获得信息。\
此时已知信息：\
`c1`, `c2`, `e1`, `e2`, `n`

```
gcd(e1, e2) = 1
m = c1^d1 mod n
m = c2^d2 mod n
```

求出m。

接下来就到了高数时间。\
`e1`,`e2`互质

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

则有

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

这里涉及到欧几里德扩展算法，可以看我另一篇文章： [欧几里德算法及扩展算法](https://1ablades.github.io/2017/08/10/%e6%ac%a7%e5%87%a0%e9%87%8c%e5%be%b7%e7%ae%97%e6%b3%95%e5%8f%8a%e6%89%a9%e5%b1%95%e7%ae%97%e6%b3%95/)\
因为

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

所以

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

即

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

所以

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

即

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

得证，可求出m。

* 注意：\
  从前面的式子`e1*s1 + e2*s2 = 1`可以知道，`s1`、`s2`中有一个为负数，而负数次幂运算，比如这里求`c2`的`s2`次幂，需要先计算c2的模反元素`c2r`，然后再求`c2r`的`-s2`次幂。