Why do you think G/2 is so strange? | Bitcointalksearch.org

garlonicon

copper member

Activity: 821

Merit: 1992

I think this hash has more than 160 bits. It has at least 192 bits, but could be also 256-bit. The reason is that in the generation procedure, it is first assigned to "e", but then assigned to "t" as modulo "2*q", and next assigned to "u" as modulo "q". So, it can be reduced to just modulo "q".

Code:

u1= 48ce563f89a0ed9414f5aa28ad0d96d6795f9c62 (160-bit)
u2=0554123b78ce563f89a0ed9414f5aa28ad0d96d6795f9c66 (192-bit)
u3= 3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 (224-bit)
u4= 3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 (256-bit)

So, I think there is some hash from at least 192-bit function (more probably 256-bit function, and we can see only a part of that), so we start from "u2". Then, for different elliptic curves, we have different "q". For secp160k1, it is probably correct, so that x-value has almost 160 bits. For secp192k1 it also seems to be correct, and that's why we can see that our hash has more than 160 bits. Then, for secp224k1 and secp256k1, it seems that "q" is lower than it should be, for example it could be some weird 168-bit value (so the first mistake would be to pick 160-bit instead of 224-bit and 256-bit, and the second mistake could be some off-by-one error that makes it 168-bit instead of 160-bit).

o_e_l_e_o

legendary

Activity: 2268

Merit: 18748

Quote from: garlonicon on January 07, 2023, 06:04:19 AM

Also, there is no reason to double that point if h=1. It is needed in other curves, where h>1.

Sure, but if you are defining the parameters for the four secp-k1 curve simultaneously, then doubling a set value on each curve is a much more straightforward way of arriving at a G which has a 50% chance of being 160/192/224/256 bits, rather than multiple hashes and combining different lengths of your two hash outputs in to one number.

Although looking more closely, the generator point for secp160k1 actually only has an x coordinate of 158 bits. So my guess above doesn't really make sense in that context.

garlonicon

copper member

Activity: 821

Merit: 1992

Quote

I wonder if the 166 bit point was doubled simply so G is 256 bits. I can already imagine all the questions about "Why is G so small?" and "Is G insecure because it is only 166 bits?" that we would see otherwise.

That could be easily avoided by running some hash function twice. If you assume that you only have 160-bit hash function, and you need some 256-bit number, then you can just take first 128 bits of your hash, and run it twice.

Code:

SHA-1("hi")=c22b5f9178342609428d6f51b2c5af4c0bde6a42
SHA-1("lo")=638e8f0171575864326f06d2a5f8e72287427b15
mask=0xffffffffffffffffffffffffffffffff00000000
x=c22b5f9178342609428d6f51b2c5af4c638e8f0171575864326f06d2a5f8e722
R=04 C22B5F9178342609428D6F51B2C5AF4C638E8F0171575864326F06D2A5F8E723 FE1CA1AC052AE7B4DAEE3D88C52CF44DB3E5A0687830F4784E1B6A55C29567A0
G=2*R
G=048F14EB7D5C44E5E28E499C24EA81F00AA269E20DBFB95D8C7D289F4E071D6FF3AA34599BE5A67F3B264B311AF0739FC582D0A2F5C343D661907CF9F885C2AE8E

Also, there is no reason to double that point if h=1. It is needed in other curves, where h>1.

o_e_l_e_o

legendary

Activity: 2268

Merit: 18748

Quote from: garlonicon on January 04, 2023, 10:39:47 AM

First, start with some drafts, like this one: https://secg.org/sec1-v1.99.dif.pdf

There's an email from Dan Brown you can read here, which might interest you if you've not seen it already: https://bitcointalksearch.org/topic/m.3183975. In terms of the generator point, he also says it is "something I cannot explain".

I wonder if the 166 bit point was doubled simply so G is 256 bits. I can already imagine all the questions about "Why is G so small?" and "Is G insecure because it is only 166 bits?" that we would see otherwise.

