README.md 4.84 KB
Newer Older
Your Name's avatar
Your Name committed
1
2
Use of the CryptoCore for Elliptic Curve Point Validation in GF(2m)

Your Name's avatar
Your Name committed
3
4
" Initial Version 0.1 "

Your Name's avatar
Your Name committed
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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:
Your Name's avatar
Your Name committed
26

Your Name's avatar
Your Name committed
27
28
29
Within this project work a Linux device driver should be extended by following ECC GF(2m)

Functions:
Your Name's avatar
Your Name committed
30

Aaisha Ghodekar's avatar
Aaisha Ghodekar committed
31
32
Preparation, Montgomery Transformation, Affine-to-Jacobi Transformation, Point Addition,
Point Doubling,  Jacobi-to-Affine Transformation,
Your Name's avatar
Your Name committed
33
34
35
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
Your Name's avatar
Your Name committed
36
37
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.

Naga Suramouli's avatar
update    
Naga Suramouli committed
38

Aaisha Ghodekar's avatar
Aaisha Ghodekar committed
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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+x*y=x^3+a2*x^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 = X2*O1
      D = Y2*O1*Z1
      E = X1+B
      F = Y1+D
      Z3 = E*Z1
      H = F*X2+Z3*Y2
      I = F+Z3
      G = Z3^2
Aaisha Ghodekar's avatar
Aaisha Ghodekar committed
69
      X3 = a2*G+F*I+E*E^S2
Aaisha Ghodekar's avatar
Aaisha Ghodekar committed
70
      Y3 = I*X3+G*H
Naga Suramouli's avatar
update    
Naga Suramouli committed
71
72
	  
	  
Your Name's avatar
Your Name committed
73

Naga Suramouli's avatar
update    
Naga Suramouli committed
74
75
76
77
78
79
80
81
82
83
84
85
86
Point Multiplication

In point multiplication a point P on the elliptic curve is multiplied with a scalar k using elliptic curve equation to
obtain another point Q on the same elliptic curve i.e. KP=Q.
Point multiplication is achieved by two basic Elliptic curve operations
• Point addition, adding two points J and K to obtain another point L i.e., L = J + K.
• Point doubling, adding a point J to itself to obtain another point L i.e. L = 2J.
Eg : k = 23 then kP = 23.P = 2(2(2(2P) + P) + P) + P.
Input: Binary representation of k and point P
k = (kn-1….k1k0)2
Output: kP


Naga Suramouli's avatar
update    
Naga Suramouli committed
87

Naga Suramouli's avatar
update    
Naga Suramouli committed
88
89
90
91
92
93
94
95
96
97
98
99
point Validation

The validation of the elliptic curve domain parameters can be simplified into two categories; validating an Elliptic Curve, and validating a Base Point.
The validation of the elliptic curve has criteria for binary Galois fields .
The coefficients of the curve, a and b, when converted to binary must have a bit-length of m bits 
 The value of b!=0

Validation of a base point
The base point, P, is not the infinity point. 
G = hP, where P = (xP , yP), and h is the cofactor.
 P = (xP , yP), and each component has bitlength equal to m.
 (xP , yP) must satisfy the associated elliptic curve equation. 
Naga Suramouli's avatar
update    
Naga Suramouli committed
100
101
102
103
 
 ![](https://mygit.th-deg.de/embedded/embedded-project-group-6/blob/master/ECC%20Over%20GF(2m)/download.png)
 ![](https://mygit.th-deg.de/embedded/embedded-project-group-6/blob/master/ECC%20Over%20GF(2m)/1_2PxXNwMceh1XC_waAP9NiA.jpeg)

Naga Suramouli's avatar
update    
Naga Suramouli committed
104

Your Name's avatar
Your Name committed
105
106
107
108
109
110
Contributors:

1)Suramouli Nagasandeep (Master)

2)Harshal Likhar

Aaisha Ghodekar's avatar
Aaisha Ghodekar committed
111
3)Aaisha Ghodekar (Developer)
Your Name's avatar
Your Name committed
112
113
114
115
116
117

4)Hamza