Do we all agree that some questions do not have answers?

[hmbdofficial]

I mean how do we answer  this; does  anyone  knows how the half of secp256k1 generator  was created?
I was having  a text with someone  and he said no body knows the answer to that.  and I kind of think  if it was created  by someone  then  it should  definitely  have an answer.
Your inputs will be appreciated.

[stwenhao]

does  anyone  knows how the half of secp256k1 generator  was created?

No, because it was discussed for decades, and nobody shared the solution yet. For example: https://www.youtube.com/watch?v=NGLR2N4EK58

if it was created  by someone  then  it should  definitely  have an answer.

And the creator certainly knew it. But it happened in the 90s, and now, we don't even have the original source code, which was used to create secp256k1 in the first place.

Also, the generator was not so important, because it was just given as an example. Different protocols and networks could use different generators.

Edit: Let's say, that someone would really want to get the same x-value for all curves: secp160k1, secp192k1, secp224k1, and secp256k1. In that case, it could be done in a provably fair way, by just hashing something with SHA-1.

Code:

SHA-1("34")=f1f836cb4ea6efb2a0b1b99f41ad8b103eff4b59

And then, it could be used for all four curves:

Code:

magic=0xf1f836cb4ea6efb2a0b1b99f41ad8b103eff4b59

p = 0xfffffffffffffffffffffffffffffffeffffac73
K = GF(p)
a = K(0x0000000000000000000000000000000000000000)
b = K(0x0000000000000000000000000000000000000007)
E = EllipticCurve(K, (a, b))
G = E.lift_x(magic)
E.set_order(0x0100000000000000000001b8fa16dfab9aca16b6b3 * 0x1)
d = 0x1
P = d * G
print(hex(P[0]),hex(P[1]))

p = 0xfffffffffffffffffffffffffffffffffffffffeffffee37
K = GF(p)
a = K(0x000000000000000000000000000000000000000000000000)
b = K(0x000000000000000000000000000000000000000000000003)
E = EllipticCurve(K, (a, b))
G = E.lift_x(magic)
E.set_order(0xfffffffffffffffffffffffe26f2fc170f69466a74defd8d * 0x1)
d = 0x1
P = d * G
print(hex(P[0]),hex(P[1]))

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffeffffe56d
K = GF(p)
a = K(0x00000000000000000000000000000000000000000000000000000000)
b = K(0x00000000000000000000000000000000000000000000000000000005)
E = EllipticCurve(K, (a, b))
G = E.lift_x(magic)
E.set_order(0x10000000000000000000000000001dce8d2ec6184caf0a971769fb1f7 * 0x01)
d = 0x1
P = d * G
print(hex(P[0]),hex(P[1]))

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
K = GF(p)
a = K(0x0000000000000000000000000000000000000000000000000000000000000000)
b = K(0x0000000000000000000000000000000000000000000000000000000000000007)
E = EllipticCurve(K, (a, b))
G = E.lift_x(magic)
E.set_order(0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 * 0x1)
d = 0x1
P = d * G
print(hex(P[0]),hex(P[1]))

Then, we would have these generators:

Code:

0xf1f836cb4ea6efb2a0b1b99f41ad8b103eff4b59 0x600ea3a01f3440d7c72149ffeddbbf4adac6931a
0xf1f836cb4ea6efb2a0b1b99f41ad8b103eff4b59 0x1196595f80903ac2083b8e8f747610d05086f97b73290e3a
0xf1f836cb4ea6efb2a0b1b99f41ad8b103eff4b59 0x2a87d3bfa537ec6b7770dab5c2becd15e4449edc5ce462b8e904442b
0xf1f836cb4ea6efb2a0b1b99f41ad8b103eff4b59 0x570f29a9c31e5071c825fbd851ab061878145b4fb0f2152516c04ce02cf79eea

And they could even be doubled, if someone would need it:

Code:

0xe25a6430a89769deda54de0967ba803482712681                         0x6ba4a131765ea434e04302c2c9fda4f05e6333f5
0x05030d4bc376204b7cbe7aca85785c13e105c514cc0c95c6                 0x995827385f204ac0cc8b4845dce013861b644575b665b01e
0x9f0db4893b0034c5cde53b97f8120aa9d695f8f7634b0730ca360346         0x461ad56d4abf48a371e91fe67400a184b461bc338fb77a9fc578f360
0x7ef889f3aba32f49170d7ed14529d74bddc3b4dbc3dbf69fdaa53d4f0f5cfe12 0xf56185816032bf11d1f877a1a784193de2bd8b3936296c1adfd5c552ecfb2480

But for some reason, that magic value around 0x48ce563f89a0ed9414f5aa28ad0d96d6795f9c62 was used. Even one bigger value would work for all four curves:

Code:

0x48ce563f89a0ed9414f5aa28ad0d96d6795f9c63 0x4c80552a4cdff5008657529ff0099a6ee990980e
0x48ce563f89a0ed9414f5aa28ad0d96d6795f9c63 0xc20dc9960bc82d2e8fa8e6521fe5ada3d6e539569c640d8
0x48ce563f89a0ed9414f5aa28ad0d96d6795f9c63 0x7f2bb64ace5c0ce64c928e128e30fc5a67163a6fd6ba88b30224473d
0x48ce563f89a0ed9414f5aa28ad0d96d6795f9c63 0x6fa8a092e8cfbb447972a525e94bc52c9bb542a6c07fd538e1a9e071b14d7c76

So, it is now simply unknown, why exactly these values were picked. Because as you can see, many others would work fine as well, if not better.

[rdenkye]

Suppose I were a malicious curve designer, and suppose there existed some generator that enabled a backdoor. I would not choose that generator as the public standard generator.

