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.
