题目

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
'''

学习资料 & 脚本来源：

• DSA
  • DSA - CTF Wiki
  • DSA相关知识整理 - Jarvis’s Blog
• 佩尔方程
  • 连分数法解佩尔方程特解
  • 连分数法解特解使用的脚本来源
  • 迭代公式可以参考这个
  • 这个讲得好像也不错，我没细看
• 中国剩余定理
  • 中国剩余定理(m不互素情况Python实现)

解题思路

 flag是dsa的私钥，已知k可以求flag。k通过dsa的k共享进行攻击得到，但是需要知道p, q和m1, m2。p, q, g还是很好算的。求m1, m2先要求ul和vl，ul, vl解佩尔方程求得，再通过中国剩余定理解方程组求m1, m2。

ul, vl

 通过assert得知，$u^2-w{v}^2=1$。这是佩尔方程，首先通过连分数法解出各组u, v的特解，再判断u, v大小是否合适（大于对应的cl中的元素），如果不够大就用迭代公式计算下一组解。

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

m1, m2

 $m_1^7\equiv c_1(\mathrm{m}\mathrm{o}\mathrm{d}u)$，用中国剩余定理解方程组。因为u不互素，所以要用不互素的脚本。

m1=b'Hello, this is the first message.'
m2=b'YES!! that is the second message.'

p, q, g

 令：
$$n=pq$$$$k=\frac{p-1}{q}$$$$\because q|p-1\text{（dsa规定的）}$$$$n=(kq+1)q$$ 求得p, q
$$t\equiv g^{pq-(p+q)}(\mathrm{m}\mathrm{o}\mathrm{d}pq)$$ 由欧拉定理，$a^{\varphi (n)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)$
 因为p和q都是质数（dsa规定的），所以$\varphi (n)=(p-1)(q-1)=pq-(p+q)+1$
$$\therefore t\equiv g^{\varphi (n)-1}\equiv g^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$$ 求t的模n逆即可得到g。
 求g在这道题没什么用。但是如果不给r1和r2就可以用g来求了。

q= 895513916279543445314258868563331268261201605181
p= 95139353880772104939870618145448234251031105153406565833029787299040378395002190438381537974853777890692924407167823818980082672873538133127131356810153012924025270883966172420658777903337576027105954119811495411149092960422055445121097259802686960288258399754185484307350305454788837702363971523085335074839
g= 13672490591171261930826729213489159146697563374509073034220721886255982152303447107197774720664438144279163383740258238065494126227608731057119338486910291529176576096612311734285061607284964658737003594964324046804258074712614189778906098614765392123515385260406254416427321997510822217750260108595410657401

k

 通过k共享进行攻击。

from gmpy2 import *
from Crypto.Util.number import *
from Crypto.Hash import SHA

m1=b'Hello, this is the first message.'
m2=b'YES!! that is the second message.'
hm1 = bytes_to_long(SHA.new(m1).digest())
hm2 = bytes_to_long(SHA.new(m2).digest())

q= 895513916279543445314258868563331268261201605181
r1=498841194617327650445431051685964174399227739376
s1=376599166921876118994132185660203151983500670896
s2=187705159843973102963593151204361139335048329243

ds = s2-s1
dm = hm2-hm1
k = mul(dm, invert(ds, q))
k = f_mod(k, q)
assert k<q
print(k)

flag

from gmpy2 import *
from Crypto.Util.number import *
from Crypto.Hash import SHA

q= 895513916279543445314258868563331268261201605181
p= 95139353880772104939870618145448234251031105153406565833029787299040378395002190438381537974853777890692924407167823818980082672873538133127131356810153012924025270883966172420658777903337576027105954119811495411149092960422055445121097259802686960288258399754185484307350305454788837702363971523085335074839
g= 13672490591171261930826729213489159146697563374509073034220721886255982152303447107197774720664438144279163383740258238065494126227608731057119338486910291529176576096612311734285061607284964658737003594964324046804258074712614189778906098614765392123515385260406254416427321997510822217750260108595410657401

k=594482470568940458934888460206220025660410768547
r1 = 498841194617327650445431051685964174399227739376
s1=376599166921876118994132185660203151983500670896
m1=b'Hello, this is the first message.'
hm1 = bytes_to_long(SHA.new(m1).digest())

tmp = mul(k, s1) - hm1
x1 = tmp * invert(r1, q)
x1 = f_mod(x1, q)
flag1=long_to_bytes(x1).decode()

r2=620827881415493136309071302986914844220776856282
s3=674735360250004315267988424435741132047607535029

tmp = mul(k, s3) - hm1
x2 = tmp * invert(r2, q)
x2 = f_mod(x2, q)
flag2=long_to_bytes(x2).decode()
print(flag1+flag2)