Mathematical doubts

[sonmat]

Hello, given that I am neither a computer scientist nor a mathematician, but reading the text it seems to me that there is a bit of confusion regarding the definition of the sum and product operations defined on the elliptic curve. Some things in the text are not very clear to me. For example: "I realized that G + G is not 2 * G in this SunEC implementation". What do you mean by 2 * G? This is classical multiplication or "strange" multiplication?

I would like to understand the java code and do some experiments, but having never used this language I waste some time understanding the syntax and how it is structured (I'm learning about classes, objects, etc..). However, I think I have understood mathematical theory of elliptic curves quite well. I would like to understand the code to see if it matches the theory and try to do some tests.

Thanks for your hard work.

[jojo2234]

2*G is 2 the private key that multiply a point on the elliptic curve, as I have understood, reading internet articles, it should be G+G. However my tests say that it's not.
You can try it yourself on a simple curve like this used in this example: https://www.youtube.com/watch?v=NTztut15D2E
Or you can try with the curve prime256v1 already implemented. For example take H be 3*G, where 3 is the private key without 0 in front of the array, I mean the private key it's an array of one byte only. You can use the function: sumPoints_prime256v1(G,H) to do G+H that should be 3*G and you will get a point Q then you can change privArr and set it as one byte (3) and the result from:

Point pub = ops.multiply(affGen, privArr);
AffinePoint affPub = pub.asAffine();

will be a different point.
The code that makes the multiplication is in the class called ECOperations from line 173 to 182.
Hope it can be helpful.

[sonmat]

Where do I find the "sumPoints_prime256v1" function?

Given priv=3, and pub=H=3G
If i calculate the sum G+H = G + 3G = 4*G
I should calculate Q = ops.multiply(G,4), not with privArr=3
Am i wrong? Did I misunderstand your words?

If I understand the math behind it correctly, the multiplication operation between a scalar and a point is not defined in the classical sense. In the classical sense, if I multiply a vector of the plane by a scalar I have to multiply both components of the vector by the same scalar. In this case the multiplication operation is defined starting from the addition operation, for example: 3H = H+H+H. In general nH=H+H... n times.
Okay multiplication is just a repeated sum, but how is the sum defined?
The sum of two points belonging to the curve is defined with the formulas you reported in "rules for point addition".
I cannot understand within the code where the function that adds two points is implemented, and how the "multiply" function is implemented. I would expect the multiply function to call the sum function "n times".

[sonmat]

I think I understand why I don't find what I expected in the code. The multiplication algorithm is not "add n times" but a variant is used to reduce the computational cost. There are several alternative multiplication algorithms:
https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

My initial idea for finding the private key was to simply add a "counter" variable within the multiplication loop. The number of iterations should match the private key. Maybe it can work when n is "small" enough. The cost of this operation should grow exponentially with n. It also seems strange to me that no one has thought of it yet given the simplicity of the idea.
I would like to try to implement the "standard" multiplication function with a counter inside to actually understand how the calculator behaves when n varies.

Thanks again

[sonmat]

Hi, re-reading the readme I think there is an error where you define the sum of two points, the line:
If p1 == p2 Than S=((b⋅x1²)+a)/(a⋅y1) mod p => S=((((b⋅x1²)+a) mod p)⋅((a⋅y1) invmod p)) mod p
should be?:
If p1 == p2 Than S=((3⋅x1²)+a)/(2⋅y1) mod p => S=((((3⋅x1²)+a) mod p)⋅((2⋅y1) invmod p)) mod p

[jojo2234]

This could explain why doesn't work, but why is 3 instead of b? And 2 instead of a? Consider that a and b are coefficients of the curve. y²=x³+ax+b

[sonmat]

Hi,
S is really the Slope of the line tangent to each point of the curve...
If you take the equation of the curve you can rewrite it as:
X^3+ax+b-y^2=0 => F(x,y)=0
F is a function that you can display in 3 dimensions: 2 for the domain (x, y) and "a height" for the image of the function F. The curve is then defined by imposing F = 0, this is equivalent to sectioning F with a horizontal plane at zero height. From this section we get the curve.
Now we want to write the equation of the tangent line to each point of the curve implicitly defined by F = 0.
The equation is:
F_x (x-x1)+F_y (y-y1) = 0 => (y-y1) = -F_x/F_y (x-x1)
So the slope of this line is -F_x/F_y
(https://en.wikipedia.org/wiki/Implicit_curve)
F_x and F_y are the partial derivative of F.

In our case F = X^3+ax+b-y^2
Taking the partial derivatives and calculating them in (x1,y1):
F_x=3x1^2+a
F_y=2y1
S=-(3x1^2+a)/(2y1)

Of course this is not meant to be a rigorous treatment that I would not even be able to do, but hope it helps to understand

[jojo2234]

Ciao,

Thank you, it's really helpful, I didn't have fully understand what was S yet.
Just to clarify with x1 I mean the x coordinate of the point one (1) it's not the derivate for me.
The function sumPoints_prime256v1 is on line 277 of HumanMethod.java

My initial idea for finding the private key was to simply add a "counter" variable within the multiplication loop. The number of iterations should match the private key. Maybe it can work when n is "small" enough. The cost of this operation should grow exponentially with n. It also seems strange to me that no one has thought of it yet given the simplicity of the idea.
I would like to try to implement the "standard" multiplication function with a counter inside to actually understand how the calculator behaves when n varies.

I dare to suggest you this article where maybe you can find out why the iteration method of a counter could fail.

[sonmat]

Hi
Also for me x1 is the x coordinate of the first point. The derivatives are calculated here, in (x1, y1). Obtaining S which is the slope of the line tangent to the curve at the point (x1, y1).

This video explains very well, in my opinion, what it means graphically to add two points in this way:
https://www.youtube.com/watch?v=muIv8I6v1aE

I have implemented a matlab/octave script which multiplies a scalar by a point on the curve. I tested it by trying to perform the same calculations that are performed manually in the video you posted earlier. I got the same results as your video so it should work.
I have edited and corrected this script:
https://it.mathworks.com/matlabcentral/fileexchange/73364-secp256k1-elliptic-curve-shared-key-generation-gui
The "for" loop inside the secp256k1 function it's exactly the implementation of the "doubling and add" algorithm:
https://www.youtube.com/watch?v=u1VRbo_fhC8
This allowed me to understand doubling and add algorithm (It's just the multiplication performed with the private key expressed in binary base...). This speeds up calculations a lot, but you can perform it since you know the private key as you wrote in your article.

The doubling and add algorithm can suffer from side channel vulnerabilities, so from what I understand, the standard is to use other algorithms to perform the multiplication numerically.
In your java code the multiplication is done via another algorithm, it looks something like a sliding window (see https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication). I haven't analyzed it well yet..

I have so many ideas to test in order to find the private key, but I'm pretty sure none of them could work as I'm not a mathematician and surely someone would have thought of that before me XD.
But at least, I'm happy to understand what the problems are ..

[WKNONV]

If that can help to better understand
https://ijireeice.com/upload/2015/april-15/IJIREEICE%2028.pdf

[jojo2234]

@WKNONV that is interesting I had alredy found it years ago but I wasn't able to find it again, thank you for sharing it.

@sonmat you are right, I should correct my code as soon as possible.
If I can suggest a test, I suspect that could exist some vulnerabilities in "limbs" I mean that numbers generated while processing the public key. I think it's interesting that an array of five zeros for example is different from an array of 2 zero. You'll get two different public key with the same big integer number 0.
Anyway I still didn't find the time to make my own tests.

[sonmat]

Hello

I don't understand what you mean with:
"I suspect that could exist some vulnerabilities in "limbs" I mean that numbers generated while processing the public key."

Regarding:
" I think it's interesting that an array of five zeros for example is different from an array of 2 zero. You'll get two different public key with the same big integer number 0.", in theory if your private key is d=0 the result of the multiplication P=d*G is zero. For example see the definition in the algorithm "double and add": https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication.

f(P, d) is
if d = 0 then
return 0 # computation complete
.....
if the algorithm is implemented correctly, you should get this result. An array of five zeros or an array of 3 zeros should be always the "zero element" of the algebraic system..

Unfortunately I don't have much time to dedicate and there are many things to study and deepen.
These are a playlist and sample video that I find interesting. They are just a basic introduction to some of the necessary tools .. :

Abstract algebra intro
https://www.youtube.com/watch?v=IP7nW_hKB7I&list=PLi01XoE8jYoi3SgnnGorR_XOW3IcK-TP6
Modular arithmetic examples:
https://www.youtube.com/watch?v=lJ3CD9M3nEQ

I find the properties of modular arithmetic interesting for example in proving divisibility criteria:
https://en.wikipedia.org/wiki/Divisibility_rule

Maybe there is a "divisibility criterion" for the public key P. A criterion that given P represented in binary basis, for example,it tells me by which d is divisible according to the definition of "multiplication on the elliptic curve (P = d * G) ".
....The problem is that in this case P is a point on the plane, d is an integer and the "multiplication" function is defined as "non-invertible" .. it is difficult to speak of "divisibility criteria" ..
Bhooo XD

[jojo2234]

This provider for ECC, SunEC, give different results with number that should be the same. Let me explain. Take as example that the private key you want to use is 23.
Now, in Italian if you say 023 or 00023 the number is still 23, because the zero is useless but in this implementation 0 is considered. So if you use 23, you obtain a public key that is different from that generated with 000000023.

[sonmat]

Hello,
About the function "multply" defined in "ECOperations.java", line 139: in this case the private key is the vector "s".
From what I seem to have understood "s" must be a vector of size 256, which represents the binary value of the private key.
If you want to compute the public key using "23" as the private key, i.e. P = 23 * G, you should translate "23" into its 256-bit binary representation and call the "multiply" function with this array "s".
I'm not sure if that was actually your doubt.

I have not yet understood which algorithm is implemented for the calculation in the "multiply" function. It looks like a kind of sliding window:
for(int i = s.length - 1; i >= 0; --i) {
this.double4(result, t0, t1, t2, t3, t4);
int high = (255 & s[i]) >>> 4; //In my opinion max value here is 15 and minimum is 0
this.lookup4(pointMultiples, high, lookupResult, zero);
this.setSum(result, lookupResult, t0, t1, t2, t3, t4);
this.double4(result, t0, t1, t2, t3, t4);
int low = 15 & s[i]; //In my opinion max value here is 15 and minimum is 0
this.lookup4(pointMultiples, low, lookupResult, zero);
this.setSum(result, lookupResult, t0, t1, t2, t3, t4);
}