garlonicon

copper member

Activity: 821

Merit: 1992

Quote

There is no anomaly, since in secp256k1 all points (except the one at infinity) are equal. No point is more equal than others.

Note that the base point was altered many times, to go from 160-bit x value, to some 166-bit x value.
Because this point could be a base point as well:

Code:

x=00000000000000000000000048CE563F89A0ED9414F5AA28AD0D96D6795F9C63
R=04 00000000000000000000000048CE563F89A0ED9414F5AA28AD0D96D6795F9C63 6FA8A092E8CFBB447972A525E94BC52C9BB542A6C07FD538E1A9E071B14D7C76
G=2*R
G=04 EEC87BD41958CF6BC868D995DD82E9E9DFBB28046C3CAEFE9E0DFCC2EBE7DC04 B007C483375518ECCA86E303B1B80726CF43362F6CAA038C49221FA7B1E26F53

Also, if someone wanted to quickly test ECDSA, and for example SHA-1, it could be done in this way:

Code:

SHA-1("")=da39a3ee5e6b4b0d3255bfef95601890afd80709
x=000000000000000000000000DA39A3EE5E6B4B0D3255BFEF95601890AFD8070B
R=04 000000000000000000000000DA39A3EE5E6B4B0D3255BFEF95601890AFD8070B 95702D3C6298E525B4474EC3AA16C1402892B7E6D4777EDB2D31F4F706242550
G=2*R
G=04 4B26F1535CB783ED23A34628E66A99ED8A971F588217D4FBD7CAB60D2C8C89A6 1B8874D16B70F9EBBB4031BE40D08F868D634903659BC8FBA779460D5133EC78

So, the reason why that generator was created more than twice on average seems to be strange, if you assume that points are "equal" in a sense that if one of them is weak, then all of them are.

j2002ba2

full member

Activity: 206

Merit: 447

Quote from: CrunchyF on January 03, 2023, 04:07:10 PM

But anyway what do you think about the goal of this anomaly?

There is no anomaly, since in secp256k1 all points (except the one at infinity) are equal. No point is more equal than others.

It seems as an easy way to check if your implementation is mostly correct - you try multiplying by 1/2, and then receive small x coordinate. Many things have to be implemented accurately, and any deviation would show up.

garlonicon

copper member

Activity: 821

Merit: 1992

First, start with some drafts, like this one: https://secg.org/sec1-v1.99.dif.pdf
Then, go to "3.1.3.2 Point Selection". You can CTRL+F the word "seed", and try to find places, where that seed is hashed.

Code:

A="Base point"
A=4261736520706f696e74
B=01
C=01
H=Hash(A||B||C||S)=Hash(4261736520706f696e740101||S)
e=H
t=e%(2*q)
u=t%q
z=t/q
u=00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63
x=00000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C63
y=C0C686408D517DFD67C2367651380D00D126E4229631FD03F8FF35EEF1A61E3C
G=hR
h=2
G=2*(0400000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C63C0C686408D517DFD67C2367651380D00D126E4229631FD03F8FF35EEF1A61E3C)
G=0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

We can guess that there was another elliptic curve, with h=2 (and for that reason the point is doubled), and there was probably some 160-bit seed S, used to derive it. Guessing the seed is extremely hard, but it is possible to be lucky, and to check seeds for existing curves, trying to find some match.

Also, because many times errors are grouped, you can try to look at places, where something was generated in another way than it should be. For example, open: https://secg.org/SEC2-Ver-1.0.pdf

There, you can find "3.4.2 Recommended Parameters sect163r1", where you have an information, that something was generated in a slightly different way.

Quote

However for historical reasons the method used to generate E from S differs slightly from the method described in ANSI X9.62 [1]. Specifically the coefficient b produced from S is the reverse of the coefficient that would have been produced by the method described in ANSI X9.62.

