Elliptic-Curves
用有偏見的 nonce 打破 ecdsa
我正在嘗試通過有偏見的隨機數打破 ecdsa 的密碼挑戰，但我所做的一切都失敗了。我正在嘗試使用 4 個簽名和 128 位偏差進行攻擊。
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所以我用 Python 來計算每個簽名的 r,s。
r1 = 17542692331604783387686597246594631064536239879663001141441187611440793041468 s1 = 59970666713963818798340484473731305519480757019507324176120722845542171346646 r2 = 21236730927690085558952219469196432587168514437771225773964740084066020096128 s2 = 73653925753660400507501089537185826698799850650431749444646701596258053995278 r3 = 85636519135624263972588997412249836789610754767096517331004268832200967809234 s3 = 95790245102093906567907250528256928057314647122623818713917454381662803603075 r4 = 43728530926482839836700207199751914848936112999432563121020693461006095148094 s4 = 62277798756101719766682324750255877473826835235202326361423336382588626699856我使用這些資訊來計算 t 和 u 對。如文中所述。
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我使用這些值在 Sage 中構造了一個矩陣並稱為 LLL 算法。
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()這是 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]文本解釋說，在減少的基礎上，cu 旁邊有一個值為 -privatekey/2^128，但我找不到這樣的值。我在這裡做錯了嗎？謝謝。
您已經轉換了
cu和的定義ct它應該是：
ct = 1 / 2**128 cu = N / 2**128這應該給出減少基礎的第二行
[ -176774894147135245389118279701715628782 -163606809150319793607559378100759099084 -239481943659790313674470604946028282117 -258670083948493958792478083334372592209 -16627923497236951427941159362308027460458715450333241891371076649367839027717/340282366920938463463374607431768211456 115792089237316195423570985008687907852837564279074904382605163141518161494337/340282366920938463463374607431768211456 ]您可以根據需要查看私鑰。