Zellic - Audit Reports

Function: `_jAdd(uint256 p1, uint256 p2, uint256 p3, uint256 q1, uint256 q2, uint256 q3)`

This function takes as parameters Jacobian coordinates (p1:p2:p3) and (q1:q2:q3) of points on the elliptic curve secp256r1 and returns Jacobian coordinates representing their sum. Additionally, if a point is (0,0,0), then the other point is returned (see Finding ref↗).

Inputs

(p1, p2, p3)
(q1, q2, q3)

Validation: No checks in this function.

Impact: For each of (p1,p2,p3) and (q1,q2,q3), the caller should ensure that these are either valid Jacobian coordinates for a point on the secp256r1 curve or (0,0,0).

Correctness:

\begin{itemize} \ItemCheckboxChecked \texttt{pd} agrees with the constant \texttt{pp} defined in the library. \ItemCheckboxChecked Assuming \texttt{(p1,p2,p3)=(0,0,0)}, the function returns \texttt{(q1,q2,q3)}. \ItemCheckboxChecked Assuming \texttt{(q1,q2,q3)=(0,0,0)}, the function returns \texttt{(p1,p2,p3)}. \ItemCheckboxUnchecked Assuming \texttt{(p1:p2:p3)} and \texttt{(q1:q2:q3)} are valid Jacobian coordinates for points on the secp256r1 curve, \texttt{(r1:r2:r3) = (p1:p2:p3) + (q1:q2:q3)}. \begin{itemize} \ItemCheckboxUnchecked 1. This holds when \texttt{(p1:p2:p3)=(q1:q2:q3)} (i.e., they represent the same point on the curve). \ItemCheckboxChecked 2. This holds when \texttt{(p1:p2:p3)=-(q1:q2:q3)} (i.e., they represent additively inverse points on the curve). \ItemCheckboxChecked 3. This holds when neither conditions above are the case. \end{itemize} \ItemCheckboxChecked The return values satisfy \texttt{0 <= r1, r2, r3 < pd}, as long as the corresponding property holds for the arguments (for this check we refer also to section \ref{ModularSubtractionTrick}). \end{itemize}

Detailed steps taken to check correctness of the result: Assuming (p1:p2:p3) and (q1:q2:q3) are valid Jacobian coordinates for points on the secp256r1 curve, we compare each of the steps of the computation done in the function with the reference book, case $P_{1} \neq = \pm P_{2}$ (though we do not assume this here). Equality is here to be taken modulo pd. Here we take (p1,p2,p3) and (q1,q2,q3) to correspond to $(x_{1}, y_{1}, z_{1})$ and $(x_{2}, y_{2}, z_{2})$ in the book.

z1z2 before redefinition in the last lines is what is called

z_{1}^{2}

in the reference book.

z2z2 is what is called

z_{2}^{2}

in the reference book.

u1 is what is called

r

in the reference book.

u2 is what is called

s

in the reference book.

s1 is what is called

t

in the reference book.

s2 is what is called

u

in the reference book.

p3q3 is what is called

z_{1} + z_{2}

in the reference book.

h is what is called

v

in the reference book.

i is what is called

4 v^{2}

in the reference book.

j is what is called

4 v^{3}

in the reference book.

rr is what is called

2 w

in the reference book.

r1 after the first assignment is what is called

4 w^{2}

in the reference book.

v is what is called

4 r v^{2}

in the reference book.

j2v before redefinition in the last lines is what is called

4 v^{3} + 8 r v^{2}

in the reference book.

r1 after the last assignment is what is called

4 x_{3}

in the reference book.

s12j is what is called

8 t v^{3}

in the reference book.

r2 after the first assignment is what is called

8 (r v^{2} - x_{3}) w

in the reference book.

r2 after the last assignment is what is called

8 y_{3}

in the reference book.

z1z1 after the last assignment is what is called

z_{1}^{2} + z_{2}^{2}

in the reference book.

j2v after the last assignment is what is called

z_{1}^{2} + 2 z_{1} z_{2} + z_{2}^{2}

in the reference book.

r3 is what is called

2 z_{3}

in the reference book.

Case 1: Points are equal. In this case, the result is not correct. We will have u1=u2 and s1=s2, which implies that all variables defined afterwards are zero. See Finding ref↗.

Case 2: Points are additive inverses. For easier notation, we use notation from Washington's book. If the points are each other's additive inverse, then there must be a nonzero $c$ (mod $p$ ) so that $(x_{2}, y_{2}, z_{2}) = (c^{2} x_{1}, - c^{3} y_{1}, c z_{1})$ . Then it follows that $r = c^{2} c_{1} z_{1}^{2} = s$ and $t = c^{3} y_{1} z_{1}^{3} = - u$ , and hence $(x_{3} : y_{3} : z_{3}) = (4 u^{2} : - 8 u^{3} : 0) = ((- 2 u)^{2} \cdot 1 : (- 2 u)^{3} \cdot 1 : (- 2 u) \cdot 0) = (1 : 1 : 0)$

Case 3: Points are different and not additive inverses. Then we obtain the point $(r1:r2:r3) = (4 x_{3} : 8 y_{3} : 2 z_{3}) = (2^{2} x_{3} : 2^{3} y_{3} : 2 z_{3}) = (x_{3} : y_{3} : z_{3})$ which is the correct result according to the book.

Function: _jAdd(uint256 p1, uint256 p2, uint256 p3, uint256 q1, uint256 q2, uint256 q3)

Inputs

Function: `_jAdd(uint256 p1, uint256 p2, uint256 p3, uint256 q1, uint256 q2, uint256 q3)`