RSA dp和dq泄露

从一个[羊城杯 2020]Power密码题，引发的关于dp 和 dq泄露等有趣的问题。

题目本身就出的有漏洞，并且对dp泄露的危害有了更深的理解。

其中的数学基础主要基于费马定理和简单的数论推导,成立以m小于p为前提

1、[羊城杯 2020]Power

题目如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from Crypto.Util.number import *
import gmpy2
from secret import flag

p = getPrime(512)
q = getPrime(512)
n = p**4*q

e = 65537
phi = gmpy2.lcm(p - 1, q - 1)
d = gmpy2.invert(e, phi)
dp = d % (p - 1)
m = bytes_to_long(flag)
c = pow(m, e, n)
print ("dp = " + str(dp))
print ("c = " + str(c))

y = 449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839

g = 2
x = 2019*p**2 + 2020*p**3 + 2021*p**4
c1 = pow(g, x, y)
print( "c1 = " + str(c1))

# dp = 379476973158146550831004952747643994439940435656483772269013081580532539640189020020958796514224150837680366977747272291881285391919167077726836326564473

# c = 57248258945927387673579467348106118747034381190703777861409527336272914559699490353325906672956273559867941402281438670652710909532261303394045079629146156340801932254839021574139943933451924062888426726353230757284582863993227592703323133265180414382062132580526658205716218046366247653881764658891315592607194355733209493239611216193118424602510964102026998674323685134796018596817393268106583737153516632969041693280725297929277751136040546830230533898514659714717213371619853137272515967067008805521051613107141555788516894223654851277785393355178114230929014037436770678131148140398384394716456450269539065009396311996040422853740049508500540281488171285233445744799680022307180452210793913614131646875949698079917313572873073033804639877699884489290120302696697425

# c1 = 78100131461872285613426244322737502147219485108799130975202429638042859488136933783498210914335741940761656137516033926418975363734194661031678516857040723532055448695928820624094400481464950181126638456234669814982411270985650209245687765595483738876975572521276963149542659187680075917322308512163904423297381635532771690434016589132876171283596320435623376283425228536157726781524870348614983116408815088257609788517986810622505961538812889953185684256469540369809863103948326444090715161351198229163190130903661874631020304481842715086104243998808382859633753938512915886223513449238733721777977175430329717970940440862059204518224126792822912141479260791232312544748301412636222498841676742208390622353022668320809201312724936862167350709823581870722831329406359010293121019764160016316259432749291142448874259446854582307626758650151607770478334719317941727680935243820313144829826081955539778570565232935463201135110049861204432285060029237229518297291679114165265808862862827211193711159152992427133176177796045981572758903474465179346029811563765283254777813433339892058322013228964103304946743888213068397672540863260883314665492088793554775674610994639537263588276076992907735153702002001005383321442974097626786699895993544581572457476437853778794888945238622869401634353220344790419326516836146140706852577748364903349138246106379954647002557091131475669295997196484548199507335421499556985949139162639560622973283109342746186994609598854386966520638338999059

我们已知c，c1，dp，e 没有n，可能我们注意力比较容易被c1的约束所吸引。

c1是由2^x mod y 生成的，其中x和p相关，y是一个非常大的数，如果没有模运算，一个简单log就能求出n， 在模运算下，这就上升为离散对数问题。

我们可以通过sympy库的discrete_log 函数来求解，可p是一个512bit的数，X是非常大的，在5min左右python跑出，或许sagemath 会更快一点，这也要求之后要掌握一些有关离散对数的求解算法。

1
print(sympy.discrete_log(y,c1,2))

参考用法: https://www.pythonf.cn/read/109392

离散对数算法: http://www.zbc53.top/archives/124/

假设 我们求出了X 之后X就是p的一个多次方程，可以用z3进行求解。

求出p之后呢，我们还是没有n 并且没有q的相关信息，这时就要用到dp这一个条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
dp= d mod p-1
#两遍同乘e
e*dp = e*d mod p -1 
#等价
e*dp = e*d + k*(p-1)    (1)

