Regular patterns in public keys | Bitcointalksearch.org

mynonce

full member

Activity: 233

Merit: 253

Quote from: BlackHatCoiner on November 17, 2021, 03:44:34 PM

Quote from: garlonicon on November 17, 2021, 03:33:28 PM

No, it is an equivalent of a burning address, but for public keys. Nobody knows the private keys for such points, but by solving y^2=x^3+7 modulo p for some x-values and y-values, you can still reach unknown-but-technically-valid points.

So first goes for a public key that has x = 1?

Yes, for x = 1, we have 2 points (one y value is even = 02 and the other one is odd = 03 - here we have compressed public keys)
And OP is taking the point (x = 1 and the even y value) and is doubling it:
first * G = 02 0000000000000000000000000000000000000000000000000000000000000001 line 1
so we get:
2 * first * G = 03 C7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF37FFFD03 line 2

Then OP does it with the point (x = 2 and the even y value)
and so on ...

Quote from: vjudeu on May 25, 2021, 02:29:22 AM

Why for the first three points there are strange, regular patterns?

Code:

first * G = 02 0000000000000000000000000000000000000000000000000000000000000001 line 1
2 * first * G = 03 C7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF37FFFD03 line 2
second * G = 02 0000000000000000000000000000000000000000000000000000000000000002 line 3
2 * second * G = 03 33333333333333333333333333333333333333333333333333333332FFFFFF3B line 4
third * G = 02 0000000000000000000000000000000000000000000000000000000000000003 line 5
2 * third * G = 03 A7878787878787878787878787878787878787878787878787878786DFFFFD80 line 6

BlackHatCoiner

legendary

Activity: 1512

Merit: 7340

Farewell, Leo

Quote from: garlonicon on November 17, 2021, 03:33:28 PM

No, it is an equivalent of a burning address, but for public keys. Nobody knows the private keys for such points, but by solving y^2=x^3+7 modulo p for some x-values and y-values, you can still reach unknown-but-technically-valid points.

So first goes for a public key that has x = 1?

garlonicon

copper member

Activity: 821

Merit: 1992

Quote

what's first * G? Definitely not 1 * G

No, it is an equivalent of a burning address, but for public keys. Nobody knows the private keys for such points, but by solving y^2=x^3+7 modulo p for some x-values and y-values, you can still reach unknown-but-technically-valid points.

BlackHatCoiner

legendary

Activity: 1512

Merit: 7340

Farewell, Leo

Hi, as a reader who likes ECC, could I have an explanation of what's first * G? Definitely not 1 * G.

garlonicon

copper member

Activity: 821

Merit: 1992

You can also reach similar patterns for small y-values, for example here:

Code:

x*G=04 146D3B65ADD9F54CCCA28533C88E2CBC63F7443E1658783AB41F8EF97C2A10B5 0000000000000000000000000000000000000000000000000000000000000001
2*x*G=04 4362E757F94DA5D99C28EF5D5B644A97F2875E3DA5A4B8721816D7E37B73F751 7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFD82

j2002ba2

full member

Activity: 206

Merit: 447

Quote from: NotATether on May 25, 2021, 04:20:16 AM

Quote from: j2002ba2 on May 25, 2021, 03:00:33 AM

doubling in secp256k1 is equal to x/4 * (1 - 63/(x^3+7)) = x/4 * (x^3 - 56) / (x^3 + 7)

You can't use this in practical programs though because it makes a floating-point result.

There is no floating point involved, please don't introduce one. There are no floating points in secp256k1 as well, where did you get it from? It is well known how to do division mod p, if you suddenly forgot please refresh your memory. This is used in practice, and gives the correct result for all x, since this is what the group law is after simplifications.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: j2002ba2 on May 25, 2021, 03:00:33 AM

doubling in secp256k1 is equal to x/4 * (1 - 63/(x^3+7)) = x/4 * (x^3 - 56) / (x^3 + 7)

You can't use this in practical programs though because it makes a floating-point result. You'd need to multiply it by the group order, and to turn it into an integer you have to round or truncate it which will cause some bits at the end to be lost.

Example of wrong points calculated:

Code:

m = int("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16)
for i in [1, 2, 3]:
  x = int(3/4 * (i**3-56)/(i**3+7) * m)
  x = x % m
  print(hex(x))

# 0xd7fffffffffffffffffffffffffffff860192d681bb3c1667eee374ce1458786
# 0x9999999999999ffffffffffffffffffc300c96b40dd9e0b33f771ba670a2c3c3
# 0x5c3c3c3c3c3c3ffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

Notice how they are all different from vjudeu's points.

Quote from: j2002ba2 on May 25, 2021, 04:33:49 AM

There is no floating point involved, please don't introduce one. There are no floating points in secp256k1 as well, where did you get it from? It is well known how to do division mod p, if you suddenly forgot please refresh your memory. This is used in practice, and gives the correct result for all x, since this is what the group law is after simplifications.

Cripes, I did the arithmetic literally instead of as point ops. In that case I stand corrected.

j2002ba2

full member

Activity: 206

Merit: 447

TL;DR: because 1+1=2

doubling in secp256k1 is equal to x/4 * (1 - 63/(x^3+7)) = x/4 * (x^3 - 56) / (x^3 + 7)
since p is very close to 2²⁵⁶ using small number for x ensures patterns

x=1 : 1/4 * (1-56)/(1+7) = -55/32
x=2 : 2/4 * (8-56)/(8+7) = -8/5
x=3 : 3/4 * (27-56)/(27+7) = -87/136

vjudeu

copper member

Activity: 906

Merit: 2258

Why for the first three points there are strange, regular patterns?

Code:

first * G = 02 0000000000000000000000000000000000000000000000000000000000000001
2 * first * G = 03 C7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF37FFFD03
second * G = 02 0000000000000000000000000000000000000000000000000000000000000002
2 * second * G = 03 33333333333333333333333333333333333333333333333333333332FFFFFF3B
third * G = 02 0000000000000000000000000000000000000000000000000000000000000003
2 * third * G = 03 A7878787878787878787878787878787878787878787878787878786DFFFFD80

Topic: Regular patterns in public keys (Read 252 times)