Bitcoin Forum
May 15, 2024, 05:20:52 AM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
  Home Help Search Login Register More  
  Show Posts
Pages: [1] 2 3 »
1  Bitcoin / Development & Technical Discussion / Re: Bounty offered to crack the seeds for NIST curves! on: November 03, 2023, 03:50:25 PM
I code a quick and dirty CUDA program  for sha1 mining.
The speed i observe is around 5 Giga hash (tries) / second on a RTX3090.
The big problem would be the way to generate the password candidate. (probably slower than the hash)
Have anyone think about it?
the solution with the linux pipe "|"
Code:
generator | ./cuda_hasher_sha1
would be the more convenient but i don't think than it can support such a speed
2  Bitcoin / Development & Technical Discussion / Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 on: September 11, 2023, 09:57:39 PM
6. Make sure that "n" is different than "p".
7. Validate that if you pick "n" as the starting prime, and go through all steps, you will reach "p".
You didn't explain why you want these properties of 2 curves forming a 2-cycle.

Is it just because this is the case for secp256k1, as noted for example (together with other interesting properties) in [1] ?

[1] https://hackmd.io/@dJO3Nbl4RTirkR2uDM6eOA/Bk0NvC8Vo

Tromp could u explain more what sort of coincidence you speak about on your link [1]

This sage script doesn't find that it is rare to have the property of the post linked when P and N are primes...:

Code:
ROUNDS=10000
for i in range(ROUNDS):
    P=randint(1,2**256)
    P=next_prime(P)
    F=FiniteField(P)
    C = EllipticCurve([F(0), F(7)])
    
    N=C.order()

    if is_prime(N):
        print('P:',P)
        print('N:',N)
        N1=EllipticCurve(GF(P), [0, 1]).order()
        N2=EllipticCurve(GF(N), [0, 1]).order()

        print('N1:',N1)
        print('N2:',N2)
        print(N1==N2)
        print('')
3  Bitcoin / Bitcoin Technical Support / Re: Need Urgent Help To Recover My Old Lost Wallet on: August 23, 2023, 01:11:40 PM
Little explanation.

b. we know partial WIF of privatekey as nonce - we can use Monte Carlo together with LLL

c. recentering for partial integers plus BKZ or LLL.

becouse: IF OP has partial WIF example knowns MSB , not known middle, and Known LSB - it is easy even for 23 missing characters.

Post Scriptum: depends how much MSB with LSB we know - maybe we need implement enumeration.

Do u mean that you can use Lattice attack only with one signature? Have u sources or studies to show about this attack?
4  Bitcoin / Bitcoin Technical Support / Re: Need Urgent Help To Recover My Old Lost Wallet on: August 21, 2023, 05:10:40 PM

any help will be appreciated too much   Smiley


Could you give us the public address of your wallet?
5  Bitcoin / Development & Technical Discussion / Re: Points where x=y on secp256k1 on: July 29, 2023, 12:30:35 PM

Main question, what would be the result of finding such points on secp256k1?

Absolutely nothing because one Generator in not different from another in term of security
6  Bitcoin / Development & Technical Discussion / Re: Points where x=y on secp256k1 on: July 29, 2023, 12:25:14 PM

How do you know that? Is there any simple way to check, if for a given p-value, there is such point or not?
the equation of the secp256k1 curve is
x³+7=y² mod(P)
or

x³+7-y²=0 mod(P)
 
if x=y
then
x³-x²+7=0

this equation is a polynomial of degree 3 in Finite Field and have no roots (solutions)

Quote
but there is one where x==y+1
Nice result! But how it was calculated?

instead of looking for x=y we can find if roots exists replacing x=y+c  in the polynomial equation
where c in a constant varying between the range [-10;10] e.g
This is my Sage script:
Code:
P=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
C = EllipticCurve([F(0), F(7)])
F=GF(P)
R.<x>=F[]
for c in range(-10,10,1):
    f=((x)**3+7)-(x+c)**2
    rts=f.roots()
    for r in rts:
        try:
            G=C.lift_x(r[0])
            print(c,G,-G)
        except:
            pass

We test G and -G to see if one corresponding to x==y+c


Quote
Now I only wonder, what algorithm is needed to get there?
see above...
7  Bitcoin / Development & Technical Discussion / Re: Points where x=y on secp256k1 on: July 28, 2023, 07:43:41 PM
This is wrong. You think x==y as pointy on curve.

