共模攻击，也称同模攻击

首先要搞清含义：即用两个及以上的公钥(n,e)来加密同一条信息m

题目通常会给出两个不同的e和c，一个相同的n，要求解题者求出m

 1 已知密文：
 2 
 3 c1=pow(m,e1,n)
 4 
 5 c2=pow(m,e2,n)
 6 
 7 当满足e1，e2,互质，则为gmpy2.gcd(e1,e2)=1
 8 
 9 根据扩展欧几里德算法，对于不完全为 0 的整数 a，b，gcd（a，b）表示 a，b 的最大公约数。那么一定存在整数 x，y 使得 gcd（a，b）=ax+by
10 所以得到：
11 e1*s1+e2*s2 = 1
12 因为e1和e2为正整数，所以s1、s2皆为整数，但是一正一负，此时假设s1为正数,s2为负数

推导过程：

 1 已知：e1*s1+e2*s2=gcd(e1,e2)
 2 这里需要使用两个幂运算的性质；
 3 幂的立方，底数不变，指数相乘和同底幂数相乘，底数不变，指数相加
 4 c1=pow(m,e1,n),c2=pow(m,c2,n)
 5 
 6 c1=m^e1%n   c2=m^e2%n
 7 
 8 根据扩展欧几里得算法可以得到：e1*s1+e2*s2=1
 9 
10 则(c1^s1*c2^s2)%n=((m^e1%n)^s1*(m^e2%n)^s2)%n
11 
12 ((m^e1%n)^s1*(m^e2%n)^s2)%n
13 
14 ((m^e1%n)^s1%n*(m^e2%n)^s2%n)%n  #(a*b)%p = (a%p*b%p)%p
15 
16 ((m^e1)^s1%n*(m^e2)^s2%n)%n  #((a%p)^b)%p = a^b%p
17 
18 ((m^e1)^s1*(m^e2)^s2)%n     #(a%p*b%p)%p = (a*b)%p
19 
20 (m^(e1*s1)*m^(e2*s2))%n     #幂的立方，底数不变，指数相乘
21 
22 (m^(e1*s1+e2*s2))%n         #同底幂数相乘，底数不变，指数相加
23 
24 e1*s1+e2*s2=gcd(e1,e2)=1
25 
26 m^1%n                       #m<n
27 证明：
28 (c1^s1*c2^s2)%n==m          前提：gcd(e1,e2)=1

这是普通的共模攻击，要用代码实现，使用gmpy2中的gcd()函数和gcdext()函数

以下是一个共模攻击的exp：

 1 import gmpy2
 2 
 3 e1=773
 4 e2=839
 5 
 6 n=6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249
 7 
 8 c1=3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349#c1
 9 c2=5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535#c2
10 
11 _,s1,s2=gmpy2.gcdext(e1,e2)
12 m=(pow(c1,s1,n)*pow(c2,s2,n))%n
13 print(gmpy2.gcd(e1,e2))
14 print(m)

 

原文地址：http://www.cnblogs.com/lgyj/p/16886808.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性