【性价之王】	【线路之王】	【价格之王】	【配置之王】
【免费之王】	【香港首推】	【梯子之王】	【独服之王】

一、题目特点

明文m、模数n相同，公钥指数e、密文c不同，gcd(e1,e2)==1。即题目给出n、e1、e2、c1、c2，m这5个参数，参数有时是直接给出，但有时是给文件，需要自己读出来。

二、共模攻击原理

摘自【https://blog.csdn.net/weixin_30770495/article/details/98899583】

1、场景分析

假设有一家公司COMPANY，在员工通信系统中用RSA加密消息。COMPANY首先生成了两个大质数P,Q，取得PQ乘积N。并且以N为模数，生成多对不同的公钥及其相应的私钥。COMPANY将所有公钥公开。而不同的员工获得自己的私钥，比如，员工A获得了私钥d1.员工B获得了私钥d2.现在，COMPANY将一条相同的消息，同时经过所有公钥加密，发送给所有员工。此时，就可能出现共模攻击。也称同模攻击，英文原名是 Common Modulus Attack 。同模攻击利用的大前提就是，RSA体系在生成密钥的过程中使用了相同的模数n。
假设COMPANY用所有公钥加密了同一条信息M：
c1 = m^e1%n ; c2 = m^e2%n
此时员工A拥有密钥d1他可以通过
m = c1^d1%n
解密得到消息m，同时员工B拥有密钥d2他可以通过：
m = c2^d2%n
解密得到消息m如果，此时有一个攻击者，同时监听了A和B接收到的密文c1,c2，因为模数不变，以及所有公钥都是公开的，那么利用同模攻击，他就可以在不知道d1，d2的情况下解密得到消息m。

2、数学原理分析

当n不变的情况下，知道n,e1,e2,c1,c2 可以在不知道d1,d2的情况下，解出m。
首先假设，e1，e2互质：gcd(e1,e2)=1
则有：e1*s1+e2*s2 = 1；式中，s1、s2皆为整数，但是一正一负。
通过扩展欧几里德算法，我们可以得到该式子的一组解（s1,s2），假设s1为正数,s2为负数.
因为：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不变的情况下，知道n,e1,e2,c1,c2 可以在不知道d1,d2情况下，解出m。这里还有一个小问题，我们知道解出来s2是为负数，而在数论模运算中，要求一个数的负数次幂，与常规方法并不一样，比如此处要求c2的s2次幂，就要先计算c2的模反元素c2r，然后求c2r的-s2次幂。

三、举例分析

