show priv of 120, 125 or 130 bit ouzzle ?
pls
Topic: lattice-attack || how to run without error - page 3. (Read 3185 times)
@ecdsa, collect some real rsz from blockchain and try your code ?
can use 1 transaction with many output. Posibl it will be more easy for use
thx.
can use 1 transaction with many output. Posibl it will be more easy for use
thx.
it is useless. as inform if you know subrange it is 6 hours. if not "time is years ior milleniums",
I have use to try : https://eprint.iacr.org/2022/385 White-Box
and here pdf: https://eprint.iacr.org/2022/385.pdf
how get subranges ? code for get them pls ?
@ecdsa, collect some real rsz from blockchain and try your code ?
can use 1 transaction with many output. Posibl it will be more easy for use
thx.
can use 1 transaction with many output. Posibl it will be more easy for use
thx.
Quote
ecdsa123 realy find partial nonce ?
I don't know. For now, I don't have any proof. No moved coins, no revealed keys, so not yet. But I think it will soon be obvious, is this attack successful or not (today, I guess it will fail). I think I understand. I guess it means that such attack is trying to solve x=2y by adding 2x=4y. It won't work. Why? Because it would be "degenerate system of equations", so it won't produce any new solutions, everything will be as unknown, as it was before.
ecdsa123 realy find partial nonce ?
I think I understand. I guess it means that such attack is trying to solve x=2y by adding 2x=4y. It won't work. Why? Because it would be "degenerate system of equations", so it won't produce any new solutions, everything will be as unknown, as it was before.
Signatures derived this way is most likely reaching to degenerate system of equations incomprehensible by Lattice reduction.
can u explain more please?
As you can see, it works. There are 100 signatures. Lattice cannot reveal the solution, no matter that all signatures are in 240-bit range. By checking "z/r" and "r/s", you can make sure that all of my signatures are in the correct range, just assume that the private key is in 120-bit range, and do addition/multiplication to see the range of the signature nonces.
Signatures derived this way is most likely reaching to degenerate system of equations incomprehensible by Lattice reduction.
Quote
or change for allow to receive e-mail from newbie
Changed. But I don't know, why I am so important? ECDSA security can be discussed publicly, for example here, in this topic. People should be aware of all possible attacks and be ready to deal with them. But of course I can also respond to private messages, no problem.Yes, discus publicly. Sacces can be in 0,1%. Maybe someone can add good things to discus
Quote
or change for allow to receive e-mail from newbie
Changed. But I don't know, why I am so important? ECDSA security can be discussed publicly, for example here, in this topic. People should be aware of all possible attacks and be ready to deal with them. But of course I can also respond to private messages, no problem. formule "450 / 9 = priv" not work for all sighns.
I thin is very hard or inposivle crack with lattice . Method very expesive of time...
I thin is very hard or inposivle crack with lattice . Method very expesive of time...
Have you ran benchmarks on this program? GNU/Linux has a "time" command which you can use to measure the running time of a program.
Maybe a little modular invert doesn't take much time but when you start doing that to hundreds of signatures, you start to notice the slwness.
Alternatively, you can gain a (limited) performance speedup by converting it to C language utilizing pthreads.
Lattice is about 500 sighnatures max. not cheched perfofance. but, formula 450 /9 work not for all sighnatures.
interesting check know part, I nit checked ... ni tine for this. If know part finder work ithis is a good new, and this enoth for find priv
ecdsa123, not answered, naybe hi provide something more interesting, will see
modular inv can make illusion of saccess, and add unknown var to formula. Then in fornula only uknown vars and them modification this maybe can be false positive results.Maybe ecdsa123, find false positive result and not writing more...
@ecdsa123, come on, lets talk, maybe we find something usefull
formule "450 / 9 = priv" not work for all sighns.
I thin is very hard or inposivle crack with lattice . Method very expesive of time...
I thin is very hard or inposivle crack with lattice . Method very expesive of time...
Have you ran benchmarks on this program? GNU/Linux has a "time" command which you can use to measure the running time of a program.
Maybe a little modular invert doesn't take much time but when you start doing that to hundreds of signatures, you start to notice the slwness.
Alternatively, you can gain a (limited) performance speedup by converting it to C language utilizing pthreads.
First, we look at signatures:
Then, things are quite simple:
But we can do more than that:
If "d" is our 120_bit_privkey, then first we add another 120_bit number to that (we can use 119-bit numbers to be 100% sure). Then, we have 121-bit number at most, it cannot be bigger. And if we multiply that by another 119-bit number (just to be sure), then we will have 121+119=240 bits in our result. It cannot be bigger than that, because if you multiply M-bit number by N-bit number, then the result has at most M+N bits. So, in this way I can be absolutely sure that if "d" is a 120-bit number, then "k" is a 240-bit number. In the same way, it is possible to generate many signatures with many different N-bit values. But it is still not enough to use that in a lattice attack, because it needs some randomness in the right places, so something else is also needed to make it.
Edit:
Code:
s=(z+rd)/k
sk=z+rd
sk-z=rd
(sk-z)/r=d
(s/r)k-(z/r)=d
(z/r)+d=(s/r)k
k=((z/r)+d)*(r/s)
Code:
z/r=random
r/s=random
Code:
z/r=120_bit_number_v1
r/s=120_bit_number_v2
k=(120_bit_number_v1+d)*120_bit_number_v2
Edit:
Quote
show your code
Code:
def generates_signatures(curve):
puzzle120=int("00000000000000000000000000000000007fffffffffffffffffffffffffffff",16) #119-bit to be 100% sure to not fall into 241-bit range
known_bits=16
n_value=ecdsa_lib.curve_n(curve)
Q_point=[93499419120076195219278579763555015417347613618260420189054155605804414805552,19494200143356336257404688340550956357466777176798681646526975620299854296492]
sigs = []
for index in range(100):
binaryIndex=(index*2).to_bytes(32,'big')
binaryIndex2=(index*2+1).to_bytes(32,'big')
hashedIndex=ecdsa_lib.sha2_int(binaryIndex)
hashedIndex2=ecdsa_lib.sha2_int(binaryIndex2)
z_value_with_r=(hashedIndex%puzzle120)
added_point=ecdsa_lib.privkey_to_pubkey(z_value_with_r,curve)
final_point=add_point(Q_point[0],Q_point[1],added_point[0],added_point[1])
r_value_with_s=(hashedIndex2%puzzle120)
R_point=multiply_point(final_point[0],final_point[1],r_value_with_s)
r_value=R_point[0]
s_value_with_r=ecdsa_lib.inverse_mod(r_value_with_s,n_value)
s_value=(s_value_with_r*r_value)%n_value
z_value=(z_value_with_r*r_value)%n_value
sigs.append(
{
"r": r_value,
"s": s_value,
"kp": 0,
"hash": z_value
}
)
ret = {
"curve": curve.upper(),
"public_key": Q_point,
"known_type": "MSB",
"known_bits": known_bits,
"signatures": sigs,
}
return ret
can we add to sighnatures 121 bit what starts with 000000 ? this will.make lsb from our sighs ?
if we thant divede is more easy, I try this method on publick key. For removing trandfer from + area to - area, is more good start with pubkey * -1, this will transfer pubkey priv range from -1 to -1-rage, result will belarge than -1, and range will be simple without start from 1 to N,, -N to -F, and will be -N to -F...
this is puzzle 100 privkey
./md 0xaf55fc59c335c8ec67ed24826 - 0xfffffffffffffffffffffffff
Result: fffffffffffffffffffffffffffffffebaaedce1a4a865d7f32eed534f088968
then subsract too mach, tlrange will be shifted to negative area, and nothin will be found in positivevsearch range
but then start from negative area result will be maybe negative too
./md 0xfffffffffffffffffffffffffffffffebaaedcdbb9e8da9f8c75cfc65163f91b + 0xffffffffffffffffffffffff
Result: fffffffffffffffffffffffffffffffebaaedcdcb9e8da9f8c75cfc65163f91a
so search in negative area is more good I think.
but found how many need substeact is not solved me. then subsract too mach privkey if publey start accumulate more bits, not substract.
ps maybe this info will be helpfull
Code:
[code]I have rewrite code for sagemath
from hashlib import sha256
import struct
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
a = 0
b = 7
G = (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
E = EllipticCurve(GF(p), [a, b])
G = E(G)
def bytes_to_long(s):
"""bytes_to_long(strinng) : long
Convert a byte string to a long integer.
This is (essentially) the inverse of long_to_bytes().
"""
acc = 0L
unpack = struct.unpack
length = len(s)
if length % 4:
extra = (4 - length % 4)
s = b('\000') * extra + s
length = length + extra
for i in range(0, length, 4):
acc = (acc << 32) + unpack('>I', s[i:i+4])[0]
return acc
def H(m):
h = sha256()
h.update(m)
return bytes_to_long(h.digest())
def egcd(a, b):
"Euclidean greatest common divisor"
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
"Modular inverse"
# in Python 3.8 you can simply return pow(a,-1,m)
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
def verify(pub,r, s, m):
v1 = m*modinv(s, n) % n
v2 = r*modinv(s, n) % n
V = v1*G + v2*pub
x,y=V.xy()
return int(x) % n == r,hex(int(v1)),hex(int(v2))
def calc_k(num,r,s,z):
k=(r*num + z)*modinv(s,n)%n
return k,n-k
sign=[]
ge=[]
def calc_x(a,b,r,s,z):
#x1 = (z1 -b)*modinv(a*s1-r1,n)%n
x_a =(z -b)%n
x_b=(a*s-r)%n
if x_b != 0:
return (x_a*modinv(x_b,n)%n)%n
return 0
def generates_signatures():
puzzle120=16
n_value=n
sigs = []
private=50
Qp=private*G
for index in range(130):
print("---- index",index)
binaryIndex=int((index*3)).to_bytes(32,'big')
binaryIndex2=int((index*2+1)).to_bytes(32,'big')
hashedIndex=H(binaryIndex)
hashedIndex2=H(binaryIndex2)
z_value_with_r=(hashedIndex%puzzle120)
added_point= int(z_value_with_r)*G
final_point=Qp+added_point
r_value_with_s=(hashedIndex2%puzzle120)
print(r_value_with_s)
if r_value_with_s!=0:
R_point=final_point*int(r_value_with_s)
x,y=R_point.xy()
r_value=int(x)
s_value_with_r=int(modinv(r_value_with_s,n)%n)
s_value=int((s_value_with_r*r_value)%n)
z_value=((z_value_with_r*r_value)%n)
print("r", r_value)
print("s", s_value)
print("hash", z_value)
k,k1=calc_k(private,r_value,s_value,z_value)
print("k",k,k1)
print("k",hex(k),hex(k1))
print(verify(Qp,r_value,s_value,z_value))
wy,b,a=verify(Qp,r_value,s_value,z_value)
x=calc_x(int(a,16),int(b,16),int(r_value),int(s_value),int(z_value))
print("x",x)
k,k1=calc_k(x,r_value,s_value,z_value)
print("k",k,k1)
print("k",hex(k),hex(k1))
t=tuple([r_value,s_value,z_value])
if t not in sign:
sign.append(t)
for le in range(0,1000):
k2=(k*2**le)%n
ge.append(int(k2))
ge.append(int(n-k2))
generates_signatures()
here is part of output:
Code:
---- index 18
9
r 63933145574282734898435981717146773918756897333098319278256437952015461322467
s 97164196692832900318159208530884680987624427476291405550721397771404732420314
hash 0
k 450 115792089237316195423570985008687907852837564279074904382605163141518161493887
k 0x1c2 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0363f7f
(True, '0x0', '0x9')
x 0
so according above:
private key = 50
k= 450
how the nonce k is calculated from pubkey (private key)
simple:
a*d + b = k nonce
here a=9 and b = 0
so 9* 50 + 0 = 450
confirm : (True, '0x0', '0x9')
it is generator
it is useless.
[/code]
./md 450 x -1
Result: fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0363f7f
= 115792089237316195423570985008687907852837564279074904382605163141518161493887
this is inversion of 450
you thant say what this is real nonce ?
I think generator must be for ex y = X^400, x is a generator. .
Br
Cobras:
./md 450 x -1
Result: fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0363f7f
= 115792089237316195423570985008687907852837564279074904382605163141518161493887
this is inversion of 450
this value 115792089237316195423570985008687907852837564279074904382605163141518161493887 = n-450
so d*(-1)%n = n-d
but according Garlonicon Generator ( yes, it is master math deduction Bravo for Garlonicon), we can use it:
becouse:
Code:
---- index 18
37929
r 106052440004676334409650332163651951923042923173423795888106072423870533309482
s 86487388237072824922585675463188678676341543446573502861944943782026730667995
hash 110763458801388154151046907647238024857062280457110140174709389756661623888001
k 1495388754 115792089237316195423570985008687907852837564279074904382605163141516666105583
k 0x5921d252 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8c77146eef
(True, '0x5904e250', '0x9429')
x 0
k 1493492304 115792089237316195423570985008687907852837564279074904382605163141516668002033
k 0x5904e250 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8c77315ef1
---- index 19
21317
r 18103990796095223393229492283858137777181144560247153354193996653271708547693
s 71995424062587838315307175718789388226264777318544777869325093881612562000023
hash 74553635558632807494232092124236529938587320104480240499961671012084809061673
k 139541082 115792089237316195423570985008687907852837564279074904382605163141518021953255
k 0x8513a5a 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cc7e506e7
(True, '0x840f6e0', '0x5345')
x 0
k 138475232 115792089237316195423570985008687907852837564279074904382605163141518023019105
k 0x840f6e0 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cc7f54a61
we know a part of k for any transaction(index)
see Index 19:
real k in transaction : k 139541082
but we know to real part as bits from this k : k 138475232
we can try use Lcd algorithm.
Tomorrow I will try check.
ok, waiting result with big interestps
139541082
13 is 2 bytes, so 16 bits, this is enoth for finding priv...
for all other transaction we have 2 bytes 2 )
try please find 2 bytes it will be good too ....
I know what you know this, but maybe you forget avout it.. regards
Code:
[code]I have rewrite code for sagemath
from hashlib import sha256
import struct
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
a = 0
b = 7
G = (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
E = EllipticCurve(GF(p), [a, b])
G = E(G)
def bytes_to_long(s):
"""bytes_to_long(strinng) : long
Convert a byte string to a long integer.
This is (essentially) the inverse of long_to_bytes().
"""
acc = 0L
unpack = struct.unpack
length = len(s)
if length % 4:
extra = (4 - length % 4)
s = b('\000') * extra + s
length = length + extra
for i in range(0, length, 4):
acc = (acc << 32) + unpack('>I', s[i:i+4])[0]
return acc
def H(m):
h = sha256()
h.update(m)
return bytes_to_long(h.digest())
def egcd(a, b):
"Euclidean greatest common divisor"
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
"Modular inverse"
# in Python 3.8 you can simply return pow(a,-1,m)
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
def verify(pub,r, s, m):
v1 = m*modinv(s, n) % n
v2 = r*modinv(s, n) % n
V = v1*G + v2*pub
x,y=V.xy()
return int(x) % n == r,hex(int(v1)),hex(int(v2))
def calc_k(num,r,s,z):
k=(r*num + z)*modinv(s,n)%n
return k,n-k
sign=[]
ge=[]
def calc_x(a,b,r,s,z):
#x1 = (z1 -b)*modinv(a*s1-r1,n)%n
x_a =(z -b)%n
x_b=(a*s-r)%n
if x_b != 0:
return (x_a*modinv(x_b,n)%n)%n
return 0
def generates_signatures():
puzzle120=16
n_value=n
sigs = []
private=50
Qp=private*G
for index in range(130):
print("---- index",index)
binaryIndex=int((index*3)).to_bytes(32,'big')
binaryIndex2=int((index*2+1)).to_bytes(32,'big')
hashedIndex=H(binaryIndex)
hashedIndex2=H(binaryIndex2)
z_value_with_r=(hashedIndex%puzzle120)
added_point= int(z_value_with_r)*G
final_point=Qp+added_point
r_value_with_s=(hashedIndex2%puzzle120)
print(r_value_with_s)
if r_value_with_s!=0:
R_point=final_point*int(r_value_with_s)
x,y=R_point.xy()
r_value=int(x)
s_value_with_r=int(modinv(r_value_with_s,n)%n)
s_value=int((s_value_with_r*r_value)%n)
z_value=((z_value_with_r*r_value)%n)
print("r", r_value)
print("s", s_value)
print("hash", z_value)
k,k1=calc_k(private,r_value,s_value,z_value)
print("k",k,k1)
print("k",hex(k),hex(k1))
print(verify(Qp,r_value,s_value,z_value))
wy,b,a=verify(Qp,r_value,s_value,z_value)
x=calc_x(int(a,16),int(b,16),int(r_value),int(s_value),int(z_value))
print("x",x)
k,k1=calc_k(x,r_value,s_value,z_value)
print("k",k,k1)
print("k",hex(k),hex(k1))
t=tuple([r_value,s_value,z_value])
if t not in sign:
sign.append(t)
for le in range(0,1000):
k2=(k*2**le)%n
ge.append(int(k2))
ge.append(int(n-k2))
generates_signatures()
here is part of output:
Code:
---- index 18
9
r 63933145574282734898435981717146773918756897333098319278256437952015461322467
s 97164196692832900318159208530884680987624427476291405550721397771404732420314
hash 0
k 450 115792089237316195423570985008687907852837564279074904382605163141518161493887
k 0x1c2 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0363f7f
(True, '0x0', '0x9')
x 0
so according above:
private key = 50
k= 450
how the nonce k is calculated from pubkey (private key)
simple:
a*d + b = k nonce
here a=9 and b = 0
so 9* 50 + 0 = 450
confirm : (True, '0x0', '0x9')
it is generator
it is useless.
[/code]
./md 450 x -1
Result: fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0363f7f
= 115792089237316195423570985008687907852837564279074904382605163141518161493887
this is inversion of 450
you thant say what this is real nonce ?
I think generator must be for ex y = X^400, x is a generator. .
Br
Someone, please, upload sage scryot to transfer.sh I from phone, very hard copy/paste without lost tabulation
Regards
@ecdsa123 is any news about lcd ?
br
Code:
[code]I have rewrite code for sagemath
from hashlib import sha256
import struct
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
a = 0
b = 7
G = (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
E = EllipticCurve(GF(p), [a, b])
G = E(G)
def bytes_to_long(s):
"""bytes_to_long(strinng) : long
Convert a byte string to a long integer.
This is (essentially) the inverse of long_to_bytes().
"""
acc = 0L
unpack = struct.unpack
length = len(s)
if length % 4:
extra = (4 - length % 4)
s = b('\000') * extra + s
length = length + extra
for i in range(0, length, 4):
acc = (acc << 32) + unpack('>I', s[i:i+4])[0]
return acc
def H(m):
h = sha256()
h.update(m)
return bytes_to_long(h.digest())
def egcd(a, b):
"Euclidean greatest common divisor"
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
"Modular inverse"
# in Python 3.8 you can simply return pow(a,-1,m)
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
def verify(pub,r, s, m):
v1 = m*modinv(s, n) % n
v2 = r*modinv(s, n) % n
V = v1*G + v2*pub
x,y=V.xy()
return int(x) % n == r,hex(int(v1)),hex(int(v2))
def calc_k(num,r,s,z):
k=(r*num + z)*modinv(s,n)%n
return k,n-k
sign=[]
ge=[]
def calc_x(a,b,r,s,z):
#x1 = (z1 -b)*modinv(a*s1-r1,n)%n
x_a =(z -b)%n
x_b=(a*s-r)%n
if x_b != 0:
return (x_a*modinv(x_b,n)%n)%n
return 0
def generates_signatures():
puzzle120=16
n_value=n
sigs = []
private=50
Qp=private*G
for index in range(130):
print("---- index",index)
binaryIndex=int((index*3)).to_bytes(32,'big')
binaryIndex2=int((index*2+1)).to_bytes(32,'big')
hashedIndex=H(binaryIndex)
hashedIndex2=H(binaryIndex2)
z_value_with_r=(hashedIndex%puzzle120)
added_point= int(z_value_with_r)*G
final_point=Qp+added_point
r_value_with_s=(hashedIndex2%puzzle120)
print(r_value_with_s)
if r_value_with_s!=0:
R_point=final_point*int(r_value_with_s)
x,y=R_point.xy()
r_value=int(x)
s_value_with_r=int(modinv(r_value_with_s,n)%n)
s_value=int((s_value_with_r*r_value)%n)
z_value=((z_value_with_r*r_value)%n)
print("r", r_value)
print("s", s_value)
print("hash", z_value)
k,k1=calc_k(private,r_value,s_value,z_value)
print("k",k,k1)
print("k",hex(k),hex(k1))
print(verify(Qp,r_value,s_value,z_value))
wy,b,a=verify(Qp,r_value,s_value,z_value)
x=calc_x(int(a,16),int(b,16),int(r_value),int(s_value),int(z_value))
print("x",x)
k,k1=calc_k(x,r_value,s_value,z_value)
print("k",k,k1)
print("k",hex(k),hex(k1))
t=tuple([r_value,s_value,z_value])
if t not in sign:
sign.append(t)
for le in range(0,1000):
k2=(k*2**le)%n
ge.append(int(k2))
ge.append(int(n-k2))
generates_signatures()
here is part of output:
Code:
---- index 18
9
r 63933145574282734898435981717146773918756897333098319278256437952015461322467
s 97164196692832900318159208530884680987624427476291405550721397771404732420314
hash 0
k 450 115792089237316195423570985008687907852837564279074904382605163141518161493887
k 0x1c2 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0363f7f
(True, '0x0', '0x9')
x 0
so according above:
private key = 50
k= 450
how the nonce k is calculated from pubkey (private key)
simple:
a*d + b = k nonce
here a=9 and b = 0
so 9* 50 + 0 = 450
confirm : (True, '0x0', '0x9')
it is generator
it is useless.
[/code]
formule "450 / 9 = priv" not work for all sighns.
I thin is very hard or inposivle crack with lattice . Method very expesive of time...
[moderator's note: consecutive posts merged]
Quote
becouse now it is generator , you have connected transactions
They are not, because it is used for hashing. So, you have SHA-256 of that. You can put "random" numbers here, but hashing can make it easier to reproduce each result when needed. @garlonicon, @ecdsa123 please reascthis pdf file. This is intresting fresh methos with success >60% but need deper knowlage of math and python then what I have.
https://eprint.iacr.org › ...PDF
A Tale of Three Signatures: practical attack of ECDSA with wNAF
You will find this pdf easy in google.
First, we look at signatures:
Then, things are quite simple:
But we can do more than that:
If "d" is our 120_bit_privkey, then first we add another 120_bit number to that (we can use 119-bit numbers to be 100% sure). Then, we have 121-bit number at most, it cannot be bigger. And if we multiply that by another 119-bit number (just to be sure), then we will have 121+119=240 bits in our result. It cannot be bigger than that, because if you multiply M-bit number by N-bit number, then the result has at most M+N bits. So, in this way I can be absolutely sure that if "d" is a 120-bit number, then "k" is a 240-bit number. In the same way, it is possible to generate many signatures with many different N-bit values. But it is still not enough to use that in a lattice attack, because it needs some randomness in the right places, so something else is also needed to make it.
Edit:
Code:
s=(z+rd)/k
sk=z+rd
sk-z=rd
(sk-z)/r=d
(s/r)k-(z/r)=d
(z/r)+d=(s/r)k
k=((z/r)+d)*(r/s)
Code:
z/r=random
r/s=random
Code:
z/r=120_bit_number_v1
r/s=120_bit_number_v2
k=(120_bit_number_v1+d)*120_bit_number_v2
Edit:
Quote
show your code
Code:
def generates_signatures(curve):
puzzle120=int("00000000000000000000000000000000007fffffffffffffffffffffffffffff",16) #119-bit to be 100% sure to not fall into 241-bit range
known_bits=16
n_value=ecdsa_lib.curve_n(curve)
Q_point=[93499419120076195219278579763555015417347613618260420189054155605804414805552,19494200143356336257404688340550956357466777176798681646526975620299854296492]
sigs = []
for index in range(100):
binaryIndex=(index*2).to_bytes(32,'big')
binaryIndex2=(index*2+1).to_bytes(32,'big')
hashedIndex=ecdsa_lib.sha2_int(binaryIndex)
hashedIndex2=ecdsa_lib.sha2_int(binaryIndex2)
z_value_with_r=(hashedIndex%puzzle120)
added_point=ecdsa_lib.privkey_to_pubkey(z_value_with_r,curve)
final_point=add_point(Q_point[0],Q_point[1],added_point[0],added_point[1])
r_value_with_s=(hashedIndex2%puzzle120)
R_point=multiply_point(final_point[0],final_point[1],r_value_with_s)
r_value=R_point[0]
s_value_with_r=ecdsa_lib.inverse_mod(r_value_with_s,n_value)
s_value=(s_value_with_r*r_value)%n_value
z_value=(z_value_with_r*r_value)%n_value
sigs.append(
{
"r": r_value,
"s": s_value,
"kp": 0,
"hash": z_value
}
)
ret = {
"curve": curve.upper(),
"public_key": Q_point,
"known_type": "MSB",
"known_bits": known_bits,
"signatures": sigs,
}
return ret
@garlonicon
Confuse with nonce and random int use in signing ?
Even with nonce 1 random int in sign always in 250 or higher bit.
From public key we can multiply random int which increase public key hidden number known as K,
so random int is a * K = R is generated.
Now same public key with 120 bit random int for multiplication
as you see, K is multiply whatever value we use for random int.
How ever there is one more thing if we multiply any public key with (N//2)+1 strange K come if private key is EVEN.
This break private key in half. K is half of private key so R is half of public key.
Example
Confuse with nonce and random int use in signing ?
Even with nonce 1 random int in sign always in 250 or higher bit.
From public key we can multiply random int which increase public key hidden number known as K,
so random int is a * K = R is generated.
Code:
private key 0x1000
public points
px: 0x175e159f728b865a72f99cc6c6fc846de0b93833fd2222ed73fce5b551e5b739
py: 0xd3506e0d9e3c79eba4ef97a51ff71f5eacb5955add24345c6efa6ffee9fed695
k:1
r: 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
s: 0xe667ef9dcbbac55a06295ce870b079d3efe3a465c532ef334320987bf4d736a5
z: 0x0
SIGN_U: 0x0000000000000000000000000000000000000000000000000000000000000000
SIGN_V: 0x13efffffffffffffffffffffffffffffe6a9fe543746b7faa740723d177739b5
as you can see example
0x13efffffffffffffffffffffffffffffe6a9fe543746b7faa740723d177739b5
Now same public key with 120 bit random int for multiplication
Code:
K: 0x000000000000000000000000000000079d523ff7bb533dc6d6fabf75a30ac000
R: 0xdaff9f3f66aae00146a41c5401fa148a9f3945b9bb9045f12c21d0bf43b5b330
S: 0x45127dc4fbeffc546746250887e2aadcbd214576b74b0202a2667ae3ad900a59
Z: 0x0000000000000000000000000000000000000000000000000000000000000000
SIGN_U: 0x0000000000000000000000000000000000000000000000000000000000000000
SIGN_V: 0x000000000000000000000000000000000079d523ff7bb533dc6d6fabf75a30ac
Sign is := True
as you see, K is multiply whatever value we use for random int.
How ever there is one more thing if we multiply any public key with (N//2)+1 strange K come if private key is EVEN.
This break private key in half. K is half of private key so R is half of public key.
Example
Code:
K: 0x0000000000000000000000000000000000000000000000000000000000000800
R: 0x5d1bdb4ea172fa79fce4cc2983d8f8d9fc318b85f423de0dedcb63069b920471
S: 0xba37b69d42e5f4f3f9c9985307b1f1b3f863170be847bc1bdb96c60d372408e2
Z: 0x0000000000000000000000000000000000000000000000000000000000000000
SIGN_U: 0x0000000000000000000000000000000000000000000000000000000000000000
SIGN_V: 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1
Sign is := True
Quote
can you generate for puz 120, 89 sighns with nonce not more 2^248 ?
Quote
no one can, unless you know the privkey
It is the opposite, everyone can do that. As I said, you only need the public key: https://pastebin.com/4fxUSrZTCode:
x=0xceb6cbbcdbdf5ef7150682150f4ce2c6f4807b349827dcdbdd1f2efa885a2630
y=0x2b195386bea3f5f002dc033b92cfc2c9e71b586302b09cfe535e1ff290b1b5ac
r1=c923e141c9c6d8aacc1cda5f5fb88f04deb0b9edc4dcfb7fdedbfa5e378f7be4
s1=d94dda4835f0f508ce3dd254e1dbb305036ff2d730d358d88a3baabe9d62b8dd
z1=20a4ddb78e28c3a53c205044e406033888d0747104a1aa7cea6060f745f01b3c
n=fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
1/r1=53491f1b04c43dd53f7fb49494addad940a027ffdd1a8c1042b8d8b2533057ac
1/s1=be72598b2890fb2dc5e9516660a3938c2227e0d4c48b3acf8265c2e224204572
z1*(1/r1)=00000000000000000000000000000000000c7076345d228cafad703a4c7d02d8
r1*(1/s1)=000000000000000000000000000000000048a18eb8762a75cfc41e17ae48e0c5
This is an example from the data.json file from https://github.com/bitlogik/lattice-attack
{"curve": "SECP256K1", "public_key": [66412380102939781024918160349386680014552536369061587637080774389860461092925, 43765600116551195273677149966008783624760986110490190619082891899095205821463], "known_type": "LSB", "known_bits": 6, "signatures": [{"r": 77527664235581399957092079345479688400475999610428178825522649055070157244692, "s": 27028479468528243957334746793835087615740874028178347534667218420099431266524, "kp": 51, "hash": 36925504434266069211917383521197840104244330385311344434522880060028429358956}, {"r": 1695214956238129249280118258814363243967244974939577175204794511553033886344, "s": 84915535421556974430475608108845062567200591001138706902138971666887762297461, "kp": 23, "hash": 76485972818364982894032873079629726025969313708578174583231327504986349400949}, {"r": 109269381046386034156037076068908319933850763940108273610325408412215759654951, "s": 48609197671516297208867726715248596584655415925682996149314879813291177259719, "kp": 49, "hash": 8857850795789766547675189849758610890848461200122419912004299328172940180927}, {"r": 41835540276419198058500360048414380626372941221767888918686846392248041576696, "s": 1825469084617584873286736453038639812754935222429578990673573348028125348352, "kp": 29, "hash": 11771613120662486178657899205469606751879506909643902145426207541353014498651}, {"r": 107103142771724135475440435595118756234545765813796109423691918131480012001322, "s": 76403726951992633295737606623610572293691262686449016257400538234410247449075, "kp": 44, "hash": 109029154205057617106956764551702586575882058359417649302233515615948131520073}, {"r": 54544573696288124190943111180088654937224138523771919858599448193516058012815, "s": 75774534848938869077595821409914703967303095416625781047518021857023231109081, "kp": 44, "hash":
Is this the public key its trying to look for [66412380102939781024918160349386680014552536369061587637080774389860461092925, 43765600116551195273677149966008783624760986110490190619082891899095205821463] ?
So I convert the r,s,z into decimal, I see the r and s. Which one is the z, is it the kp?
I'm trying to see what goes where.
{"curve": "SECP256K1", "public_key": [66412380102939781024918160349386680014552536369061587637080774389860461092925, 43765600116551195273677149966008783624760986110490190619082891899095205821463], "known_type": "LSB", "known_bits": 6, "signatures": [{"r": 77527664235581399957092079345479688400475999610428178825522649055070157244692, "s": 27028479468528243957334746793835087615740874028178347534667218420099431266524, "kp": 51, "hash": 36925504434266069211917383521197840104244330385311344434522880060028429358956}, {"r": 1695214956238129249280118258814363243967244974939577175204794511553033886344, "s": 84915535421556974430475608108845062567200591001138706902138971666887762297461, "kp": 23, "hash": 76485972818364982894032873079629726025969313708578174583231327504986349400949}, {"r": 109269381046386034156037076068908319933850763940108273610325408412215759654951, "s": 48609197671516297208867726715248596584655415925682996149314879813291177259719, "kp": 49, "hash": 8857850795789766547675189849758610890848461200122419912004299328172940180927}, {"r": 41835540276419198058500360048414380626372941221767888918686846392248041576696, "s": 1825469084617584873286736453038639812754935222429578990673573348028125348352, "kp": 29, "hash": 11771613120662486178657899205469606751879506909643902145426207541353014498651}, {"r": 107103142771724135475440435595118756234545765813796109423691918131480012001322, "s": 76403726951992633295737606623610572293691262686449016257400538234410247449075, "kp": 44, "hash": 109029154205057617106956764551702586575882058359417649302233515615948131520073}, {"r": 54544573696288124190943111180088654937224138523771919858599448193516058012815, "s": 75774534848938869077595821409914703967303095416625781047518021857023231109081, "kp": 44, "hash":
Is this the public key its trying to look for [66412380102939781024918160349386680014552536369061587637080774389860461092925, 43765600116551195273677149966008783624760986110490190619082891899095205821463] ?
So I convert the r,s,z into decimal, I see the r and s. Which one is the z, is it the kp?
I'm trying to see what goes where.
Read careful example file and will find all you need. first kp for ex = 51.hash is a z
Jump to: