39-fvtavat-xrl-erpbirel.py

from hashlib import sha256

from utils import mod_inv


pub = 134447896505843040234439361618807024839230325083252969607675643505192734726139988950261747175302381226678134064105996581647099933409494961356017995968147644639766556951105161330535466100877568207989472554610348593509089608022587531809797876535966412608394739902764514153846985635343032397232407116925513749584101394107456998214861733480772660095819039182385286611803476365519318090864048607766310874724168955127120179734330245449650377839639663453072375669516066043498826485629996998658642767819501285121642475181626722366537395176336716406922335013088023269186009045881068600613567421065913464148898790823202232548968302463481746289956243567585605508180668490324773113656621344255870476327361037073239494124105552433268144906922868484380324219173556807340040785773321845962110189563823706165136020892759747115593956681200638504665595107087767853374139770617000183638934179700105674045566007697230091485781069619879793749554

p = 4015858885927439238583250456569278549016512717101725248866784719386441147963455661160228623096707922190193791849592964437329454552406508732012665497675583746418931900252892916848640453404141203077950893333665116784236121833956943892060619232387796485835213804251998144887271894041955522788436196105854012023504152449302836535257815210640106057337993903262564729224968102252557741910328928161122430004044862330907667738350997001320800701325951905875566300958522097650683485670369234995523251237177760353321559285261279939805001612697656022507111206736894770342515915927077395387435566838050852683600081041502702094182391975118581796522837222982715744268316523827519776755286988707170361718981447360771605006937241934244094598277235421205140764477235280972992397502727213141720502778936665796601326885241282738221257342038477848526110073659277943468995416055356436986880095174580678122738684991789609953401108196801572231233271
q = 67682941006266027949168208810302604661052759914424117531959279184082777202593
g = 133049890488238595365236421672126759518263759063969113352321985163996045946502509573686466650081413570222932376719154790272681965604750010061609991827177304532040339979370380665271580429929479893083279926396223643036122877920222955994678301022565383451977028972702168032005319387597540832668538108210477257846262252253714192756344607194358402422746610137229988880317112645873754608159067355773147304094132933944387267925842126401564590800187495428874799664023908624708788465528672485402055912087865970815012538089009660002639710566833255663848167761119931461132827288909136036311919388048711817855467104058980179218506334637800013298841301765159162206490549490498369449958338824822043376620935238199320879848695983209640928609603827622568161382690950684205614748362775182018757751839776524089921456961029436249791533082402610781365745877638563724964183560697383123547115358454292121560005412816811331680050772524122873258718

def hex_to_int(h):
    return int(h.translate({ord(k): "" for k in ": \n"}), 16)


H = sha256
S1 = (b"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
      35623234345770674178461511775741429919697286385779853734750439026778433274062,
      45539125425907527650281204451874392252555815280529934540724889833951752886498)
S2 = (b"BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB",
      35623234345770674178461511775741429919697286385779853734750439026778433274062,
      19012499976858645754384863291076389351600771465090039299838961759746601923026)

m1, r1, s1 = S1
m2, r2, s2 = S2
assert r1 == r2  # the two signatures were generated with the same nonce

h = lambda x: int.from_bytes(H(x).digest(), byteorder="big")

# s_1 - s_2 = k^{-1} (H(m_1) - H(m_2)) mod q
k = (h(m1) - h(m2)) * mod_inv(s1 - s2, q) % q
r = pow(g, k, p) % q
assert r == r1 == r2

# s = k^{-1} (H(m) + xr) mod q
x = (k * s1 - h(m1)) * mod_inv(r, q) % q
assert pub == pow(g, x, p)

priv = hex(x)[2:]
print(priv)