Show Posts
|
Pages: [1] 2 3 »
|
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 "|" generator | ./cuda_hasher_sha1 would be the more convenient but i don't think than it can support such a speed
|
|
|
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/Bk0NvC8VoTromp 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...: 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('')
|
|
|
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?
|
|
|
any help will be appreciated too much Could you give us the public address of your wallet?
|
|
|
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
|
|
|
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) 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: 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 Now I only wonder, what algorithm is needed to get there?
see above...
|
|
|
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
|
|
|
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
|
|
|
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 ). 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...
|
|
|
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
|
|
|
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)
|
|
|
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 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 ?
|
|
|
Youtube: Nadia Heninger - 48ce563f89a0ed9414f5aa28ad0d96d6795f9c62As 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
|
|
|
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 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?
|
|
|
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
|
|
|
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
|
|
|
The generator G of secp256k1 is the point (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8) or (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: 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 : 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?
|
|
|
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?
|
|
|
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
|
|
|
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.pdfsome 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.
|
|
|
|