Use of the CryptoCore for Elliptic Curve Point Validation in GF(2m)

" Initial Version 0.1 "

Elliptic Curve Cryptography (ECC) defines asymmetric cryptographic systems, which perform operations on elliptic curves over finite fields. Such methods are secure only if discrete logarithms in the group of points of the elliptic curve cannot be efficiently calculated. The computation on elliptic curves is done by the operations Point Addition, Point Doubling and Point Multiplication in which the latter is based on a sequence of Point Doublings and Point Additions.

For the overall security of ECC cryptographic systems, the evaluation whether a received or calculated Point indeed is a valid Point on the given elliptic curve, is essential. In the past this validation step quite often simply has been omitted, partly due to efficiency reasons, which created a potential attack vector.

During Point Validation first it has to be evaluated for a given Point Q that the Point is not equal to the Point at Infinity (Q , O). Furthermore it has the be evaluated that the coordinates of the Point xQ, yQ are indeed elements of GF(2m). In addition it will be evaluated if its coordinates inserted into the equation of the elliptic curve (E : y2+x·y = x3+a·x2+b mod n(x)) produces a valid result. In a last test, it will be evaluated if the Point Multiplication [n]Q = O, with n being the order of the generator Point. If any of this tests fails, the Point will not be accepted. By nature, due to uniqueness reasons the validation must be performed in affine coordinate representation of the Point.

Goal:

Within this project work a Linux device driver should be extended by following ECC GF(2m)

Functions:

Preparation, Montgomery Transformation, Affine-to-Jacobi Transformation, Point Addition, Point Doubling, Jacobi-to-Affine Transformation, Montgomery Back-transformation, Point Validation. By using a Linux User Space Application the correct functionality should be verified by performing Point Validations in GF(2m) for the supported ECC precision widths. Based on a given Point and elliptic curve equation a statement must be made whether the Point is on the curve or not.For the validation of the calculation inside of the CryptoCore the open-source mathematics software SageMath should be used.In order to be able to illustrate the time required for ECC Point Validation with different precision widths the Real Time Library support (-lrt) should be included.

Point Addition:

With 2 distinct points, P and Q, addition is defined as the negation of the point resulting from the intersection of the curve, E, and the straight line defined by the points P and Q, giving the point, R. P+Q=R (x1,y1)+(x2,y2)=(x3,y3)

An elliptic curve in short Weierstrass form has parameters a2 a6 and coordinates x y satisfying the following equations: y^2+xy=x^3+a2x^2+a6

Affine addition formulas: (x1,y1)+(x2,y2)=(x3,y3) where x3 = ((y1+y2)/(x1+x2))^2+((y1+y2)/(x1+x2))+x1+x2+a2 y3 = ((y1+y2)/(x1+x2))^3+(x2+a2+1)*((y1+y2)/(x1+x2))+x1+x2+a2+y1

Jacobian coordinates represent x y as X Y Z satisfying the following equations:

x=X/Z^2 y=Y/Z^3

Assumptions: Z2=1. Explicit formulas: O1 = Z1^2 B = X2O1 D = Y2O1Z1 E = X1+B F = Y1+D Z3 = EZ1 H = FX2+Z3Y2 I = F+Z3 G = Z3^2 X3 = a2G+FI+EE^S2 Y3 = IX3+G*H

Contributors:

1)Suramouli Nagasandeep (Master)

2)Harshal Likhar

3)Aaisha Ghodekar (Developer)

4)Hamza