P07.共模攻击

共模攻击，也称同模攻击。

同模攻击利用的大前提就是，RSA体系在生成密钥的过程中使用了相同的模数n。

在CTF题目中，就是同一明文，同一n,不同e，进行加密。

m，n相同；e，c不同，且e1 和 e2互质

出题脚本

随机生成flag

import random
import hashlib
import string

#字符串列表
a=string.printable
#随机生成flag
for i in range(10):
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = hashlib.md5(flag.encode()).hexdigest()
    print("flag{" + flag + "}")

题目1

#coding:utf-8
import libnum
import gmpy2
#生成素数
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e1=2333
e2=23333
m="flag{6ed4c74e022cb18c8039e96de93aa9ce}"
m=libnum.s2n(m)
n=p*q
#pow(x, y[, z])
#函数是计算 x 的 y 次方，如果 z 在存在，则再对结果进行取模
c1=pow(m,e1,n)
c2=pow(m,e2,n)
print("n1:",n)
print("e1:",e1)
print("c1:",c1)
print("n2:",n)
print("e2:",e2)
print("c2:",c2)

题目1解密

#coding:utf-8
import gmpy2
import libnum

n=10509135007927020910961570498020654777820601579825669027410027026173076573380693204454238919762243178647774720169342528691085983225219960236799370268896666867164869238677749575679762611540687182614629847614275763451130215062534086871119259415866636857654106010518677919485438729877453549868724935457349692430637646827845074169704597756894678350214029352130966923159025112991395150214022844221949818486992653054085916326074567355928744181958934887632087019273037034539054980148783728604561167417571308543568511557184742388987903995431328908643666134429145944816840592528868078022503367301892068877343146684216682292031
e1=2333
c1=7817747253100075445080016685151086112268236401548478039383697586624131257005712900744875480257235019856465005133060251952853265167801711501859975585492982445693865641552507292652891995513965716569403068769379922648392091598433743576490830481993190692094310002540291082497060442504191087716491306341060343322555758506922102525722142895936303098845293736052077805416603114326241892440936798612985329887620848022507113494020806335634837064221561034485913416272720657761870572787579710754920585427628542146537468299211892356070884683021760416483687996756045071803827949139730328011630778732391114457251096093112357217218
n2=10509135007927020910961570498020654777820601579825669027410027026173076573380693204454238919762243178647774720169342528691085983225219960236799370268896666867164869238677749575679762611540687182614629847614275763451130215062534086871119259415866636857654106010518677919485438729877453549868724935457349692430637646827845074169704597756894678350214029352130966923159025112991395150214022844221949818486992653054085916326074567355928744181958934887632087019273037034539054980148783728604561167417571308543568511557184742388987903995431328908643666134429145944816840592528868078022503367301892068877343146684216682292031
e2=23333
c2=4005739533838233872100900192412804692746056018222370689494999429600683965220671145551011781360384072398973847079099863801781412654844344905559510784496389730242858693821886631397324132791823439680955157172958658051082121321917953586754734740594115385719917993135141183252010390389651513644552790616554115701338569755344442572426665297172781226400939991451728779259308086811204397695171302495091439788703682660000347393283282772216143916787270940246611837483151694679246528820414931162726657909701256510917389048934521382784300651451892299324944208983841733409704979351560563883697858790944929943311340614454947233485


#共模攻击
#共模攻击函数
def rsa_gong_N_def(e1,e2,c1,c2,n):
    e1, e2, c1, c2, n=int(e1),int(e2),int(c1),int(c2),int(n)
    print("e1,e2:",e1,e2)
    print(gmpy2.gcd(e1,e2))
    s = gmpy2.gcdext(e1, e2)
    print(s)
    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
    return int(m)

m = rsa_gong_N_def(e1,e2,c1,c2,n)
print(m)
print(libnum.n2s(int(m)).decode())

题目2（密钥型，跟2018年巅峰极客的类似）

import libnum
from Crypto.PublicKey import RSA
import base64
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e1=2333
e2=23333
n=p*q
m="flag{09edeb8aa1db60814c34da8994590758}"
m=libnum.s2n(m)
n=p*q
c1=pow(m,e1,n)
c2=pow(m,e2,n)
#print "d:",d

rsa_components = (n, e1)
keypair = RSA.construct(rsa_components)
with open('pubkey1.pem', 'wb') as f :
    f.write(keypair.exportKey())

rsa_components = (n, e2)
keypair = RSA.construct(rsa_components)
with open('pubkey2.pem', 'wb') as f :
    f.write(keypair.exportKey())

with open("c1.enc","wb") as f:
    f.write(base64.b64encode(libnum.n2s(c1)))
with open("c2.enc","wb") as f:
    f.write(base64.b64encode(libnum.n2s(c2)))

题目2解密脚本

#coding:utf-8
import gmpy2
import libnum
from Crypto.PublicKey import RSA
import base64

with open("pubkey1.pem","rb") as f:
    key = RSA.import_key(f.read())
    n1=key.n
    e1=key.e

with open("pubkey2.pem","rb") as f:
    key = RSA.import_key(f.read())
    n2=key.n
    e2=key.e

with open("c1.enc","rb") as f:
    c1=f.read()
    c1=base64.b64decode(c1)
    c1=libnum.s2n(c1)
with open("c2.enc","rb") as f:
    c2=f.read()
    c2=base64.b64decode(c2)
    c2=libnum.s2n(c2)

n=n1
# 共模攻击
# 扩展欧几里得算法
s = gmpy2.gcdext(e1, e2)
s1 = s[1]
s2 = -s[2]
#求逆元
c2 = gmpy2.invert(c2, n)
m = (pow(c1,s1,n) * pow(c2 , s2 , n)) % n
print(m)
print(libnum.n2s(int(m)).decode())

共模攻击原理

https://www.dazhuanlan.com/2019/12/18/5df98f54585e8/

两个及以上的公钥(n,e)来加密同一条信息m

c1 = pow(m, e1, n)
c2 = pow(m, e2, n)

e1，e2互质，则有

gcd(e1,e2)=1

根据扩展欧几里德算法对于不完全为 0 的整数 a，b，gcd（a，b）表示 a，b 的最大公约数。那么一定存在整数 x，y 使得 gcd（a，b）=ax+by

e1*s1+e2*s2 = 1

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

根据模运算性质：幂运算是一种关于幂的数学运算。同底数幂相乘，底数不变，指数相加。同底数幂相除，底数不变，指数相减。幂的乘方，底数不变，指数相乘。

(a * b) % p = (a % p * b % p) % p
a ^ b % p = ((a % p) ^ b) % p

简化公式为：

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

=> (c1^s1*c2^s2)%n = ((m^e1%n)^s1%n*(m^e2%n)^s2%n)%n #(a * b) % p = (a % p * b % p) % p

=> (c1^s1*c2^s2)%n = ((m^e1)^s1%n*(m^e2)^s2%n)%n #((a % p) ^ b) % p =a ^ b % p

=> (c1^s1*c2^s2)%n = ((m^e1)^s1*(m^e2)^s2)%n # (a % p * b % p) % p=(a * b) % p

=>(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

上述就是rsa共模攻击的过程

因此，同一m，同一n,不同e，进行加密。在不需要知道d的情况下，可以进行解密。