So, you can try seed "S=24B7B137 C8A14D69 6E676875 6151756F D0DA2E5C" and generate some hashes. Another thing is that we can guess SHA-1 was used, but it could be RIPEMD-160 or any other 160-bit hash function as well. Or, the endianness could be swapped, or things like that could happen in the middle.

ABCbits

legendary

Activity: 2870

Merit: 7490

Crypto Swap Exchange

Quote from: n0nce on January 03, 2023, 04:42:16 PM

Quote from: CrunchyF on January 03, 2023, 04:07:10 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.

This is naive assumption. Knowing parameter of secp256r1[1] is chosen by NSA and cryptography security could be reduced on specific parameter (such as e=3 on RSA[2]), OP concern is valid.

[1] https://it.slashdot.org/story/13/09/11/1224252/are-the-nist-standard-elliptic-curves-back-doored
[2] https://security.stackexchange.com/a/2339

CrunchyF

jr. member

Activity: 56

Merit: 26

Quote from: ?? on ??

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 ?

CrunchyF

jr. member

Activity: 56

Merit: 26

Quote from: o_e_l_e_o on January 04, 2023, 04:49:04 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

o_e_l_e_o

legendary

Activity: 2268

Merit: 18748

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.

CrunchyF

jr. member

Activity: 56

Merit: 26

Quote from: ?? on ??

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?

tromp

legendary

Activity: 990

Merit: 1108

Quote from: n0nce on January 03, 2023, 06:04:52 PM

It's alluding to the fact that you arbitrarily chose to divide G by 2.

It feels like you're trolling. There is almost nothing arbitrary about 1/2; it's the simplest fraction.
I also find it intriguing that the x-coordinate of 1/2 * G, while large in absolute terms,
is so relatively minute. If the people responsible for picking G ever come forward to
explain their choice, I'm sure it will explain the 1 in 10^26 odds that this property
would hold at random.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: n0nce on January 03, 2023, 04:42:16 PM

Quote from: CrunchyF on January 03, 2023, 04:07:10 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.

Bruh, thats Walt Disney's signature. 666 is an ancient conspiracy theory.

Quote from: CrunchyF on January 03, 2023, 05:06:48 PM

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

You need to do this thousands of times to get sufficiently random entropy.

Alternatively, you can use Von Neumann's device where you simply generate 2x amount of bits you need, and then interpret "01" sequences as 0, and "10" sequences as 1, or vice versa (and discard 00 and 11 sequences). If you run out of 2-bit pairs, just generate some more.

ymgve2

full member

Activity: 161

Merit: 230

all secp k curves share almost the same value when divided by 2: https://bitcoin.stackexchange.com/questions/113116/how-is-the-generator-point-g-chosen-in-the-secp256k1-curve-used-in-bitcoin

CrunchyF

jr. member

Activity: 56

Merit: 26

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 Z_p, 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

n0nce

hero member

Activity: 882

Merit: 5834

not your keys, not your coins!

Quote from: CrunchyF on January 03, 2023, 05:06:48 PM

So your pretty gif is totally irrelevant

It's alluding to the fact that you arbitrarily chose to divide G by 2. You can probably find a divisor for any other point whose result has some kind of pattern. Or maybe multiply the point by a scalar. Maybe the 'pattern' is not being in a specifically small range, but having a repeating number at the start in some representation like hex or octal or whatever may fit.

Also how do you get to this number?

Quote from: CrunchyF on January 03, 2023, 04:07:10 PM

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

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 Z_p, but you get the idea)

CrunchyF

jr. member

Activity: 56

Merit: 26

Quote from: n0nce on January 03, 2023, 04:42:16 PM

Quote from: CrunchyF on January 03, 2023, 04:07:10 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

n0nce

hero member

Activity: 882

Merit: 5834

not your keys, not your coins!

Quote from: CrunchyF on January 03, 2023, 04:07:10 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.

CrunchyF

jr. member

Activity: 56

Merit: 26

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?

Topic: Why do you think G/2 is so strange? (Read 369 times)