明文为m，密文为c 模n = p*q 欧拉函数值φ(n)，φ(n)=(p-1)(q-1) 公钥参数e和私钥参数d，可由欧拉函数值计算出，e≡d^-1 (mod φ(n))； 加密：m^e ≡ c (mod n) 解密：c^d ≡ m (mod n)
所谓共模，就是明文m相同，模n相同，用两个公钥e1,e2加密得到两个私钥d1,d2和两个密文c1,c2 共模攻击，即当n不变的情况下，知道n,e1,e2,c1,c2 。可以在不知道d1,d2的情况下，解出m。 这里有个条件，即
gcd(e1,e2)=1有整数s1,s2(一正一负）
e1*s1+e2*s2 = 1根据扩展欧几里德算法，我们可以得到该式子的一组解（s1,s2），假设s1为正数,s2为负数。
要了解扩展欧几里得算法，最好先知道欧几里得算法 欧几里得算法：
d = gcd(a,b) d = gcd(b,a mod b) //这里假设a>b gcd(a,b) = gcd(b,a mod b) 上面就是一次辗转相除 一直辗转相除下去，可得： gcd(a,b) = gcd(b,a mod b) = ... = gcd(m,0) 其中m为最大公约数用例：
gcd(21,15) = gcd(15,6) = gcd(6,3) = gcd(3,0) 即可得21与15的最大公约数为3用代码表示：
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)因为
c1 = m^e1%n c2 = m^e2%n 所以
(c1s1*c2s2)%n = ((me1%n)s1*(me2%n)s2)%n 化简得 c1^s1 * c2^s2 = m
在数论模运算中，要求一个数的负数次幂，与常规方法并不一样。
比如此处要求c2的s2次幂，就要先计算c2的模反元素c2r，然后求c2r的-s2次幂 所以我们有以下脚本：
