# Breaking ecdsa with biased nonce

I'm trying to do this cryptopals challenge for breaking ecdsa with biased nonce but everything I do fail to work. I'm trying my attack with 4 signatures and 128 bit bias.

N = 115792089237316195423570985008687907852837564279074904382605163141518161494337 #order of secp256k1 curve
pk = 16627923497236951427941159362308027460458715450333241891371076649367839027717 #private key

#four nonces k with 128 LSB as zero
nonce1 = 60153379392585532817763184791753168239082300186671469170262444887926575726592
nonce2 = 55672512262053072456453068312231509137761547980658296475606970355416567906304
nonce3 = 81491482623380280222300749256492816190672498088497870113042981799449279332352
nonce4 = 88020868417631376090079091379271492730528034066109611780777611808986370146304

h = 34485895765404950534695163583661338451834482700897522297910075077309244615356 #hash of message


So I used Python to calculate r,s for each signature.

r1 = 17542692331604783387686597246594631064536239879663001141441187611440793041468
s1 = 59970666713963818798340484473731305519480757019507324176120722845542171346646

r2 = 21236730927690085558952219469196432587168514437771225773964740084066020096128
s2 = 73653925753660400507501089537185826698799850650431749444646701596258053995278

r3 = 85636519135624263972588997412249836789610754767096517331004268832200967809234
s3 = 95790245102093906567907250528256928057314647122623818713917454381662803603075

r4 = 43728530926482839836700207199751914848936112999432563121020693461006095148094
s4 = 62277798756101719766682324750255877473826835235202326361423336382588626699856


I used these information to calculate t and u pairs. as mentioned in the text.

import gmpy2

t1 = (r1*gmpy2.invert(s1*2**128,N) % N
t2 = (r2*gmpy2.invert(s2*2**128,N) % N
t3 = (r3*gmpy2.invert(s3*2**128,N) % N
t4 = (r4*gmpy2.invert(s4*2**128,N) % N

u1 = (-h * gmpy2.invert(s1*2**128,N))% N
u2 = (-h * gmpy2.invert(s2*2**128,N))% N
u3 = (-h * gmpy2.invert(s3*2**128,N))% N
u4 = (-h * gmpy2.invert(s4*2**128,N))% N

cu = 1 / 2**128
ct = N / 2**128


I used these values to construct a matrix in Sage and called the LLL algorithm.

M = matrix(QQ,[[N,0,0,0,0,0],[0,N,0,0,0,0],[0,0,N,0,0,0],[0,0,0,N,0,0],[t1,t2,t3,t4,ct,0],[u1,u2,u3,u4,0,cu]])

M = LLL()


This the final result from the LLL.

[                                                                                                                                       0                                                                                                                                        0                                                                                                                                        0                                                                                                                                        0                   115792089237316195423570985008687907852837564279074904382605163141518161494337/340282366920938463463374607431768211456                                                                                                                                        0]
[                                                                                                -176774894147135245389118279701715628782                                                                                                 -163606809150319793607559378100759099084                                                                                                 -239481943659790313674470604946028282117                                                                                                 -258670083948493958792478083334372592209                   -16627923497236951427941159362308027460458715450333241891371076649367839027717/340282366920938463463374607431768211456                   115792089237316195423570985008687907852837564279074904382605163141518161494337/340282366920938463463374607431768211456]
[                                                                              1374608170557004289482386739806254896008120917716728511334                                                                               2688491935934706104414070063835969152603784112285630977912                                                                              -3093836885233629709393549734615289084690011409752816518283                                                                               2550867772126923432513971792634665110418138759670723782740                     2367783007046836688268601405612723714850354183650303172369651047357562773703/170141183460469231731687303715884105728   75220863878015337171682040526806903607615987826495479313056776792577082893694257433163601640929/42535295865117307932921825928971026432]
[                                                                             -1058108336042114050147939769278506685288320297643692108497                                                                                -38948308491406928933749641965050006268152597354921705781                                                                               2311383020574229753386010575371426020277002894019556252757                                                                               3536352564502644068862087482864441337521859674039009098976                    35176180477298401770041738467692979679606078545358416412463055345789590195531/340282366920938463463374607431768211456  159357989433324621277687352591333303178530743646233964649880809355282084153553944208050428128853/42535295865117307932921825928971026432]
[                                                                              5338220388291694536427993571044314772586923056617776477846                                                                              -2248221072186802937674839191988484819830380192452166583263                                                                                -59931005800967653939221949467469622879862958909013894552                                                                              -2731459522355738196622570395914308741815995016225013512931                       -16297644598658052674014434514656418855125914723685113718723737042044693439/42535295865117307932921825928971026432 -72530094757512005666428331478203998825070583519244965175931907781947889311343584530874741804907/170141183460469231731687303715884105728]
[                                                                              1296712520937872834793351887192776877977047987266214009460                                                                               2955155568254162344954773023173352254529258719328801669877                                                                               3523632690649703684644642736365212761672472679655172737553                                                                              -3037507897306820449323608845156023100917584486734764008842                     7060023519052484465347527408725055172114306115593274678055788140776243718831/170141183460469231731687303715884105728 385421887201160009926136241236588061634427114647678218035671810454884493476857816580744420135231/170141183460469231731687303715884105728]


The text explains that there is a value as -privatekey/2^128 next to cu in the reduced basis, but I couldn't find such value. Is there something I'm doing wrong here? Thanks.

You have transposed the definitions of cu and ct

ct = 1 / 2**128
cu = N / 2**128


which should give the second row of the reduced basis as

[
-176774894147135245389118279701715628782
-163606809150319793607559378100759099084
-239481943659790313674470604946028282117
-258670083948493958792478083334372592209
-16627923497236951427941159362308027460458715450333241891371076649367839027717/340282366920938463463374607431768211456
115792089237316195423570985008687907852837564279074904382605163141518161494337/340282366920938463463374607431768211456 ]


and you can see the private key as required.

• I changed it and I'm still not getting the result. The final basis doesn't look like the one you posted. It's really weird for me. Jul 20 at 14:22
• If you want to open a chat room and drop some code and numbers in there, I’ll try and look over them. Jul 20 at 21:26
• Thanks! stin.to/53aat Jul 21 at 7:21