RSA共模攻击

1
共模攻击又称为同模攻击
2
利用前提就是，RSA 体系在生成密钥的过程中使用了相同的模数 n。
3
在 CTF 题目中，就是同一明文，同一 n，不同 e，进行加密。
4
m，n 相同；e，c不同，且 e1 和 e2 互质

出题脚本

1
import libnum
2
import gmpy2
3
#生成素数
4
p=libnum.generate_prime(1024)
5
q=libnum.generate_prime(1024)
6
e1=2333
7
e2=23333
8
m="flag{6ed4c74e022cb18c8039e96de93aa9ce}"
9
m=libnum.s2n(m)
10
n=p*q
11
c1=pow(m,e1,n)
12
c2=pow(m,e2,n)
13
print("n1=",n)
14
print("e1=",e1)
15
print("c1=",c1)
16
print("n2=",n)
17
print("e2=",e2)
18
print("c2=",c2)

1
n1= 22817687453594561093170822818588556986000277011160841262403199551502393484061389491076634028395392962009793343228923092886612054684991389737345787326688972149020842914583529891082951179868956251440218819392737891580746359703612669934795746328529684247374338767533615449137922700209178872879393811272704609719211648918140586912108580205636048007578563306043719614052483880870863585575789285811137240550308561197822070383596622339059648874103646152181728062250516561732247367298336213353262461433129881382518579313853002877615869600273701570716055172359763089001737467178031343367158386145278698670428722439275845919781
2
e1= 2333
3
c1= 3068809693807866023250755658664845434485205828465649532485636355597541495998547292203314532428913714359308569689226326859742231253434512875638995289737105648245479262947503107061775198134528761923809971337752228433712694907389266491011323130151153659988164704012204904188050921984759096394916823487514822445094725670595389625922254860442056207665348751725474779763956046176636678179973856349898301877434746301170348718023275617926638966403382396173578715063898456749053806934669362603972508535137105087580584331172845215217788861292350387522104196969389523864142820496499475769368225502201005081764695328115125716051
4
n2= 22817687453594561093170822818588556986000277011160841262403199551502393484061389491076634028395392962009793343228923092886612054684991389737345787326688972149020842914583529891082951179868956251440218819392737891580746359703612669934795746328529684247374338767533615449137922700209178872879393811272704609719211648918140586912108580205636048007578563306043719614052483880870863585575789285811137240550308561197822070383596622339059648874103646152181728062250516561732247367298336213353262461433129881382518579313853002877615869600273701570716055172359763089001737467178031343367158386145278698670428722439275845919781
5
e2= 23333
6
c2= 14321584584635710601699862022940447451458443319804064303028371997206157560474856130068721352840265237932584758125998845200030240230088697475257804076891915461964081330330701969941369024375036108814909954911842762561181905181080581182569456796896705718244477631301075420423567981003074132957174019040041623975800201106522574541756690453732269869578461267131690321760712385293576843426568170997558455004390668769058534236566151168725808220917155776537019046559669930314898872064974853472108134659947349093033210643312110173688854873249213787719807659050762967536386015370877644748346382736830713914593995648231348173041

解题脚本

1
import gmpy2
2
import libnum
3

4
n = 25333966058003377512707481338795714713737652659944601834182685873529702913988641983855700459996104700470621411559153944988952210084014634675583566338568882440708528997808798650962116756969822211586531522430245040013570571043385238601846104615050089457836721437790715225367971106085839523500735480715155424498941150468093083816830215632716244390679417218873179734276657411907216486790815037105108306055794473002315541787461904728375164737225486501009857299717749346279371251245318729951905832578739696926931502225899707226264570557623527701806829827566904224572897378639191756878049342203546309520458672464170859577433
5
e1 = 2333
6
c1 = 11355981897781478907853356911752561659125575027336719997290835661089901154031171698660586203170528368228850895159361637188990782030255983633790580700032092629587631108597144196551438410868034739981960656110887650747325311613900008001234835897835613759692146419080113176963747835592656185435741504176116672174539018089139547795447109458469225330809064539216773123671814859510069089532677704482026169178543062578686794346026774853085101278125763460212801929360456888869350105294595904940799522522144740464043605342348269086324747729288399275079874271519208155039364092577755518532799345651172433227745483422620900776136
7
e2 = 23333
8
c2 = 1326499538902841116411674554069945581390130048432351353260154261863309471312810811160302458644816390944833633923435634961251092531893503039914793217247984595331920909367627316087404934402312358642315675486438968585084964845763881078835787872160374025547400141298650794551970291119975344578667689961134814676553190178139842507675899262024572370313939107080072875068218336255452161407859907308656094331557912187788276334833723893856310434523337557011032081467262457427167978528280339494077785813461280853735266463152709443731638714219391773144349752633555310299318290576258086971373777118482642702020599928071855133041
9

10
# 共模攻击函数
11
def rsa_gm_attack(e1, e2, c1, c2, n):
12
    # e1, e2, c1, c2, n = int(e1), int(e2), int(c1), int(c2), int(n)
13
    s = gmpy2.gcdext(e1, e2)      # 欧几里得公式扩展，满足 e1 * s1 + e2 * s2 = 1
14
    # print(s)
15
    s1 = s[1]
16
    s2 = s[2]
17
    # print(s1)
18
    # print(s2)
19
    if s1 < 0:
20
        s1 = - s1
21
        c1 = gmpy2.invert(c1, n)
22
    elif s2 < 0:
23
        s2 = - s2
24
        c2 = gmpy2.invert(c2, n)
25
    m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
26
    return int(m)
27

28
m = rsa_gm_attack(e1, e2, c1, c2, n)
29
# print(m)
30
print(libnum.n2s(int(m)))

1
b'flag{6ed4c74e022cb18c8039e96de93aa9ce}'

共模攻击原理

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

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

e1，e2互质，则有

1
gcd(e1,e2)=1

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

1
e1*s1+e2*s2 = 1

s1、s2皆为整数，但是一正一负，假设s1为正数,s2为负数

因为

1
c1 = m^e1%n
2
c2 = m^e2%n

可得：

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

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

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

简化公式为：

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

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

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

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

9
=> (c1 ^ s1 * c2 ^ s2) % n = ((m ^ (e1 * s1) * (m ^ (e2 * s2)) % n           # 幂的乘方，底数不变，指数相乘。
10

11
(c1 ^ s1 * c2 ^ s2) % n = (m ^ (e1 * s1 + e2 * s2)) % n                    # 同底数幂相乘，底数不变，指数相加。

因为 e1*s1+e2*s2 = 1 得：

1
(c1 ^ s1 * c2 ^ s2) % n = (m ^ 1) % n
2

3
(c1 ^ s1 * c2 ^ s2）% n = m        # gcd(e1, e2) = 1 的时候

变形

1
假设 gcd(e1, e2) = x       # x != 1
2
即：
3
(c1 ^ s1 * c2 ^ s2) % n = (m ^ x) % n
4
所以真实的 m1：
5
m1 = (m ^ x) % n
6
m1 = (m ^ x) + kn
7
计算的时候需要减去 k 倍的 n

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

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

dacj4n's

RSA共模攻击

出题脚本

解题脚本

共模攻击原理

变形