Lattice used for finding range of nonce in transactions - academic question

dan.alex

newbie

Activity: 1

Merit: 0

Quote from: ecdsa123 on October 31, 2022, 12:04:56 PM

I'm not taking about calculation privkey from collection signatures. You will not find my solutions on net. i rebuild LLL and way of rearranged for testing one signature as part r s z for finding closest pointt as integer value.

And if someone of you do the same we can discus

The elliptic curves points do not retain the properties of the numbers they represent in such a way that you can perform a modulo operation or check the last digit. The points on the elliptic curve are the solutions of the equation y^2 = x^3 + ax + b (over some finite field), and they don't correspond directly to integers in a way that would allow you to check if their remainder is 0. Lattice is useless unless you know either the corresponding MSB or the LSB for each specific nonce and you cannot use lattices to find them, so why would you create such delusional topic?

COBRAS

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Lattice is a shit dont waste your time !

ecdsa123

full member

Activity: 211

Merit: 105

Dr WHO on disney+

PS. it is the part of my PH.D work.

ecdsa123

full member

Activity: 211

Merit: 105

Dr WHO on disney+

here more testing:

Code:

private 1329227995784915872903807064575311872 nonce 131437503589373493937467858504790506092
r 34082606389192619557532329142625616773941454776938292022250932946992094812911 s 90453886658291840404835025533905187219579933145788813132510264994637252202609 z 63436997692085125645346100214068225441337773102648563094540117299570054938824
signature matches
r 95323123089714168900967931428611332695599803581566448000895682395979520056796 s 20468966147602026522603053580076575157237760697508456381709480745538641437541 z 97850616939087590463493397125622705001932638558501235044372300801757315638202

real new k= 64826877121840101682523629462674967702936350352373549210422730086475468800457 50965212115476093741047355546012940149901213926701355172182433055042692693880 100011110101001010110
k proposed 64826877121840101682523629462674967702937679580369334126295633893540044112330 50965212115476093741047355546012940149899884698705570256309529247978117382007
k proposed 64826877121840101682523629462674967702937679580369334126295633893540044112328 50965212115476093741047355546012940149899884698705570256309529247978117382009
k proposed 41668459274376862597809432460937386132231792200853342159581826587990022006870 74123629962939332825761552547750521720605772078221562223023336553528139487467
k proposed 87985294969303340767237826464412549273643566959885326093009441199090066217788 27806794268012854656333158544275358579193997319189578289595721942428095276549
k proposed 54633834698744882934314158353472379672896797901813582026681906479914204298660 61158254538571312489256826655215528179940766377261322355923256661603957195677

what and how to read:

first we need one transactions as r s z (first upper real transaction)
we must find collisions in nearest plan Babai algorith ( it is hard) the output is new r s z with new nonce for pubkey from first transactions
the new k is "real new k"

once again we perform CVP on one signatures (the new one)
we get k proposed . and now look compare k proposed with real new k.

the problem is with bounding and it works for more than 240 bit . I do not know why I can't take value of nonce for below 2**240 bit

CrunchyF

jr. member

Activity: 54

Merit: 26

Quote from: ecdsa123 on October 31, 2022, 12:04:56 PM

I'm not taking about calculation privkey from collection signatures. You will not find my solutions on net. i rebuild LLL and way of rearranged for testing one signature as part r s z for finding closest pointt as integer value.

And if someone of you do the same we can discus

Ok can you tell me what are the inegality you want to resolve?
for what i learned the HNP problem is based on the following assumption:

α is a secret integer (it can be the privkey, or the nonce k for R).
The attacker is assumed to be given an oracle that given a random sequence of integers ti , for i ∈ {1, . . . , m}, returns a sequence ai such that

|ti.α − ai | mod q ≤ C

ti is a partial "leaked" information knowed by the attacker. so if you don't have ti it's impossible to resolve the inegality system.

An other thing intrigues me.. if you are able to guess the upper bit of a nonce , you will be able to guess every bit of the nonce because you just have to multiply R,S,Z by a power of 2 (mod N) to shift the bits at the desired place and redo the guessing..so ECDSA will be broken. In modular arithmetic every bit of a number have exactly the same "weight" unlike classical arithmetic where the upper bits have more weight that the lower

In this paper :

https://pdfs.semanticscholar.org/f8f7/ad041226bb4d2afd504d1372feafafa7efe8.pdf
some techniques are explained to guess certain bits of a nonce
but for example you can guess the third bit of the nonce (at a certain index) only if you know the two previous bits and you need for that a minimum of 80 leaked signatures.

ecdsa123

full member

Activity: 211

Merit: 105

Dr WHO on disney+

I'm not taking about calculation privkey from collection signatures. You will not find my solutions on net. i rebuild LLL and way of rearranged for testing one signature as part r s z for finding closest pointt as integer value.

And if someone of you do the same we can discus

CrunchyF

jr. member

Activity: 54

Merit: 26

Quote from: ecdsa123 on October 30, 2022, 12:39:37 PM

Dears

Did someone of you designed lattice for finding "upper bit" of nonce used in transaction?

