[Python] I need help the restructuring and reforming of these scripts

I am working on a research project on lattice attacks on ECDSA and got confused with the correct implementation of the ECDSA parameters in the simulation scripts. I need help restructuring the ECDSA parameters and implementation in these simulation scripts, I need them to use standard ECDSA implementations. This one is for generating signatures with biased nonce (python script):



from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key

from random import randbytes, randint



G = generator_256

p = G.order()



def genKeyPair():

d = 0x30f39ca15c295c1114174ca0217d0572eb95ed4811e71364a33dde5d5fad8696

pubkey = Public_key(G, d*G)

privkey = Private_key(pubkey, d)

return pubkey, privkey



def sign(privkey, bias):

m = randbytes(32)

nonce = randbytes(32 - bias)

sig = privkey.sign(int.from_bytes(m, "big"), int.from_bytes(nonce, "big"))

return (m, sig.r, sig.s)



pubkey,privkey = genKeyPair()

print('Public key:', (int(pubkey.point.x()), int(pubkey.point.y())))

print('Private key:', int(privkey.secret_multiplier))



SIGs = []

for _ in range(40):

SIGs += [sign(privkey, 1)]



SIGs


And this is the lattice algorithm to test the biased and weak signatures and simulate private key recovery, (sage environment):



# --- SECP256K1 / ECDSA PARAMETERS ---

q = 115792089210356248762697446949407573530086143415290314195533631308867097853951

A = -3

B = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B

F = GF(q)

E = EllipticCurve(F,[A,B])

Gx = 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296

Gy = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5

G = E(Gx,Gy)

p = 115792089210356248762697446949407573529996955224135760342422259061068512044369

assert G.order() == p



# The public key

P = E(97072186797211310505016479095232580218352290897911577856744836894403414937794, 39021415952191690909385107115390271479179743595779360677080390824579192648103)



# The collected biased signatures

# SIGs contains tuples (z, r, s) with (r,s) being a signature for z under P