"""
根据我们钟爱的e*d = 1 mod phi n

n= (p^4) *q
phi(n) = (p^3)*(p-1)*q

有了这些前提,不妨让式(1) mod phin
"""
e*d + k*(p-1) mod phin = e*dp 
#等价
1 + k*(p-1) = e*dp +  k*phin    phin=(p^3)*(p-1)*q  也是k'*(p-1)
#整理 也就是
e*dp = 1 + k1*(p-1)     (2)    #感觉出其中的倍数关系即可
#此处标位式(2) 我们之后会重点用到

"""
既然
m ^ e = c mod n
c^d mod n = m
用到了欧拉定理
a^(phin) mod n = 1 

那么我们可以类似
c ^ (dp) = m ^ (e*dp) = m ^ (1 + k1*(p-1))
根据费马定理 a ^ (p-1) mod p = 1
那么 c ^ dp  mod p = m
"""
c ^ dp  mod p = m

根据上述推导，拿到p，游戏就结束了。

  • 上述 c ^ dp mod p = m 必须要满足 m < p 或者近似接近 否则近乎不能求解

    即 m = (c^dp mod p) + k*p

回顾一下解题思路，我们执着于解离散对数和高次方程不就是为了求p么，但总结一下上面无论是dp还是 c1 都是有关p的，两个方程求一个未知量，是不是有点奢侈了呢?

注意推导中的这个式子edp = 1 + k1(p-1)！！！ e和dp已知，k未知但是 edp - 1 一定是 (p-1)的整数倍，并且edp-1为525个bit 是十分接近的，这完全可以爆破。

脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import  gmpy2
import cmath
import sympy
from  Crypto.Util.number import *
e = 65537
dp=379476973158146550831004952747643994439940435656483772269013081580532539640189020020958796514224150837680366977747272291881285391919167077726836326564473
c=57248258945927387673579467348106118747034381190703777861409527336272914559699490353325906672956273559867941402281438670652710909532261303394045079629146156340801932254839021574139943933451924062888426726353230757284582863993227592703323133265180414382062132580526658205716218046366247653881764658891315592607194355733209493239611216193118424602510964102026998674323685134796018596817393268106583737153516632969041693280725297929277751136040546830230533898514659714717213371619853137272515967067008805521051613107141555788516894223654851277785393355178114230929014037436770678131148140398384394716456450269539065009396311996040422853740049508500540281488171285233445744799680022307180452210793913614131646875949698079917313572873073033804639877699884489290120302696697425
ep=e*dp-1

