共模攻击

原题文件中存在两个文件message.txt和task.py

• message.txt文件

n=122031686138696619599914690767764286094562842112088225311503826014006886039069083192974599712685027825111684852235230039182216245029714786480541087105081895339251403738703369399551593882931896392500832061070414483233029067117410952499655482160104027730462740497347212752269589526267504100262707367020244613503
c1=39449016403735405892343507200740098477581039605979603484774347714381635211925585924812727991400278031892391996192354880233130336052873275920425836986816735715003772614138146640312241166362203750473990403841789871473337067450727600486330723461100602952736232306602481565348834811292749547240619400084712149673
c2=43941404835820273964142098782061043522125350280729366116311943171108689108114444447295511969090107129530187119024651382804933594308335681000311125969011096172605146903018110328309963467134604392943061014968838406604211996322468276744714063735786505249416708394394169324315945145477883438003569372460172268277

• task.py文件

from Crypto.Util.number import bytes_to_long, getPrime

f = open('flag.txt', 'rb')
flag = f.read()
f.close()
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p * q
e1 = 65536
e2 = 270270
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)
f = open('message.txt', 'w')
f.write('n=' + str(n) + '\n')
f.write('c1=' + str(c1) + '\n')
f.write('c2=' + str(c2) + '\n')
f.close()

解题代码

n=122031686138696619599914690767764286094562842112088225311503826014006886039069083192974599712685027825111684852235230039182216245029714786480541087105081895339251403738703369399551593882931896392500832061070414483233029067117410952499655482160104027730462740497347212752269589526267504100262707367020244613503
e1=65536
e2= 270270
c1=39449016403735405892343507200740098477581039605979603484774347714381635211925585924812727991400278031892391996192354880233130336052873275920425836986816735715003772614138146640312241166362203750473990403841789871473337067450727600486330723461100602952736232306602481565348834811292749547240619400084712149673
c2=43941404835820273964142098782061043522125350280729366116311943171108689108114444447295511969090107129530187119024651382804933594308335681000311125969011096172605146903018110328309963467134604392943061014968838406604211996322468276744714063735786505249416708394394169324315945145477883438003569372460172268277

import gmpy2
import libnum

s,s1,s2=gmpy2.gcdext(e1,e2)   #e1*s1+e2*s2=2
print(s,s1,s2)  #此时s=2，最大公约数
m1=(pow(c1,s1,n)*pow(c2,s2,n))%n  #扩展欧几里得算法
m,t=gmpy2.iroot(m1,2)   #[0]是m的值，[1]是t的值true还是false
if t:
    print(libnum.n2s(int(m)))

共模攻击的原理

• 上面解题代码中m1=(pow(c1,s1,n)pow(c2,s2,n))%n与数学中（c1^s1c2^s2）%n这个式子是同一个，下面证明这个式子能够化简出明文。（“%”是取余数）
  • 将c1，c2带入到上面的式子（c1^s1c2^s2）%n里，进行一系列数论中的模运算，有：
    （c1^s1c2^s2）%n=（（m^e1%n）^s1*（m^e2%n）^s2）%n
  • 根据模运算的性质（ab）%p=（a%pb%p）%p得：
    （（m^e1%n）^s1（m^e2%n）^s2）%n=（（（m^e1%n）^s1）%n（（m^e2%n）^s2）%n）%p
  • 根据模运算的性质（（a%p）^b）%p=a^b%p得：
    （（（m^e1%n）^s1）%n（（m^e2%n）^s2）%n）%p=（（（m^e1）^s1%n）（（m^e2）^s2%n））%p
  • 根据模运算的性质（a%pb%p）%p=（ab）%p得：
    （（（m^e1）^s1%n）（（m^e2）^s2%n））%p=（（m^e1）^s1（m^e2）^s2）%p
  • 由幂的乘方，底数不变，指数相乘可得：
    （m^（e1s1）m^（e2*s2））%p
  • 由同底数幂相乘，底数不变，指数相加可得：
    （m^（e1s1+e2s2））%n
  • 因为e1s1+e2s2=1，所以（c1^s1c2^s2）%n=（m^1）%n,因为m小于n,所以（c1^s1c2^s2）%n=m。

共模攻击，正常情况下e1和e2是互素的最大公约数应该是1
而现在的e1和e2分别为65536，270270他们最大公约数是2，可得（e1s1+e2s2）=2，
就有（c1^s1c2^s2）%n=（m^2）%n—>（c1^s1c2^s2）%n=m^2.
然后对m开平方的可以了