SIGs = [

(38000798177211802687813163831537249461003818810823040747312627576979826149588, 87471860015059189703236137773642831184736841890632235084246109711627781257858, 63133927548059291417465730537335149045977952900569631737292314227056024506867),

(111740430575368962806997471824551417413932781476957672024218352232322323458716, 38799912782570650419042855286138858397897432845802489083656263946988797883634, 65673364723478809439788949730589345252668129356850004213499878788192753264114),

(109471736153500797600289399599603612417206514279656293125741029506460920705510, 33018778321245351255834911241912271877131678919197652984430445391180043578451, 68794573169245303192236194229553076673928329522217012731086730343915500609245),

(3428039712156506685063761213590010967589339701947343281990183115408095946955, 33847108210470745889263973706032099560456153945623285028926732879720243668966, 101032229617726041505001861922730042664940055441807580415482120450974622703840),

(112832547424785005330966270932839487272417451823063241613087021511567713102481, 4498640521207618834708983162876232184306498630236063750161182630881292823747, 2597284659263288679792034895017566170501372107525154963933928103422685578177),

(89210777451375939767912559345222365636703422273694561446259233182692266037514, 3148110516178317859826408207631436280518197414805997396430182056821450019243, 24884394397794915311164256392676833516045370503241228243722739666353174721946),

(92125687882265374451160632507660867263055238044979499729031817585027675944443, 18512695575447232516659199824763228069300593728595998375698889476971706245790, 69771644945162472054143663375004954317964526872056891309209917550341516046946),

(44931115767175857636783814038025143624497311367085988181021151662143075005816, 90159912684307733907716373306509402658750067307148014089060911664268537846186, 80040564567142277158965814149119657046619216592802786737140735531588142159672),

(99824216776912615684583461882134017927050863204838136476650411211740545691414, 72510042680529582256071794409225061516248227639347794693378158484387873903713, 1241372813699620220794164192191886010038251343852943790901786012935137465810),

(26423059661953627546082984253783853957228933225919544563703829761482932830581, 95089044171936832261837375372844439399858569540917319869847173773947615344508, 32415694356588882330419002600338362570673837988048942638952420722277714691328),

(39093736984257634117333691346985600862449508296548911171848710710992568508944, 46307435491146669847459441201199094677513959681337089713719334416853616553835, 52539060284018799612174913436030712352265037198469791674090903387218500273451),

(80915222634032587274836046954124200214734564919849973836791801552944566983238, 109024594447261400997359038933339812175707537112619546804450075557315904083064, 84914089719551937629888536187599064939417037544609200154813537621310562984949),

(53574938369514431642660498524071393532110012321262039760871057221495186075723, 87604213795648297940228804402036751109603876203727676817832848047760552274790, 38545126097527733651159628857398619841361810923763112771817587307485325020243),

(60249338573218083663278154193397386464080501263347810801846914736239512446446, 79550483512876045792305954677587194936916035239250031692971359671165338215371, 102046172604923097236560231026785086628521973652336032743911187490012721548258),

(71265571235982972160322582990507374188796339118442878648750897653435326031287, 67881994474120078757143661710314691306433858886087869397891278471827540456214, 6876467855417110631485858739226778678337990278292260069466337493425800008371),

(95387768900360121497781116181308388952040318490379409383806789474520668138305, 84086822957653093068674942257334820963368037016780531728886650523593613435090, 28477903800209663612636174501471988627893095548757564801826789385829075592472),

(109244701190078546692004985312747109123942481339340714492679264662280107122679, 29265795804565082547759266656590914003715070465692315449295466972069180238236, 52233856262914918644394985123656935383427507890485736071911468213723834810053),

(74230718909372612099627771189774184340028243398438147388428424413953951107882, 28344821553970147716913338149572396446456998471027163527577029375500388764874, 48058457846129439807923765066768962880259186415838844704689702233861643769812),

(11752602457181666943118604934263017415848301698468131970865124369693974700999, 36968937935485787206157602934039134021392130855159556344113000060697755038349, 104473118071910859619717683273250537999824926196585042949953690004612749912442),

(36468677799088106651751023597422286804329418705069302666496650396276958240541, 58858042482577549051769169041020204807044247585560660847859385759743573023102, 14329852185127149855977553948802773334036622272261861740042509291367457879273),

(91697633527936257022585624574687380707826622073381893192636711724017860529761, 87568746295157886537444944239455287623980241040288066558074550385068727088673, 100038312283111710415936206168074543863861388759408853379596650813770789855885),

(45470400978445659544801595981398071311843633104183691662819069479095406057440, 82752761153294728120397154293059845321750466453114246418645856475676034879698, 3528585878369093817271859608659342432862455320591962622597622561068536451085),

(75936983570064540341822879473660098625052174591880422384170300594883189933939, 24033853901476658326201452227478184071207886538982940099153182030825558739334, 57405753688485878187272307125953308141839275459980683893522604432900467339031),

(42987806299776412753022876666830593021256490370527363556813512444580569508925, 8803426219066744891197787373593687824643494995888782183178823629236964651257, 58326396635610169513497624825714626105445572291829353461909469888071216226845),

(61508337877071720938109371140643457018124464952131035220435618882381952058700, 87668313737379926069078168193458725941363102601710203855657953645091589369327, 103323208246513467599612224041381444119693631300981264809286358311557357340722),

(3029256104542783873188438456026712621807498920754087022991999471003894851828, 107742708555911103446361387222962891399723113675433059479411923061724697283022, 89931802786982269586198562289426822271025831120441751008514420218190829001407),

(96882777452218725748616639130620044777738585482837721493726566110183013117260, 8616970681936411845344364083480840874965114654681596840257833953383248916628, 38363747168265353080047610400507660363027897446825712396517289138970663878251),

(40110947893115911699652284016100777036251415737511025165756080938767464534347, 10094638054310176879055329807286640918475670183049482611900507879771059568104, 92373083510198880120981639013170540431727842875398500913818381788790256655748),

(49037534520394699297970804639773904601399800247449880170355822496172541338505, 55111844865951262235949074866995519211429839285970160074431713105415134247114, 109614079017417427220621088015418398120850939179761029521196516176452403193644),

(97736634077151479656405875194167913285714586002039548686848977314695456769550, 48864523784711471330059846254437387376604668432923924350798904895400620584219, 103671044850272596878118916238387562627751119997678733983525634235370556020498),

(87060754830158674533073775934551616693679486224328506652915700807148822723301, 39587846874472242304900515582359998182618011855151469732683869372305264939838, 56600936401295025305301361854465869314373190633275218778157981080442864910926),

(50443633067651391779679080908529257597781219591569701771432405936869992873214, 110611233591007858868112459738388942788340636252303529453429726197881783242270, 67534195065295593516996390982129650489591114291372055995525875299033906670455),

(70884773696247224814016649550658639608018458774426980967768640829710026941164, 80368942225792309400570561235331771461642601772497148066467842003402068111412, 94090601120237934578713455392187079226191277415230356954802056195766078272431),

(26150770910625322789760513928892818423863884590148101270860028708678385828681, 84548970054652804877520485334274147677769528552057273478560039941691330520451, 42665458565218029167287016302432661331932488363931123619603206426071177779096),

(72748199291922034632604888421095300971297452923057130966756499190435214503887, 96174480214362268395094167667088718601985531668984503273154965185322074304392, 99387334415452856806698060102090538918820228997400046177111836494406300297248),

(100590584631801697409936663200006715380972457755119364325390912628702022659892, 108203177273289245108674903916160754346571765543126615819970747011289761439672, 7023746332916853700118748570391904047852626343550893781185393012658256943107),

(100998952163858959875912495718437242830651071031414993322283176382784078224197, 11422003813771992476870467991983135007496534633484788701394015259062903507329, 105417742246060431455419061109662264399406698228295085506922631749765694576097),

(14923418863112121037578603792556948840932533022583262921513108407067337608145, 36783928236658736743889097944137743791100935115022666175544647985433881403535, 86951764623506071983483466589228285006111679413515713492307230678921043331138),

(70598287328063356939439960868301502950592710242335155248591521914942322831345, 10137002555781487951407260743359046248459167299714683495092057258517249699167, 108206422361579212773177075583369311836172084183023098737616460329284244732108),

(103682554983023523285773889322296267491748253572140650954042714177670168079057, 3728685596362981911852982183847568071028819285129189294264012192085974331279, 26101372316372242532237449816856040978466341644558159293227268830973869537791)

]