Theo real value is y == modinv(x.n) or x == modinv(y,n)


I have found only 5 points with this. One is satoshi pubkey





Sorry i don't understand your post...and why I'm wrong
I speak about coordinate in affine plan
as Q->(x,y)

Q : (103219894018170979103981239500535823206309202530631329673674059809050911020508,103219894018170979103981239500535823206309202530631329673674059809050911020507)
or 04e43463c1a7b06b6e49f555d75238bd140690ee0f689fda75d87623e10acf95dce43463c1a7b06 b6e49f555d75238bd140690ee0f689fda75d87623e10acf95db (uncompresed pubkey)
or 03e43463c1a7b06b6e49f555d75238bd140690ee0f689fda75d87623e10acf95dc
is a perfect valid bitcoin pubkey



8  Bitcoin / Development & Technical Discussion / Re: Points where x=y on secp256k1 on: July 28, 2023, 06:54:38 PM
No there is no point in secp256k1 where x==y
but there is one where x==y+1

x=103219894018170979103981239500535823206309202530631329673674059809050911020508
y=103219894018170979103981239500535823206309202530631329673674059809050911020507

(x**3+7)%P==(y**2)%P => True
9  Other / Archival / Re: Is it possible to find out which X coordinate is -N ? on: May 17, 2023, 09:56:19 PM

Well, I'm not interested in signatures and related stuff, the entire  elliptic curve system revolves around public keys, so that is the only entry point for me to try all I got and find the best solution. "If there are no known method to correctly guess the position of any X coordinate of k, then finding a way should be a goal.

I have been studying the secp256k1 for the past 2 months, and tried at least 40-50 methods to figure out which one could be used to crack  the target k by hand, not using automated existing tools.

What actually is bothering me is a lack of a safe environment to publish study results without worrying about other people exploiting them! Though I'm in the learning phase, no breakthroughs  yet!😉

Without to be paranoiac, I think that finding a weakness on ECC such secp256k1 and stay anonymous in a "safe place" is near impossible in this hyper-connected world
After this discover, billions of dollars will be instantly at the fingertips of the researcher(s) and at the friends well informed (notice that the most probable issue is that the price of bitcoin will drop to zero).

