2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

You have transposed the definitions of cu and ct

It should read:

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Lordi
    Jul 20 at 14:22
  • $\begingroup$ If you want to open a chat room and drop some code and numbers in there, I’ll try and look over them. $\endgroup$
    – Daniel S
    Jul 20 at 21:26
  • $\begingroup$ Thanks! stin.to/53aat $\endgroup$
    – Lordi
    Jul 21 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.