I would choose a generator that appears ordinary and secure, while privately using the special generator for my own computations. Since generators in the same cyclic group are related by a scalar multiple, I could translate results between the hidden generator and the official one through the corresponding scalar conversion.

In other words, if a vulnerable generator exists, the official generator does not necessarily have to be that vulnerable generator. It could simply be a safe-looking representative of the same group, while the actual trapdoor relationship is used privately.

For that reason, an unclear origin of the standard generator does not automatically imply that the generator itself is unsafe. A generator-based backdoor, if such a thing were possible, would not need to be visible directly in the published generator.

[satashi_nokamato]

@rdenkye, hi.
Can you please kindly explain how could such a tricky (back-door) generator work?  A simple demonstration would suffice.
All I can think right now, I already have, you CAN NOT use a broken and also wrong key to figure out the inner pin combination of a lock.

In secp256k1, there is no such a thing as a weak generator. Whatever you go with, it would eventually mess you up when you hit a giant mountain of numbers we call N.

[rdenkye]

@rdenkye, hi.
Can you please kindly explain how could such a tricky (back-door) generator work?  A simple demonstration would suffice.
All I can think right now, I already have, you CAN NOT use a broken and also wrong key to figure out the inner pin combination of a lock.

In secp256k1, there is no such a thing as a weak generator. Whatever you go with, it would eventually mess you up when you hit a giant mountain of numbers we call N.

I didn't say that. I was trying to explain that if anyone had doubts about the election, even the doubt itself was invalid.

[mcdouglasx]

@rdenkye, hi.
Can you please kindly explain how could such a tricky (back-door) generator work?  A simple demonstration would suffice.
All I can think right now, I already have, you CAN NOT use a broken and also wrong key to figure out the inner pin combination of a lock.

In secp256k1, there is no such a thing as a weak generator. Whatever you go with, it would eventually mess you up when you hit a giant mountain of numbers we call N.

edit:

The size of N doesn't really matter because in cryptography, no, we cannot blindly trust data, and this data is not verifiable.

And this is why how G was created is important and subject to debate.

[stwenhao]

Can you please kindly explain how could such a tricky (back-door) generator work?

There is no backdoor. It is all about knowing, how things were created. Another discussion about it: https://github.com/crocs-muni/DiSSECT/issues/8

A simple demonstration would suffice.

See this topic: https://crypto.stackexchange.com/questions/60420/what-does-the-special-form-of-the-base-point-of-secp256k1-allow

Basically, if you would use G.x = SHA-256("something") then that "something" can be used in some message, if a given protocol is designed in a broken way. But as long as you simply commit to the generator, and use SHA-256("something"||G), there is no backdoor anymore, so it can be easily fixed.

Also, even today's Bitcoin blocks are not that strong, to produce SHA-256 of a header, which would be comparable to this small x-value. Which means, that in 90s, when secp256k1 was created, people definitely didn't have that much computing power. And even if that x-value would be an artifact of using SHA-1, then still: Bitcoin uses SHA-256, so it is very unlikely, that you can even attack some bad signature scheme, even if it would be created, and would not commit to the generator.

And yet another thing is that the value is changed from the initial one, to something else. If you know, that SHA-1("34") is equal to 0xf1f836cb4ea6efb2a0b1b99f41ad8b103eff4b59, but you use for example 0xf1f836cb4ea6efb2a0b1b99f41ad8b103eff4b5f, then all of your advantage is gone, because you can no longer produce a message, which would exactly hash to a proper value. And here, the initial 160-bit value was adjusted for different curves, so it is even less likely to be abused.

[hmbdofficial]

Basically, if you would use G.x = SHA-256("something") then that "something" can be used in some message, if a given protocol is designed in a broken way. But as long as you simply commit to the generator, and use SHA-256("something"||G), there is no backdoor anymore, so it can be easily fixed.

It also got me thinking if there will be risk of backdoors when deriving an elliptical curve generator point G using something like G.x =SHA 256(“some fixed string “), and if there is, how can it be possibly mitigated?

[stwenhao]

how can it be possibly mitigated?

You already have the answer to that in the linked things:

For example, I could ask you to adopt a secp256k1 pedersen commitment scheme which uses G and a new generator H = to_point(sha256("certicom rocks" || counter)). Well clearly I don't know the discrete log of some SHA2 output! ... except if G was generated as H*random-- then I do and I can break the soundness of the commitment scheme.

Obviously, I don't think there was any funny business like this here, for one-- "2" is a pretty non-random 'key'. And any vaguely competent effort to create H would commit to G, e.g. H = to_point(sha256(to_bits(G) || "certicom rocks" || counter).

So, again: if you use SHA-256("something") alone, then it could be unsafe. But if it would be SHA-256("something"||G), then it no longer matters, which generator would be there, as long as it would be constant. And the practically used value in secp256k1 has 166 bits, so it is too long for SHA-1, and too short for SHA-256, so it is extremely unlikely, that someone knows anything, where SHA-256 of that would be equal to exactly 0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63. As I said, even today's miners cannot reach it that easily, and even if they could, then endianness would break it. In 90s, nobody had that much computing power, to generate such low hash. And if it was generated from SHA-1, RIPEMD-160, or anything else, then it doesn't matter, because Bitcoin uses SHA-256.

[rdenkye]

If any generator is unsafe, then no generator is safe. This is a mathematical and concrete fact. Therefore, discussing generator selection is entirely due to a lack of sufficient information.

[stwenhao]

If any generator is unsafe, then no generator is safe.

Of course. But it doesn't change the fact, that it was picked in an unknown way. And the question was: "are there any questions with unknown answers", which are just cases like that. It is more about curiosity, related to the exact generation procedure, than to any weakness.