for k in range(2,1000000):
    if ep % k ==0:
        p = (ep//k) +1
        if isPrime(p):
            print(k)

p=12131601165788024635030034921084070470053842112984866821070395281728468805072716002494427632757418621194662541766157553264889658892783635499016425528807741
print(long_to_bytes(pow(c,dp,p)))

这样也能达到解出p的目的，并且直接用 pow(c,dp,p),求解，用到了两个二级推导结论。

这也能透露出当m<p时e*dp泄露的危害，如果能通过dp爆破出p，或者直接拿到p ，则直接用dp 和 p，作为私钥和公钥解密即可。

dp，dq本身就是为了快速解密服务的，也就决定了，大多情况下的p和q是非常大的，往往m会比p要小很多，如果出题人在dp泄露时忽视了这一点，那么可能会出现非预期。

1
2
3
4
5
6
#在m>>p 的dp泄露就需要给出e和n，以便我们借助p来分解n
#以网上的一个题目为例
('dp=', '0x7f1344a0b8d2858492aaf88d692b32c23ef0d2745595bc5fe68de384b61c03e8fd054232f2986f8b279a0105b7bee85f74378c7f5f35c3fd505e214c0738e1d9')
('n=', '0x5eee1b4b4f17912274b7427d8dc0c274dc96baa72e43da36ff39d452ff6f2ef0dc6bf7eb9bdab899a6bb718c070687feff517fcf5377435c56c248ad88caddad6a9cefa0ca9182daffcc6e48451d481f37e6520be384bedb221465ec7c95e2434bf76568ef81e988039829a2db43572e2fe57e5be0dc5d94d45361e96e14bd65L')
('e=', '0x10001')
('c=', '0x510fd8c3f6e21dfc0764a352a2c7ff1e604e1681a3867480a070a480f722e2f4a63ca3d7a92b862955ab4be76cde43b51576a128fba49348af7a6e34b335cfdbda8e882925b20503762edf530d6cd765bfa951886e192b1e9aeed61c0ce50d55d11e343c78bb617d8a0adb7b4cf3b913ee85437191f1136e35b94078e68bee8dL')

1、p<m Quic Crack

p的位数可以直接观察dp得出，接近512bit，64字节，一般flag在30-50左右甚至更短，即m<p

1
2
3
4
5
6
7
8
9
10
11
12
13
import  gmpy2
from Crypto.Util.number import *
dp=0x7f1344a0b8d2858492aaf88d692b32c23ef0d2745595bc5fe68de384b61c03e8fd054232f2986f8b279a0105b7bee85f74378c7f5f35c3fd505e214c0738e1d9

n=0x5eee1b4b4f17912274b7427d8dc0c274dc96baa72e43da36ff39d452ff6f2ef0dc6bf7eb9bdab899a6bb718c070687feff517fcf5377435c56c248ad88caddad6a9cefa0ca9182daffcc6e48451d481f37e6520be384bedb221465ec7c95e2434bf76568ef81e988039829a2db43572e2fe57e5be0dc5d94d45361e96e14bd65
e=0x10001
c=0x510fd8c3f6e21dfc0764a352a2c7ff1e604e1681a3867480a070a480f722e2f4a63ca3d7a92b862955ab4be76cde43b51576a128fba49348af7a6e34b335cfdbda8e882925b20503762edf530d6cd765bfa951886e192b1e9aeed61c0ce50d55d11e343c78bb617d8a0adb7b4cf3b913ee85437191f1136e35b94078e68bee8d
edp=e*dp - 1
for k in range(2,10000000):
    if edp%k==0:
        p= edp//k + 1
        if isPrime(p):
            print(long_to_bytes(pow(c,dp,p)))

当然这只是一种特殊情况，但是网上大多数关于dp泄露题目貌似都存在这个问题。

2、通用解法

通解，当然rsa加密对密文本身就限制了m是要比n小的

所以分解n直接解就得了，既然上脚本我们已经测试出了p ，那么q = n//p 即可。

综上，综合两种脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import  gmpy2
from Crypto.Util.number import *
dp=0x7f1344a0b8d2858492aaf88d692b32c23ef0d2745595bc5fe68de384b61c03e8fd054232f2986f8b279a0105b7bee85f74378c7f5f35c3fd505e214c0738e1d9

n=0x5eee1b4b4f17912274b7427d8dc0c274dc96baa72e43da36ff39d452ff6f2ef0dc6bf7eb9bdab899a6bb718c070687feff517fcf5377435c56c248ad88caddad6a9cefa0ca9182daffcc6e48451d481f37e6520be384bedb221465ec7c95e2434bf76568ef81e988039829a2db43572e2fe57e5be0dc5d94d45361e96e14bd65
e=0x10001
c=0x510fd8c3f6e21dfc0764a352a2c7ff1e604e1681a3867480a070a480f722e2f4a63ca3d7a92b862955ab4be76cde43b51576a128fba49348af7a6e34b335cfdbda8e882925b20503762edf530d6cd765bfa951886e192b1e9aeed61c0ce50d55d11e343c78bb617d8a0adb7b4cf3b913ee85437191f1136e35b94078e68bee8d
edp=e*dp - 1
for k in range(2,10000000):
    if edp%k==0:
        p= edp//k + 1
        if isPrime(p):
            try:
                print(long_to_bytes(pow(c,dp,p)).decode('utf-8')) #flag肯定是可见字符
                print('Quick Crack Suc!')
                break
            except:
                q=n//p
                phi=(p-1)*(q-1)
                d=gmpy2.invert(e,phi)
                try:
                    print(long_to_bytes(pow(c,d,n)).decode('utf-8'))
                    print('yes!')
                    break
                except:
                    pass

测试，用如下式例来测试 m > p的情况

1
2
3
4
5
dp = 14423533367739841601650555272663543354837347609362352488761411482549189398193
p =  69901287164206610888661720099426949703910023683707793762919220907478091073681
c=  2262919207276468849681578487794992281448594044416435512543882157738828978766101685798623343531305619235784170849036103143665025760464116190980363198608567
e=65537
n=5965322435025945026021165385608956120433036321627501574655956870755806607342365635361310529607383516087208412532082338428923031616470920911896483167491881

2、dp dq泄露

dp 和 dq泄露 和dp泄露有着异曲同工之妙，不过忽略了m < p / q 就成了纸老虎。

1
2
3
4
5
c: 95272795986475189505518980251137003509292621140166383887854853863720692420204142448424074834657149326853553097626486371206617513769930277580823116437975487148956107509247564965652417450550680181691869432067892028368985007229633943149091684419834136214793476910417359537696632874045272326665036717324623992885
p: 11387480584909854985125335848240384226653929942757756384489381242206157197986555243995335158328781970310603060671486688856263776452654268043936036556215243
q: 12972222875218086547425818961477257915105515705982283726851833508079600460542479267972050216838604649742870515200462359007315431848784163790312424462439629
dp: 8191957726161111880866028229950166742224147653136894248088678244548815086744810656765529876284622829884409590596114090872889522887052772791407131880103961
dq: 3570695757580148093370242608506191464756425954703930236924583065811730548932270595568088372441809535917032142349986828862994856575730078580414026791444659

按之前的算法 是要用中国剩余定理求d的

1
2
dp = d mod p-1
dq = d mod q-1

1、解密思路 + Crt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
m1 = c^dp mod p
m2 = c^dq mod q
dp = d mod p-1   -> dp = d + k*(p-1)
dq = q mod q-1
#根据 费马可得 c^dp mod p = c^d mod p
#同理 c^dq mod q = c^d mod q 
c^d mod p = m1
c^d mod q = m2

构造 x = k1*m1 + k2*m2

(1)k1 mod p =1
(2)k1 mod q =0

k1 = k*q 带入(1)
k = q^(-1) mod p 
即 k1 = (q ^(-1) mod p) *q

"""
推广到一般 如果 在剩余定理中
x mod a1 = b1 
x mod a2 = b2
x mod a3 = b3
...

那么构造的数 m = k1*b1 + k2*b2 + ... kn * bn
k1 = ((a2 *a3 *..an)^(-1) mod a1) * (a2 *a3 *..an)
k2 = ((a1 *a3 *..an)^(-1) mod a1) * (a2 *a3 *..an)
... 如此规律
M=a1*a2*..an
Mi = M / ai
Mi' = gmpy2.invert(Mi,ai)
Mi * Mi' * bi 每一项
综合要%M  一下
"""

即

1
2
3
4
5
6
7
8
9
10
11
12
13
import  gmpy2
from Crypto.Util.number import *

dp= 90494486973243104756298311175705002887155440121025946664275790548694955799661434870163629541771658812502682012435200659355928618529521731475360236486362525996535354732687624609637012830178545914960485330748345108757203508531117591067570383564779625954776907685968592668868046507450242047759226407026094726359
dq= 92386717102324384872139253931247976320472847834037799716676564640678692924258053130751618730959510913784801723023536527134208843358920592320351399005428347188639433875570867152865970587272904695272790831679276818402117343413503376057524788386479263579869430615501089905630519162146030369086836183772975252551
p= 121869669684596731118740111360803257498670698122183387353481580136405322481841982461820301261370579505460038281590785837096967719889404913176714663774999789266522508163678949469953184327222227297952119212490499582581953510522212981687122483764873187827531047946130999532741388680549345732675732040579796067001
q= 128363031923139297392077349407719417788135630403499671848196425800900870531452570499668481104884553795224784931947824885511134525485570129640119439950191944938407656926280993408854767711557863016197167505998324659906146937423415404059310560359693643987781862684489401368519777953281060013045590132161625607377
c= 4176193749773450562408160796325873473193702511560805285554329767573726211097194419198463203488792792756598428753745425419950423161673497255820731183746106463781291156892140581651301528184812357534808298071893380519977926677138246941946185699346532140641376461516107672722425971178865758049759985915001009787241295292157744353554548314911531918044654676691927347018033509499136103964942830581407087547565204232556314726045307279963709599952745342811947421707024572981812906869557834491207590418553244020621858083633564878305733114484857827620268881100166090837841224767358579366482347136224695333980041913268394994302
m1 = pow(c,dp,p)
m2 = pow(c,dq,q)
d = gmpy2.invert(q,p)*(q)*m1 + gmpy2.invert(p,q)*(p)*m2

print(long_to_bytes(d%(p*q)))

用python的库sympy来实现crt

1
2
3
4
5
6
7
from sympy.ntheory.modular import * #从sympy数论库中导入函数
crt([p,q],[m1,m2])
# 第一个参数是模数组，第二个参数是余数组
# 返回值是一个元组 第一个数是求解的m值，第二个数是所有模数的乘积

m=crt([p,q],[m1,m2])[0] #得到解即可
print(long_to_bytes(m%n))

sympy库中有很多方便的函数，有大致印象百度即可。

2、测试用例

反例当messaege>q

注意m要小于n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import  gmpy2
from Crypto.Util.number import *
p=getPrime(256)
q=getPrime(256)
n=p*q
phi=(p-1)*(q-1)
e=65537
d=gmpy2.invert(e,phi)
dp=d%(p-1)
dq=d%(q-1)
print('dp = ',dp)
print('p = ',p)
print('dq = ',dq)
print('q= ',q)
m=b'flag{If_the message_is_larger_than_prime_end!!!}'
c=bytes_to_long(m)
c= pow(c,e,n)
print('c= ',c)

如果继续解密,则是乱码

1
2
3
4
5
6
from Crypto.Util.number import *
dp = 14423533367739841601650555272663543354837347609362352488761411482549189398193
p =  69901287164206610888661720099426949703910023683707793762919220907478091073681
c=  2262919207276468849681578487794992281448594044416435512543882157738828978766101685798623343531305619235784170849036103143665025760464116190980363198608567
print(long_to_bytes(pow(c,dp,p)))
# b'Y\x83^\xa4\xf2\xbaC\xbfY\xa0\x9a!\x07^\xb0\x12\xaa-\xa0\x10\xf8;\x9b\xb1\xaaF5\x9f\xb2\x952\xc0'

中国剩余定理,成功解决

1
2
3
4
5
6
7
8
9
10
11
12
13
import  gmpy2
from Crypto.Util.number import *
dp =  14423533367739841601650555272663543354837347609362352488761411482549189398193
p =  69901287164206610888661720099426949703910023683707793762919220907478091073681
dq =  32437946587531699347725552012753985094383131578752766354933176932787801620073
q=  85339235900086908600694050911639754370783480963298143334400691126173744722201
c=  2262919207276468849681578487794992281448594044416435512543882157738828978766101685798623343531305619235784170849036103143665025760464116190980363198608567
m1 = pow(c,dp,p)
m2 = pow(c,dq,q)
d = gmpy2.invert(q,p)*(q)*m1 + gmpy2.invert(p,q)*(p)*m2

print(long_to_bytes(d%(p*q)))
#b'flag{If_the message_is_larger_than_prime_end!!!}'

推导过程中的中间结论也能对解密有巨大贡献，在进行加密时，还要考虑密文和素因数以及模数的大小，防止出现非预期的漏洞。

Crypto
Crypto

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！