Elliptic curve encryption method and system

摘要

In encryption techniques using an elliptic curve, in order to use a homogeneous coordinate system ÄX, Y, ZÜ, a high speed ÄX1, Y1, Z1, (Z1)<2>, (Z1)<3>Ü for the addition and a high speed ÄX1, Y1, Z1Ü for the doubling the following schemes are provided: (1) Addition is executed by ÄX3, Y3, Z3Ü = ÄX1, X1, Z1, (Z1)<2>, (Z1)<3>Ü + ÄX2, Y2, Z2Ü (Step 209). (2) Doubling is executed by a conventional ÄX3, Y3, Z3Ü = 2ÄX1, Y1, Z1Ü and an addition operation is executed by ÄX3, Y3, Z3Ü = ÄX1, Y1, Z1, (Z1)<2>, (Z1)<3>Ü + ÄX2, Y2, Z2Ü (Step 207). It is also required to speed up the multiplication modulo operation. The Montgomery multiplication modulo operation is speeded up by using the following forms of the definition order (prime): (3) the multiplication modulo operation is executed at high speed by using a prime having a form of p = Ab + B (Step 303) where 0 < A < 2; 0 < B < 2, b = 2; and w, A, b, n and B are positive integers.