1、椭圆曲线密码简明教程1Online Elliptic Curve Cryptography Tutorial椭圆曲线密码简明教程1.0 Introduction2.0 Elliptic Curve Groups Over Real Numbers2.1 Elliptic Curve Addition: A Geometric Approach2.1.1 Adding distinct points P and Q2.1.2 Adding the points P and -P2.1.3 Doubling the point P2.1.4 Doubling P if y P = 02.2 Ell
2、iptic Curve Addition: An Algebraic Approach2.2.1 Adding distinct points P and Q2.2.2 Doubling the point P2.3 Experiment: An Elliptic Curve Model (real numbers)2.4 Quiz 1 Elliptic curve groups over real numbers3.0 Elliptic Curve Groups Over Fp3.1 An Example of an Elliptic Curve Group over Fp3.2 Arith
3、metic in an Elliptic Curve Group over Fp3.2.1 Adding distinct points P and Q3.2.2 Doubling the point P3.3 Experiment: An Elliptic Curve Model (over Fp)3.4 Quiz 2 Elliptic curve groups over Fp4.0 Elliptic Curve Groups Over F 2m4.1 An Example of an Elliptic Curve Group over F2m4.2 Arithmetic in an Ell
4、iptic Curve Group over F2m4.2.1 Adding the distinct points P and Q4.2.2 Doubling the point P4.3 Experiment: An Elliptic Curve Model (over F2m )4.4 Quiz 3 Elliptic curve groups over F 2m5.0 EC Groups and the Discrete Log Problem5.1 Scalar Multiplication5.2 The Elliptic Curve Discrete Logarithm Proble
5、m5.3 An Example of the Elliptic Curve Discrete Logarithm Problem5.3.1 An ECDLP Solution1.0 IntroductionWelcome to the Elliptic Curve Cryptosystem Classroom. This site provides an intuitive introduction to Elliptic Curves and how they are used to create a secure and powerful cryptosystem. The first t
6、hree sections introduce and explain the properties of elliptic curves. A background understanding of abstract algebra is required, much of which can be found in the Background Algebra section. The next section describes the factor that makes elliptic curve groups suitable for a cryptosystem though t
7、he introduction of the Elliptic Curve Discrete Logarithm Problem (ECDLP). The last section brings the theory together and explains how elliptic curves and the ECDLP are applied in an encryption scheme. This classroom requires a JAVA enabled browser for the interactive elliptic curve experiments and
8、animated examples. Elliptic curves as algebraic/geometric entities have been studied extensively for the past 150 years, and from these studies has emerged a rich and deep theory. Elliptic curve systems as applied to cryptography were first proposed in 1985 independently by Neal Koblitz from the Uni
9、versity of Washington, and Victor Miller, who was then at IBM, Yorktown Heights. Many cryptosystems often require the use of algebraic groups. Elliptic curves may be used to form elliptic curve groups. A group is a set of elements with custom-defined arithmetic operations on those elements. For elli
10、ptic curve groups, these specific operations are defined geometrically. By introducing more stringent properties to the elements of a group, such as limiting the number of points on such a curve, creates an underlying field for an elliptic curve group. In this classroom, elliptic curves are first ex
11、amined over real numbers in order to illustrate the geometrical properties of elliptic curve groups. Thereafter, elliptic curves groups are examined with the underlying fields of Fp (where p is a prime) and F2m (a binary representation with 2m elements). 2.0 Elliptic Curve Groups over Real NumbersAn
12、 elliptic curve over real numbers may be defined as the set of points (x,y) which satisfy an elliptic curve equation of the form: y2 = x3 + ax + b, where x, y, a and b are real numbers. Each choice of the numbers a and b yields a different elliptic curve. For example, a = -4 and b = 0.67 gives the e
13、lliptic curve with equation y2 = x3 - 4x + 0.67; the graph of this curve is shown below: If x3 + ax + b contains no repeated factors, or equivalently if 4a3 + 27b2 is not 0, then the elliptic curve y2 = x3 + ax + b can be used to form a group. An elliptic curve group over real numbers consists of th
14、e points on the corresponding elliptic curve, together with a special point O called the point at infinity. P + Q = R is the additive property defined geometrically. 2.1 Elliptic Curve Addition: A Geometric ApproachElliptic curve groups are additive groups; that is, their basic function is addition.
15、 The addition of two points in an elliptic curve is defined geometrically. The negative of a point P = (xP,yP) is its reflection in the x-axis: the point -P is (xP,-yP). Notice that for each point P on an elliptic curve, the point -P is also on the curve. 2.1.1Adding distinct points P and Q Suppose
16、that P and Q are two distinct points on an elliptic curve, and the P is not -Q. To add the points P and Q, a line is drawn through the two points. This line will intersect the elliptic curve in exactly one more point, call -R. The point -R is reflected in the x-axis to the point R. The law for addit
17、ion in an elliptic curve group is P + Q = R. For example: 2.1.2 Adding the points P and -PThe line through P and -P is a vertical line which does not intersect the elliptic curve at a third point; thus the points P and -P cannot be added as previously. It is for this reason that the elliptic curve g
18、roup includes the point at infinity O. By definition, P + (-P) = O. As a result of this equation, P + O = P in the elliptic curve group . O is called the additive identity of the elliptic curve group; all elliptic curves have an additive identity. 2.1.3 Doubling the point PTo add a point P to itself
19、, a tangent line to the curve is drawn at the point P. If yP is not 0, then the tangent line intersects the elliptic curve at exactly one other point, -R. -R is reflected in the x-axis to R. This operation is called doubling the point P; the law for doubling a point on an elliptic curve group is def
20、ined by: P + P = 2P = R. The tangent from P is always vertical if yP = 0.2.1.4 Doubling the point P if yP = 0If a point P is such that yP = 0, then the tangent line to the elliptic curve at P is vertical and does not intersect the elliptic curve at any other point. By definition, 2P = O for such a p
21、oint P. If one wanted to find 3P in this situation, one can add 2P + P. This becomes P + O = P Thus 3P = P. 3P = P, 4P = O, 5P = P, 6P = O, 7P = P, etc. 2.2 Elliptic Curve Addition: An Algebraic ApproachAlthough the previous geometric descriptions of elliptic curves provides an excellent method of i
22、llustrating elliptic curve arithmetic, it is not a practical way to implement arithmetic computations. Algebraic formulae are constructed to efficiently compute the geometric arithmetic. 2.2.1 Adding distinct points P and QWhen P = (xP,yP) and Q = (xQ,yQ) are not negative of each other, P + Q = R wh
23、ere s = (yP - yQ) / (xP - xQ) xR = s2 - xP - xQ and yR = -yP + s(xP - xR) Note that s is the slope of the line through P and Q. 2.2.2 Doubling the point P When yP is not 0, 2P = R where s = (3xP2 + a) / (2yP ) xR = s2 - 2xP and yR = -yP + s(xP - xR) Recall that a is one of the parameters chosen with
24、 the elliptic curve and that s is the tangent on the point P. 2.3 Experiment: An Elliptic Curve Model over Real NumbersThe following model can be used to experiment with addition in a variety of elliptic curve groups. Geometric Elliptic Curve Model. ( A javascript applet that opens in a separate win
25、dow)Try the following experiments: 1. Change the variables a and b to see the resulting shape and the elliptic curve. 2. Select a point P on the curve, and then select a point Q on the curve. Add them together. 3. Select a point P on the curve and then double it. 4. Try selecting a = -3 and b = 2 2.
26、4 QUIZ 1Elliptic Curve Groups over real numbers 1. Does the elliptic curve equation y2 = x3 - 7x - 6 over real numbers define a group? 2. What is the additive identity of regular integers? 3. Is (4,7) a point on the elliptic curve y2 = x3 - 5x + 5 over real numbers? 4. What are the negatives of the
27、following elliptic curve points over real numbers? P(-4,-6), Q(17,0), R(3,9), S(0,-4) 5. In the elliptic curve group defined by y2 = x3 - 17x + 16 over real numbers, what is P + Q if P = (0,-4) and Q = (1,0)? 6. In the elliptic curve group defined by y2 = x3 - 17x + 16 over real numbers, what is 2P
28、if P = (4, 3.464)? （解见后）Click here for solutionsAn essential property for cryptography is that a group has a finite number of points. 3.0 Elliptic Curve Groups over FpCalculations over the real numbers are slow and inaccurate due to round-off error. Cryptographic applications require fast and precis
29、e arithmetic; thus elliptic curve groups over the finite fields of Fp and F2m are used in practice. Recall that the field Fp uses the numbers from 0 to p - 1, and computations end by taking the remainder on division by p. For example, in F23 the field is composed of integers from 0 to 22, and any op
30、eration within this field will result in an integer also between 0 and 22. An elliptic curve with the underlying field of Fp can formed by choosing the variables a and b within the field of Fp. The elliptic curve includes all points (x,y) which satisfy the elliptic curve equation modulo p (where x a
31、nd y are numbers in Fp). For example: y2 mod p = x3 + ax + b mod p has an underlying field of Fp if a and b are in Fp. If x3 + ax + b contains no repeating factors (or, equivalently, if 4a3 + 27b2 mod p is not 0), then the elliptic curve can be used to form a group. An elliptic curve group over Fp c
32、onsists of the points on the corresponding elliptic curve, together with a special point O called the point at infinity. There are finitely many points on such an elliptic curve. Note the seemingly random spread of points for the elliptic curve over Fp. 3.1 Example of an Elliptic Curve Group over FpAs a very small example, consider an elliptic curve over the field F23. With a = 1 and b = 0, the elli
