Patent Number:
6,480,606
Title:
Elliptic curve encryption method and system
Abstract:
In encryption techniques using an elliptic curve, in order to use a homogeneous coordinate system [X, Y, Z], a high speed [X.sub.1, Y.sub.1, Z.sub.1, (Z.sub.1).sup.2, (Z.sub.1).sup.3 ] for the addition and a high speed [X.sub.1, Y.sub.1, Z.sub.1 ] for the doubling the following schemes are provided: (1) Addition is executed by [X.sub.3, Y.sub.3, Z.sub.3 ]=[X.sub.1, Y.sub.1, Z.sub.1, (Z.sub.1).sup.2, (Z.sub.1).sup.3 ]+[X.sub.2, Y.sub.2, Z.sub.2 ]. (2) Doubling is executed by a conventional [X.sub.3, Y.sub.3, Z.sub.3 ]=2[X.sub.1, Y.sub.1, Z.sub.1 ] and an addition operation is executed by [X.sub.3, Y.sub.3, Z.sub.3 ]=[X.sub.1, Y.sub.1, Z.sub.1, (Z.sub.1).sup.2, (Z.sub.1).sup.3 ]+[X.sub.2, Y.sub.2, Z.sub.2 ]. 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.sup.n +B where 0<A<2.sup.w, 0<B<2.sub.w, b=2.sub.w ; and w, A, b, n and B are positive integers.
Inventors:
Kurumatani; Hiroyuki (Yokohama, JP)
Assignee:
Hitachi, Ltd.
International Classification:
G06F 7/72 (20060101); G06F 7/60 (20060101); H04L 9/28 (20060101); H04L 9/30 (20060101); H04L 009/00 ()
Expiration Date:
11/12/2019