dsa

(r1, s1) = (43665657147136977892760835332544097729763754398125679419859037123212964274095, 11372107439153704547599978617809027960018057676066118055075660375442954789009)
(r2, s2) = (29184887007213204285288676779168140587575609668559831035949650649308618592275, 5011738292572181542092375902756977363590922060964162373234404450451520414798)
p = 31961141251107494919420190534228520246958409864267239760354623819192809291490262139213317490432416411403367763443527530375117617196123131270496004125231254335150221348901335274505489844222882171272650010562960614279185073793274638651086760235178963210965828168433516820007716846876686795459738332444629111764967204355463398049697867061034126529189537688874999118692225915790053920062142349951686250122300061810240375783724631961234942175580462986265098353263395579346466921241016500821787793395554444982717141449909744838267161237273856377774256250949274635575801148994817767751541256849860886577256992383324866941911
q = 69375998045163628324086568160767337544901252262545889505892695427466730978301
g = 23095306638137759877487469277470910487928442296144598697677211337473146684728707820084075779044942034329888686699655576145455963231144004571165817481066424910959951439014314776050521403558035997997820617824839889597136772108383034876458141163933312284054415480674388788905935457149956424898637134087874179010376667509489926236214865373552518669840236207944772752416668193786003948717604980584661094548997197117467440864460714843246250800575997370964173558788145639802963655916833143883799542309432910222224223561677245110195809587171802538978009246887077924173034608600837785506594525481696000424121705524449481831586
y = 30195133393879069638917191223585579396119430591488890396938821804398771785068454607425044458865556053274470709839502680269466948174813926392729790863065933078609827279352860810689776644132512095691760326095517755483748554008211568781998662554432781285208646921699265866446498342049913829592480268053599307065979016922204438675164034767731708343084371572648019835171087671868322447023378942812010740490724160077164191297435291229504616686997442254543493394641023587237077429236872101951650325361004443988267286616139798736713430746804524113024341440435623834197278500144543476528466395780355874841379098027115073850819
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import*
import itertools 
IV = 0x7380166f4914b2b9172442d7da8a0600a96f30bc163138aae38dee4db0fb0e4e
default_hm1 = b'HZNUCTFRound#1'
default_hm2 = b'HZNUCTFRound#1'

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []
H1=19905280947443115569469777697852124038269468456842113763109865796452965095134
H2=H1
PR.<k1, x0> = PolynomialRing(Zmod(q))
f = (s2*(k1**2+x0)-H2)*inverse(r2,q)-(s1*k1-H1)*inverse(r1,q)
roots = small_roots(f, (2^64, 2^20), m=1, d=2)
print(roots)
k1,x0=roots[0]
#[(15744441039285451081, 631339)]
k2=k1**2+x0
x = (s1*k1-H1)*inverse(r1,q)%q
print(long_to_bytes(int(x))