Why gcd between base point and any other point will give us one or three?

digaran

copper member

Activity: 1330

Merit: 899

🖤😏

@j2002ba2, can you explain why do we get y= 0x8 when we set x= 0x7, y= 0x8 and k= lambda on secp curve? There was a raccoon around here, he couldn't satisfy me with his answer. Apology for the humor.

j2002ba2

full member

Activity: 206

Merit: 447

Because 0x1110...f784 has many small factors:
2^2 * 17 * 4289 * 6196937 * 9672199247 * 441571470858719851994038335827739586159888848835828007

While 0x1b88...e5e9 has factor 3, and then some unholy big numbers.

Your funny random mapping then produces some random integer, which is very very unlikely to have one of the big factors in the second one.

That said, what is the purpose of this exercise?

Point coordinates are not integers, they are instead infinite sets of all kind of numbers, represented by integers.

Specially y^2 = x^3 + 7 does not have integer or rational number solutions. Plugging integers makes even less sense here.

Why not use an isomorphic curve of rank>0, i.e. y^2 = x^3 - 2. Then at least you'd know that there are rational solutions, and have a single nice generator (3,5).

garlonicon

copper member

Activity: 821

Merit: 1992

First, we start from secp256k1, where we replace the real base point with (x=0x1;y=0x4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee). Then, we calculate "zero side" for the famous equation: y^2=x^3+7. Which means, we move all things to one side, which can give us: x^3-y^2+7=0. The right side is then zero, and the left side is just a huge number, which gives us zero, when we apply modulo p-value. We make sure that our left side is non-negative (so we use x^3-y^2+7 or y^2-x^3-7). Then, this left value is what we can compute for any public key we want. For convenience, we can divide it by p-value, to work with smaller numbers (because all of them are divisible by p-value, if we are working with valid points).

And then, we compare those "zero values" between different public keys, by applying gcd to both of them. If we can get only p-value out of that, we will get just "one" (because of division by p-value), which means this particular pair of points can be present only on this particular curve, or some curve with bigger p-value. However, if our gcd is bigger than one (after dividing by p-value), then it means, we can teleport those points to a different curve, with a different p-value.

So, which values can we get out of that? Well, if we start with our modified generator, we can get 0x1, 0x2, 0x4, 0x11, 0x22, 0x44, 0x10c1, 0x2182, 0x4304, and so on. However, if we use the original generator, we can get only 0x1 or 0x3. Why it is the case?

Code:

basePoint=0x1110df3be5e21e6776516a5fa6702d71d937b2614804cce0315f9575458ff784
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
modulo_root=(p+1)/4
x=2
limit=x+0x100
b_value=7
is_on_curve=False
while x    x_cube=(x*x*x)%p
    y_square=(x_cube+b_value)%p
    y=y_square.powermod(modulo_root,p)
    is_on_curve=(y.powermod(2,p)==y_square)
    if is_on_curve:
        y_negative=(p-y)
        if y_negative            y=y_negative
    if is_on_curve:
        left_side=y*y
        right_side=x*x*x+b_value
        zero_side=left_side-right_side
        if zero_side<0:
            zero_side=right_side-left_side
        zero_side=zero_side/p
        common=gcd(zero_side,basePoint)
        print(hex(x),hex(y),hex(common))
    x+=1

So, our "basePoint" for (x=0x1;y=0x4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee) is equal to 0x1110df3be5e21e6776516a5fa6702d71d937b2614804cce0315f9575458ff784 (after division by p-value). For the real generator, it is equal to 0x1b888e01a06e974017a28a5b4da436169761c9730b7aeedf75fc60f6a33cfc7792fe74711f025 d590b10e57f1b3a7ce38ffc4c885c515894b45c19c9f413e5e9. But then, after replacing that value, the code will give us only one or three. Do you have any idea, why it is the case?

Topic: Why gcd between base point and any other point will give us one or three? (Read 85 times)