NSA, Armed forces, governments,research consortium,mathematicians,  big tech societies,   will deploy all possible technicals and humans resources to obtain the study (and not only the legals ways  Cry). just to insure that if secp256k1 is broken or partially broken means that the others curves (like the very close secp256r1 widely used) aren't compromised too.
Today every secures communications (website certificate, https, banks,stock exchange, cryptocurrencies, army, administration... on internet  use ECC.And a lot of our economy is based on the security of the communications.
The cake is simply too big...
10  Other / Archival / Re: Is it possible to find out which X coordinate is -N ? on: May 17, 2023, 07:44:20 PM
Hi there again with more trouble and questions, I'd appreciate the time you'd spend to respond.

Is it possible to determine which X coordinate of our k is -N  or is -k inverse without obviously looking at the k ?



No there is no knowed way to guess any information of private key  (your k) with any information of public key (your X coordinate), even little.

Every actual attack (Lattice Attack etc...) oblige the attacker to know a part of the private part. and it is not an attack on the elliptic curve cryptography itself but on bad way to use signature.
 
ECC (and every asymmetric cryptography like RSA) is based on the assumption that the derivation of a private key in a public key "seems" perfectly randomly distributed.

Just for fun i tried a lot a cryptanalysis technical (statistics on huge amount of keys, pattern identification, deep learning  ...) to find a bias in the distribution of key and believe me :
secp256k1 (curve used by bitcoin) seems really safe
11  Bitcoin / Development & Technical Discussion / Re: Reused R nonce faulty signature attack on: January 10, 2023, 09:38:41 PM
it is not finished.

try your self. secp256k1 if you add abstract thinking you will see "there are another properties" that you can use.

You should observe the values as output and think what is going on and test it.

a lot of us had make thousend test to verify thousends posiibilities.

some times you must "go away" and create you own pattern , sometimes expand "calculation" for new  coeffs.

I still observe and have a good result.


no one on this forum will really share with his knowledge. TRY Harder and be positive.



🥰🥰

This attack is not applicable to Bitcoin. Because you need that the message are the same in the two signature (it not possible in the blockchain)
12  Bitcoin / Development & Technical Discussion / Re: Why do you think G/2 is so strange? on: January 04, 2023, 11:38:39 AM

I did not find any leading zero. that point is in the middle of secp256k1 subgroup.(additive inverse of middle of range point)
57896044618658097711785492504343953926418782139537452191302581570759080747168
0400000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c633f3979bf72ae8 202983dc989aec7f2ff2ed91bdd69ce02fc0700ca100e59ddf3
57896044618658097711785492504343953926418782139537452191302581570759080747169 (multiplicative inverse of 2 mod secp256k1 n)
0400000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63c0c686408d517 dfd67c2367651380d00d126e4229631fd03f8ff35eef1a61e3c
First off I have visual generator. You can set any scalar from secp256k1 range and it will generate subgroup in full correspondence to secp256k1 subgroup.
Secondly all group operation with points(addition, scalar_multiplication, subtraction, division) are isomorphic to (Zp,+,*) where we fix p as secp256k1 n.

N = 115792089237316195423570985008687907852837564279074904382605163141518161494337
lambda1 = 37718080363155996902926221483475020450927657555482586988616620542887997980018
lambda2 = 78074008874160198520644763525212887401909906723592317393988542598630163514318
    
def multiplicative_inverse(x, m):
    return pow(x, m - 2, m)
    
def additive_inverse(a):
    return N - a
    
def add(a, b): #addition
    return (a + b) % N

def sub(a, b): #subtraction
    return (a + additive_inverse(b)) % N

def mul(a, b): #multiplication
    return (a * b) % N
    
def div(a, b): #division
    return (a * multiplicative_inverse(b, N)) % N

print(div(1, 61168582499785340698020811768434254152333414806039741990912550463524917977698))
print(div(57896044618658097711785492504343953926418782139537452191302581570759080747169,
61168582499785340698020811768434254152333414806039741990912550463524917977698))

I did a mistake I don't see that your first point is just a hexadecimal representation of the point (G/2) i talked about
I though that you found a "new point" with leading zero on x that you can reprent in k.G form

Quote
Secondly all group operation with points(addition, scalar_multiplication, subtraction, division) are isomorphic to (Zp,+,*) where we fix p as secp256k1 n.

Can u explain more how you fix p as secp256k1 n ?
13  Bitcoin / Development & Technical Discussion / Re: Why do you think G/2 is so strange? on: January 04, 2023, 09:53:34 AM
Youtube: Nadia Heninger - 48ce563f89a0ed9414f5aa28ad0d96d6795f9c62

As outlined in the video, the string "8ce563f89a0ed9414f5aa28ad0d96d6795f9c6" is common to the x coordinate of G*inv2 of all secp-k1 curves. I think it is very likely that 48ce563f89a0ed9414f5aa28ad0d96d6795f9c62 (with perhaps the first and last character (4 bits) changed) was/is generated by hashing some input, and then that was used as the basis for arriving at G.

It would be interesting to know what the original input to the hash function was, and the rationale behind the changed/added bits.

Yes thanks this is an interesting video
14  Bitcoin / Development & Technical Discussion / Re: Why do you think G/2 is so strange? on: January 04, 2023, 09:27:03 AM

for example:

in subgroup generated by
0447316cb65cc8f20d539616cf65bc78479c686c3f70454cf5aab84c579b57efcd18a6a630cef25 44625d80b0297017dc9fef77712bd494fb3374974096e4dc278
that has scalar(61168582499785340698020811768434254152333414806039741990912550463524917977698) in secp256k1 subgroup

0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c 4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 G of secp256k1
will be at position(have scalar) 54229698599845083480280347574976582697435195709826937379446800456474139525780

0400000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63c0c686408d517 dfd67c2367651380d00d126e4229631fd03f8ff35eef1a61e3c
will be at position(have scalar) 27114849299922541740140173787488291348717597854913468689723400228237069762890

we can find generator point so that some point be at certain position in the subgroup.
or we can retrieve point  by generator and position.
 
and we can do so with any point from secp256k1 if we take point and its scalar. good for research only.
will not be able to break secp256k1 curve with that.


Nice generation of points!

in your
Code:
G0 = generator of secp256k1
G = 61168582499785340698020811768434254152333414806039741990912550463524917977698*G0

G = 0447316cb65cc8f20d539616cf65bc78479c686c3f70454cf5aab84c579b57efcd18a6a630cef2544625d80b0297017dc9fef77712bd494fb3374974096e4dc278
k=27114849299922541740140173787488291348717597854913468689723400228237069762890
pt0 = k.G = 0400000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63c0c686408d517dfd67c2367651380d00d126e4229631fd03f8ff35eef1a61e3c

how do you find such point with x having many leading zeros and the corresponding scalar?
I name it pt0 for convenient

do you start from it and randomly pick a scalar that point pt0/scalar = G  ?

or inversely fix a random G and randomly  generate a scalar k unless you find a point with x having sufficient leading zero?

15  Bitcoin / Development & Technical Discussion / Re: Why do you think G/2 is so strange? on: January 04, 2023, 12:09:33 AM
Quote
I don't think that x coordinates on secp256k1 are uniformly distributed.
You can actually see visually that they're not. (I know this is not over Zp, but you get the idea)


if you work in Finite Field F(P) around a half of x coordinate between 1-2^256 lie on the curve y**2=x**3 + 7 (mod P)
it's just the number of solution of sqrt_mod(x**3+7)

 and there are perfectly distributed (even we wish for) . because if not ECSDA will be have a bias and it is not good at all for a cryptographic system
16  Bitcoin / Development & Technical Discussion / Re: Why do you think G/2 is so strange? on: January 03, 2023, 10:06:48 PM
But anyway what do you think about the goal of this anomaly?
I don't know how G was chosen, but I don't think it's an anomaly or indicative of anything, really. You can find patterns or 'magic numbers' anywhere and everywhere.


I'm agree about the fact that you can find magic pattern and voodoo belief  anywhere when you speak of a chance of 1/1000 or 1/1000000 (see the Christ in the cloud, see a alien on a cigaret pack etc...)
But i'm totaly disagree when the chance is 1/100000000000000000000000000
10^26 is so big that it is totally impossible that it is due to an human misinterpretation.
it will takes millions years to a standard computer before reaching only one point with a x coordinate like this by traversing randomly the curve.

So your pretty gif is totally irrelevant

Someone : Ok Boys let's throw this coin 256 times and see the result:

0000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000001110110111100011001110010101100011111110001001101000001110110110010100000101001 1110101101010100010100010101101000011011001011011010110011110010101111110011100 01100011

Me : It's strange not?
You : you are a dreamer . it's just pure luck
17  Bitcoin / Development & Technical Discussion / Why do you think G/2 is so strange? on: January 03, 2023, 09:07:10 PM
The generator G of secp256k1 is the point
Code:
(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
or
Code:
(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424) in base10

if you divide this point by 2 with a group operation => a multiplication by the modular inverse of 2  

you obtain this point:

Code:
inv2=inverse_mod(2,N)=57896044618658097711785492504343953926418782139537452191302581570759080747169
G*inv2= (86918276961810349294276103416548851884759982251107, 87194829221142880348582938487511785107150118762739500766654458540580527283772)

a x coordinate in the range of 10^50 - 10^51 occurs only around every 10^(77-51) = 1 on 10^26  


So for me it's a proof that it is extremely unlikely that G was chosen randomly
It's not what we can called a weakness because normally every generator generate an high entropy between every scalar multiplication 1.G 2.G 3.G etc...
you can for example choose the point :
Code:
G: (1,29896722852569046015560700294576055776214335159245303116488692907525646231534)

without problem, because this "extreme" generator will be untraceable after many modulus operation

But anyway what do you think about the goal of this anomaly?
18  Bitcoin / Development & Technical Discussion / Re: Even or Odd Point on: November 17, 2022, 03:54:24 PM

here you only need to know the range where point is and find the right sequence of powers of 2 down.
This method also computationally quite hard. for example for puzzle #120 the sequence will  be around 46 values if you put lower 2^30 in bloomfilter.



Alexander, can u explain how you arrive to a sequence of 46 values of power of 2 with a bloomfilter of size 2^30 for puzzle 120?
Thanks

46  is approximately. i cannot of course know it exactly.
here is the code. you can test any secp256k1 range value.
the same will be with point operations.
p=120 # 2^120
puzzle = 1231052970201832551532555186137109517 #value to test

pows = [2**0,2**1,2**2,2**3,2**4,2**5,2**6,2**7,2**8,2**9,
        2**10,2**11,2**12,2**13,2**14,2**15,2**16,2**17,2**18,2**19,
        2**20,2**21,2**22,2**23,2**24,2**25,2**26,2**27,2**28,2**29,
        2**30,2**31,2**32,2**33,2**34,2**35,2**36,2**37,2**38,2**39,
        2**40,2**41,2**42,2**43,2**44,2**45,2**46,2**47,2**48,2**49,
        2**50,2**51,2**52,2**53,2**54,2**55,2**56,2**57,2**58,2**59,
        2**60,2**61,2**62,2**63,2**64,2**65,2**66,2**67,2**68,2**69,
        2**70,2**71,2**72,2**73,2**74,2**75,2**76,2**77,2**78,2**79,
        2**80,2**81,2**82,2**83,2**84,2**85,2**86,2**87,2**88,2**89,
        2**90,2**91,2**92,2**93,2**94,2**95,2**96,2**97,2**98,2**99,
        2**100,2**101,2**102,2**103,2**104,2**105,2**106,2**107,2**108,2**109,
        2**110,2**111,2**112,2**113,2**114,2**115,2**116,2**117,2**118,2**119,
        2**120,2**121,2**122,2**123,2**124,2**125,2**126,2**127,2**128,2**129,
        2**130,2**131,2**132,2**133,2**134,2**135,2**136,2**137,2**138,2**139,
        2**140,2**141,2**142,2**143,2**144,2**145,2**146,2**147,2**148,2**149,
        2**150,2**151,2**152,2**153,2**154,2**155,2**156,2**157,2**158,2**159,
        2**160,2**161,2**162,2**163,2**164,2**165,2**166,2**167,2**168,2**169,
        2**170,2**171,2**172,2**173,2**174,2**175,2**176,2**177,2**178,2**179,
        2**180,2**181,2**182,2**183,2**184,2**185,2**186,2**187,2**188,2**189,
        2**190,2**191,2**192,2**193,2**194,2**195,2**196,2**197,2**198,2**199,
        2**200,2**201,2**202,2**203,2**204,2**205,2**206,2**207,2**208,2**209,
        2**210,2**211,2**212,2**213,2**214,2**215,2**216,2**217,2**218,2**219,
        2**220,2**221,2**222,2**223,2**224,2**225,2**226,2**227,2**228,2**229,
        2**230,2**231,2**232,2**233,2**234,2**235,2**236,2**237,2**238,2**239,
        2**240,2**241,2**242,2**243,2**244,2**245,2**246,2**247,2**248,2**249,
        2**250,2**251,2**252,2**253,2**254,2**255,2**256]

pattern = []
p = 120
puzzle = 1231052970201832551532555186137109517
print(f'Puzzle: {puzzle}')
p = p - 1
act1 = puzzle - pows[p]
print(f'{puzzle} - {pows[p]} = {act1}')
p = p - 1
counter = 0
while p > 0:
    if act1 < pows[p]:
        p = p - 1
        continue
    else:
        counter += 1
        save = act1
        act1 -= pows[p]
        print(f'{counter}: {save} - {pows[p]} = {act1} power=[{p}]')
        pattern.append(p)
        p = p - 1
s = ''
for p in pattern:
    s += 'p' + str(p) + ','
print(s)

the actual code to achieve that i will not share. guess anyone with coding skills can do it from this explanation alone.
it will require good knowledge of combinatorics in order to try it.


Ok maybe I understand.
46 is the average length of the power of 2 sequence? that's right?
19  Bitcoin / Development & Technical Discussion / Re: Even or Odd Point on: November 17, 2022, 02:39:31 PM

here you only need to know the range where point is and find the right sequence of powers of 2 down.
This method also computationally quite hard. for example for puzzle #120 the sequence will  be around 46 values if you put lower 2^30 in bloomfilter.



Alexander, can u explain how you arrive to a sequence of 46 values of power of 2 with a bloomfilter of size 2^30 for puzzle 120?
Thanks
20  Bitcoin / Development & Technical Discussion / Re: Lattice used for finding range of nonce in transactions - academic question on: October 31, 2022, 11:10:32 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.
Pages: [1] 2 3 »
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!