# coding:utf-8'''题目的特点是N是一样的当n不变的情况下，知道n,e1,e2,c1,c2 可以在不知道d1,d2的情况下，解出me1，e2互质'''import libnumimport gmpy2#欧几里得扩展算法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, ydef main(): """ with open('flag.enc1', 'r') as f1: c1 = f1.read().encode('hex') c1 = string.atoi(c1, base=16) with open('flag.enc2', 'r') as f2: c2 = f2.read().encode('hex') c2 = string.atoi(c2, base=16) n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263seo68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L """ n = 116547141139745534253172934123407786743246513874292261984447028928003798881819567221547298751255790928878194794155722543477883428672342894945552668904410126460402501558930911637857436926624838677630868157884406020858164140754510239986466552869866296144106255873879659676368694043769795604582888907403261286211 c1 = 78552378607874335972488545767374401332953345586323262531477516680347117293352843468592985447836452620945707838830990843415342047337735534418287912723395148814463617627398248738969202758950481027762126608368555442533803610260859075919831387641824493902538796161102236794716963153162784732179636344267189394853 c2 = 98790462909782651815146615208104450165337326951856608832305081731255876886710141821823912122797166057063387122774480296375186739026132806230834774921466445172852604926204802577270611302881214045975455878277660638731607530487289267225666045742782663867519468766276566912954519691795540730313772338991769270201 e1 = 1804229351 e2 = 17249876309 s = egcd(e1, e2) s1 = s[1] s2 = s[2] # 求模反元素 if s1 < 0: s1 = -s1 c1 = gmpy2.invert(c1, n) elif s2 < 0: s2 = -s2 c2 = gmpy2.invert(c2, n) m = pow(c1, s1, n) * pow(c2, s2, n) % n #print(libnum.n2s(m))#二进制转string print '{:x}'.format(int(m)).decode('hex')#跟上面这句打印出来同样的效果if __name__ == '__main__': main()#打印的结果是：flag_Strength_Lies_In_Differences# coding:utf-8'''题目的特点是N是一样的当n不变的情况下，知道n,e1,e2,c1,c2 可以在不知道d1,d2的情况下，解出me1，e2互质'''import libnumimport gmpy2#欧几里得扩展算法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, ydef main(): """ with open('flag.enc1', 'r') as f1: c1 = f1.read().encode('hex') c1 = string.atoi(c1, base=16) with open('flag.enc2', 'r') as f2: c2 = f2.read().encode('hex') c2 = string.atoi(c2, base=16) n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263seo68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L """ n = 116547141139745534253172934123407786743246513874292261984447028928003798881819567221547298751255790928878194794155722543477883428672342894945552668904410126460402501558930911637857436926624838677630868157884406020858164140754510239986466552869866296144106255873879659676368694043769795604582888907403261286211 c1 = 78552378607874335972488545767374401332953345586323262531477516680347117293352843468592985447836452620945707838830990843415342047337735534418287912723395148814463617627398248738969202758950481027762126608368555442533803610260859075919831387641824493902538796161102236794716963153162784732179636344267189394853 c2 = 98790462909782651815146615208104450165337326951856608832305081731255876886710141821823912122797166057063387122774480296375186739026132806230834774921466445172852604926204802577270611302881214045975455878277660638731607530487289267225666045742782663867519468766276566912954519691795540730313772338991769270201 e1 = 1804229351 e2 = 17249876309 s = egcd(e1, e2) s1 = s[1] s2 = s[2] # 求模反元素 if s1 < 0: s1 = -s1 c1 = gmpy2.invert(c1, n) elif s2 < 0: s2 = -s2 c2 = gmpy2.invert(c2, n) m = pow(c1, s1, n) * pow(c2, s2, n) % n #print(libnum.n2s(m))#二进制转string print '{:x}'.format(int(m)).decode('hex')#跟上面这句打印出来同样的效果if __name__ == '__main__': main()#打印的结果是：flag_Strength_Lies_In_Differences# coding:utf-8'''题目的特点是N是一样的当n不变的情况下，知道n,e1,e2,c1,c2 可以在不知道d1,d2的情况下，解出me1，e2互质'''import libnumimport gmpy2#欧几里得扩展算法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, ydef main(): """ with open('flag.enc1', 'r') as f1: c1 = f1.read().encode('hex') c1 = string.atoi(c1, base=16) with open('flag.enc2', 'r') as f2: c2 = f2.read().encode('hex') c2 = string.atoi(c2, base=16) n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263seo68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L """ n = 116547141139745534253172934123407786743246513874292261984447028928003798881819567221547298751255790928878194794155722543477883428672342894945552668904410126460402501558930911637857436926624838677630868157884406020858164140754510239986466552869866296144106255873879659676368694043769795604582888907403261286211 c1 = 78552378607874335972488545767374401332953345586323262531477516680347117293352843468592985447836452620945707838830990843415342047337735534418287912723395148814463617627398248738969202758950481027762126608368555442533803610260859075919831387641824493902538796161102236794716963153162784732179636344267189394853 c2 = 98790462909782651815146615208104450165337326951856608832305081731255876886710141821823912122797166057063387122774480296375186739026132806230834774921466445172852604926204802577270611302881214045975455878277660638731607530487289267225666045742782663867519468766276566912954519691795540730313772338991769270201 e1 = 1804229351 e2 = 17249876309 s = egcd(e1, e2) s1 = s[1] s2 = s[2] # 求模反元素 if s1 < 0: s1 = -s1 c1 = gmpy2.invert(c1, n) elif s2 < 0: s2 = -s2 c2 = gmpy2.invert(c2, n) m = pow(c1, s1, n) * pow(c2, s2, n) % n #print(libnum.n2s(m))#二进制转string print '{:x}'.format(int(m)).decode('hex')#跟上面这句打印出来同样的效果if __name__ == '__main__': main()#打印的结果是：flag_Strength_Lies_In_Differences