2021-西湖论剑-unknow_dsa

题目

from Crypto.Util.number import *
from Crypto.PublicKey import DSA
from Crypto.Hash import SHA
from gmpy2 import invert,powmod
import random
from secret import flag,m1,m2,ul,vl,wl

def encrypt():
    key = DSA.generate(int(1024))
    q = key.q
    p = key.p
    g = key.g
    x1 = bytes_to_long(flag[:len(flag)//2])
    x2 = bytes_to_long(flag[len(flag)//2:])
    assert x1<q and x2<q
    t = powmod(g, p*q-(p+q), p*q)
    hm1 = bytes_to_long(SHA.new(m1).digest())
    hm2 = bytes_to_long(SHA.new(m2).digest())
    k = random.randint(1, q-1)
    r1 = powmod(g, k, p) % q
    s1 = (hm1 + x1*r1) * invert(k, q) % q
    s2 = (hm2 + x1*r1) * invert(k, q) % q
    r2 = powmod(g, x1, p) % q
    s3 = (hm1 + x2*r2) * invert(k, q) % q
    print(p*q, (p-1)//q, t, sep=', ')
    print(r1, s1, s2, sep=', ')
    print(r2, s3, sep=', ')

def main():
    for i in range(len(ul)):
        assert ul[i]**2 - wl[i]* vl[i]**2==1
    e = 7
    cl1 = [int(powmod(bytes_to_long(m1), e, x)) for x in ul]
    cl2 = [int(powmod(bytes_to_long(m2), e, y)) for y in vl]
    print(wl, cl1, cl2, sep=', ')
    
    encrypt()


if __name__ == '__main__':
    main()

'''
[3912956711, 4013184893, 3260747771], [2852589223779928796266540600421678790889067284911682578924216186052590393595645322161563386615512475256726384365091711034449682791268994623758937752874750918200961888997082477100811025721898720783666868623498246219677221106227660895519058631965055790709130207760704, 21115849906180139656310664607458425637670520081983248258984166026222898753505008904136688820075720411004158264138659762101873588583686473388951744733936769732617279649797085152057880233721961, 301899179092185964785847705166950181255677272294377823045011205035318463496682788289651177635341894308537787449148199583490117059526971759804426977947952721266880757177055335088777693134693713345640206540670123872210178680306100865355059146219281124303460105424], [148052450029409767056623510365366602228778431569288407577131980435074529632715014971133452626021226944632282479312378667353792117133452069972334169386837227285924011187035671874758901028719505163887789382835770664218045743465222788859258272826217869877607314144, 1643631850318055151946938381389671039738824953272816402371095118047179758846703070931850238668262625444826564833452294807110544441537830199752050040697440948146092723713661125309994275256, 10949587016016795940445976198460149258144635366996455598605244743540728764635947061037779912661207322820180541114179612916018317600403816027703391110922112311910900034442340387304006761589708943814396303183085858356961537279163175384848010568152485779372842]
85198615386075607567070020969981777827671873654631200472078241980737834438897900146248840279191139156416537108399682874370629888207334506237040017838313558911275073904148451540255705818477581182866269413018263079858680221647341680762989080418039972704759003343616652475438155806858735982352930771244880990190318526933267455248913782297991685041187565140859, 106239950213206316301683907545763916336055243955706210944736472425965200103461421781804731678430116333702099777855279469137219165293725500887590280355973107580745212368937514070059991848948031718253804694621821734957604838125210951711527151265000736896607029198, 60132176395922896902518845244051065417143507550519860211077965501783315971109433544482411208238485135554065241864956361676878220342500208011089383751225437417049893725546176799417188875972677293680033005399883113531193705353404892141811493415079755456185858889801456386910892239869732805273879281094613329645326287205736614546311143635580051444446576104548
498841194617327650445431051685964174399227739376, 376599166921876118994132185660203151983500670896, 187705159843973102963593151204361139335048329243
620827881415493136309071302986914844220776856282, 674735360250004315267988424435741132047607535029
'''

solve

1. ul[3], vl[3], wl[3] 满足下式, 且 wl[3] 已知.

for i in range(len(ul)):
    assert ul[i]**2 - wl[i]* vl[i]**2==1

这个就是 Pell 等式, 可以用 在线网站 解决; 也可以用 sage 解决(连分数), 模板如下:

def solve_pell(N , numTry = 1000):
    cf = continued_fraction(sqrt(N))
    for i in range(numTry):
        denom = cf.denominator(i)
        numer = cf.numerator(i)
        if numer ^2 - N * denom ^2 == 1:
            return numer , denom
    return None, None

wl = [3912956711, 4013184893, 3260747771]
for tw in wl:
    print(solve_pell(tw))

解得:

ul = [10537190383977432819948602717449313819513015810464463348450662860435011008001132238851729268032889296600248226221086420035262540732157097949791756421026015741477785995033447663038515248071740991264311479066137102975721041822067496462240009190564238288281272874966280, 121723653124334943327337351369224143389428692536182586690052931548156177466437320964701609590004825981378294358781446032392886186351422728173975231719924841105480990927174913175897972732532233, 1440176324831562539183617425199117363244429114385437232965257039323873256269894716229817484088631407074328498896710966713912857642565350306252498754145253802734893404773499918668829576304890397994277568525506501428687843547083479356423917301477033624346211335450]
vl = [168450500310972930707208583777353845862723614274337696968629340838437927919365973736431467737825931894403582133125917579196621697175572833671789075169621831768398654909584273636143519940165648838850012943578686057625415421266321405275952938776845012046586285747, 1921455776649552079281304558665818887261070948261008212148121820969448652705855804423423681848341600084863078530401518931263150887409200101780191600802601105030806253998955929263882382004, 25220695816897075916217095856631009012504127590059436393692101250418226097323331193222730091563032067314889286051745468263446649323295355350101318199942950223572194027189199046045156046295274639977052585768365501640340023356756783359924935106074017605019787]

2. 由于 e 很小, 且 ul, vl 已知, 可以先 crt, 然后再开根号求取 m1, m2.

cl1 = [2852589223779928796266540600421678790889067284911682578924216186052590393595645322161563386615512475256726384365091711034449682791268994623758937752874750918200961888997082477100811025721898720783666868623498246219677221106227660895519058631965055790709130207760704, 21115849906180139656310664607458425637670520081983248258984166026222898753505008904136688820075720411004158264138659762101873588583686473388951744733936769732617279649797085152057880233721961, 301899179092185964785847705166950181255677272294377823045011205035318463496682788289651177635341894308537787449148199583490117059526971759804426977947952721266880757177055335088777693134693713345640206540670123872210178680306100865355059146219281124303460105424]
cl2 = [148052450029409767056623510365366602228778431569288407577131980435074529632715014971133452626021226944632282479312378667353792117133452069972334169386837227285924011187035671874758901028719505163887789382835770664218045743465222788859258272826217869877607314144, 1643631850318055151946938381389671039738824953272816402371095118047179758846703070931850238668262625444826564833452294807110544441537830199752050040697440948146092723713661125309994275256, 10949587016016795940445976198460149258144635366996455598605244743540728764635947061037779912661207322820180541114179612916018317600403816027703391110922112311910900034442340387304006761589708943814396303183085858356961537279163175384848010568152485779372842]
ul = [10537190383977432819948602717449313819513015810464463348450662860435011008001132238851729268032889296600248226221086420035262540732157097949791756421026015741477785995033447663038515248071740991264311479066137102975721041822067496462240009190564238288281272874966280, 121723653124334943327337351369224143389428692536182586690052931548156177466437320964701609590004825981378294358781446032392886186351422728173975231719924841105480990927174913175897972732532233, 1440176324831562539183617425199117363244429114385437232965257039323873256269894716229817484088631407074328498896710966713912857642565350306252498754145253802734893404773499918668829576304890397994277568525506501428687843547083479356423917301477033624346211335450]
vl = [168450500310972930707208583777353845862723614274337696968629340838437927919365973736431467737825931894403582133125917579196621697175572833671789075169621831768398654909584273636143519940165648838850012943578686057625415421266321405275952938776845012046586285747, 1921455776649552079281304558665818887261070948261008212148121820969448652705855804423423681848341600084863078530401518931263150887409200101780191600802601105030806253998955929263882382004, 25220695816897075916217095856631009012504127590059436393692101250418226097323331193222730091563032067314889286051745468263446649323295355350101318199942950223572194027189199046045156046295274639977052585768365501640340023356756783359924935106074017605019787]
m1e = crt(cl1, ul)
m2e = crt(cl2, vl)

e = 7

m1 = m1e.nth_root(e)
m2 = m2e.nth_root(e)

# 8382905590662478666595114136929713707132131361720892331048437274828529226704174
print(m1)
# 10336852405630488944198347577475266693234960398137850045398990629116544863921454
print(m2)

3. 已知 p*q, (p-1)//q, 而且 DSA 要求 p-1 是 q 的倍数. 由此求出 p, q

pq = 85198615386075607567070020969981777827671873654631200472078241980737834438897900146248840279191139156416537108399682874370629888207334506237040017838313558911275073904148451540255705818477581182866269413018263079858680221647341680762989080418039972704759003343616652475438155806858735982352930771244880990190318526933267455248913782297991685041187565140859
times = 106239950213206316301683907545763916336055243955706210944736472425965200103461421781804731678430116333702099777855279469137219165293725500887590280355973107580745212368937514070059991848948031718253804694621821734957604838125210951711527151265000736896607029198

temp = 1+4*times*pq
q = (int(temp.nth_root(2))-1)//(2*times)
assert pq % q == 0
p = pq//q

print(p,q,sep=', ')
# 95139353880772104939870618145448234251031105153406565833029787299040378395002190438381537974853777890692924407167823818980082672873538133127131356810153012924025270883966172420658777903337576027105954119811495411149092960422055445121097259802686960288258399754185484307350305454788837702363971523085335074839, 895513916279543445314258868563331268261201605181

4. 由于 encrtpt() 中的两次签名共享一个 k, 将两式相减可解密钥 k. 详情看 DSA

    s1 = (hm1 + x1*r1) * invert(k, q) % q
    s2 = (hm2 + x1*r1) * invert(k, q) % q

剩余的脚本如下:

from Crypto.Util.number import *
from Crypto.PublicKey import DSA
from Crypto.Hash import SHA

from gmpy2 import invert,powmod

m1 = long_to_bytes(8382905590662478666595114136929713707132131361720892331048437274828529226704174)
m2 = long_to_bytes(10336852405630488944198347577475266693234960398137850045398990629116544863921454)

s1 = 376599166921876118994132185660203151983500670896
s2 = 187705159843973102963593151204361139335048329243
s3 = 674735360250004315267988424435741132047607535029

r1 = 498841194617327650445431051685964174399227739376
r2 = 620827881415493136309071302986914844220776856282

p = 95139353880772104939870618145448234251031105153406565833029787299040378395002190438381537974853777890692924407167823818980082672873538133127131356810153012924025270883966172420658777903337576027105954119811495411149092960422055445121097259802686960288258399754185484307350305454788837702363971523085335074839
q = 895513916279543445314258868563331268261201605181

hm1 = bytes_to_long(SHA.new(m1).digest())
hm2 = bytes_to_long(SHA.new(m2).digest())

k = (invert(s1-s2, q) * (hm1-hm2) % q + q) % q

x1 = ((s1 * k - hm1) * invert(r1, q) % q + q) % q
x2 = ((s3 * k - hm1) * invert(r2, q) % q + q) % q
# DASCTF{f11bad18f529750fe52c56eed85d001b}
print(long_to_bytes(x1) + long_to_bytes(x2))