# We know that the first byte is biased, hence all nonces k satisfies k < B = 2^(256-8)

L = 8 # note that this correspond to the amount of leaked or zero bits.

U = 256-L

B = 2**(U)



# We construct the first two rows of the lattice

Mtilde = [B, 0]

Rtilde = [0, B/p]

for sig in SIGs:

z,r,s = sig

Mtilde += [inverse_mod(s,p)*z % p]

Rtilde += [inverse_mod(s,p)*r % p]



# We redefine the arrays as matrixes

Mtilde = matrix(QQ, 1, len(Mtilde), Mtilde)

Rtilde = matrix(QQ, 1, len(Rtilde), Rtilde)



# We contruct the diagonal submatrix with p entries

Pdiag = -p*identity_matrix(QQ, len(SIGs));



# We construct the lower left n x 2 zero block matrix

Z = matrix(QQ, len(SIGs), 2, [0 for i in range(len(SIGs)*2)] )



# We construct the final matrix assembling all blocks

M = block_matrix([[Z, Pdiag]])

M = block_matrix([[Mtilde], [Rtilde], [M]])



# We run the LLL algorithm

L = M.LLL()



# We check if any valid nonce was found

found = 0

for row in L.rows():

if found:

break

for i in range(len(SIGs)):

if found:

break

z,r,s = SIGs

# we skip the first two vector components we used to improve LLL

solk = row[i+2]

# LLL might have swapped the sign of found short vectors

for k in [solk,-solk]:

d = inverse_mod(r,p)*(k*s-z) % p

if d*G == P:

print("Private key found!", d)

found = 1

break










Actually, the script works perfectly well with the present implementation but that's not correct compared to standard ECDSA implementations. I've tried doing it but I keep getting errors. The scripts are supposed to use n = curve.order instead of p just like standard signature signing and other related corrections.

Continue reading...