I would like to discuss about it.

Code:

signature matches
r,s,z 48689154203859932735178617811990715115458951113100269383364565174585471617161 59488788402984084081847159809764481890644008521609461496494308766936034267606 59079767853462261938702612351887995533770336525476423798454265358689099134317
nonce upper bit 52958707970624021912956063206457566071499734389836203485954119293586656 0000000000000000000001111 True
nonce upper bit 52958707970624021912956063206457566151183141809120411787220724971382566 0000000000000000000001111 True
nonce upper bit 52958707970624021912956063206457566096964448935598356216995353203856658 0000000000000000000001111 True
nonce upper bit 52958707970624021912956063206457566125718427263358259056179491061112564 0000000000000000000001111 True
nonce upper bit 52958707970624021912956063206457566119102316860861579868337547139563925 0000000000000000000001111 True
nonce upper bit 52958707970624021912956063206457566103580559338095035404837297125405297 0000000000000000000001111 True
private key 647321811779000003997549197398845893 115792089237316195423570985008687907852836916957263125382601165592320762648444
real nonce 25790403829687632369718936211412764674628780345318086433686503628591346 115792063446912365735938615289751696440072889650294559064518729455014532902991
bin 0000000000000000000000111

I'm not sure to understand well your question
but for what i look on the net (and test myself) about lattice attack
it's only possible to find a private key of a collection of signatures in this two case
1) You know a minimum of 3-4 bits (not only the upper bit but everywhere in the 256 bits) of the k value in every signature (required around 80 signature for 4 bits to have a good probability of success).
2) you know that a there is fixed bits in every k (3 or 4 bits everywhere in the 256bits) => 252 bits of entropy

ecdsa123

full member

Activity: 211

Merit: 105

Dr WHO on disney+

Quote from: NotATether on October 31, 2022, 01:51:12 AM

When you say weak bits, you are referring to the ECDSA signature in the DER area?

If so, then you are probably referring to weak keys. It is nonsensical to talk about weak bits individually because all of the bits are processed together, and there is no way to determine a partially (percentage) weak key because the result wouldn't look like a weak key in those cases.

According to the link I just posted, nobody has found any weak keys in ECDSA... yet. The same is not true for RSA, though that only happens when you have insufficient entropy. So just use a large amount of entropy to generate your private keys or seed phrases and you should be fine.

exactly.
if and only if entrophy is less than 2**250 bit and more than 2**127 bit , there is chance as 99% to find upper bit of nonce and nonce is more than 240 bit.

if is less than 240 bit is not work. and I would like to discuss about is, where I made mistakes.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

When you say weak bits, you are referring to the ECDSA signature in the DER area?

If so, then you are probably referring to weak keys. It is nonsensical to talk about weak bits individually because all of the bits are processed together, and there is no way to determine a partially (percentage) weak key because the result wouldn't look like a weak key in those cases.

According to the link I just posted, nobody has found any weak keys in ECDSA... yet. The same is not true for RSA, though that only happens when you have insufficient entropy. So just use a large amount of entropy to generate your private keys or seed phrases and you should be fine.

ecdsa123

full member

Activity: 211

Merit: 105

Dr WHO on disney+

Quote from: PrivatePerson on October 30, 2022, 02:42:26 PM

If "r" starts with 000 - can this be considered a weak upper bit?
How to determine from a transaction that it has weak bits?

exactly.

PrivatePerson

member

Activity: 173

Merit: 12

If "r" starts with 000 - can this be considered a weak upper bit?
How to determine from a transaction that it has weak bits?

ecdsa123

full member

Activity: 211

Merit: 105

Dr WHO on disney+

Dears

Did someone of you designed lattice for finding "upper bit" of nonce used in transaction?

I would like to discuss about it.

Code:

signature matches
r,s,z 48689154203859932735178617811990715115458951113100269383364565174585471617161 59488788402984084081847159809764481890644008521609461496494308766936034267606 59079767853462261938702612351887995533770336525476423798454265358689099134317
nonce upper bit 52958707970624021912956063206457566071499734389836203485954119293586656 0000000000000000000001111 True
nonce upper bit 52958707970624021912956063206457566151183141809120411787220724971382566 0000000000000000000001111 True
nonce upper bit 52958707970624021912956063206457566096964448935598356216995353203856658 0000000000000000000001111 True
nonce upper bit 52958707970624021912956063206457566125718427263358259056179491061112564 0000000000000000000001111 True
nonce upper bit 52958707970624021912956063206457566119102316860861579868337547139563925 0000000000000000000001111 True
nonce upper bit 52958707970624021912956063206457566103580559338095035404837297125405297 0000000000000000000001111 True
private key 647321811779000003997549197398845893 115792089237316195423570985008687907852836916957263125382601165592320762648444
real nonce 25790403829687632369718936211412764674628780345318086433686503628591346 115792063446912365735938615289751696440072889650294559064518729455014532902991
bin 0000000000000000000000111

Topic: Lattice used for finding range of nonce in transactions - academic question (Read 298 times)