ELLIPTIC CURVE INTEGRAL MULTIPLE ARITHMETIC DEVICE, AND KEY GENERATING DEVICE, ENCRYPTING DEVICE, AND DECRYPTING DEVICE CAPABLE OF UTILIZING THE ARITHMETIC DEVICE

摘要

PROBLEM TO BE SOLVED: To solve the following problem: an elliptic curve cryptogram is promising as a public key cryptogram since it is safe and the number of the digits of the key can be reduced, but it takes time in the operation in a finite field. SOLUTION: An input/output section 10 receives the input of an integer k which provides the coordinates of a point P on an elliptic curve and the multiple for integral multiplication. An s-ary expansion section 28 obtains the s-ary expansion of the integer k for each of a plurality of radixes (s). A cost evaluation section 30 obtains the calculation cost when k-multiplication is performed in s-ary system based on the number of non-zero digits of each s-ary expansion. A selection section 32 selects h-ary system with the lowest calculation cost. A preliminary computing section 34 previously calculates integral multiple points equal to or less than (h-1)-folds with respect to the point P and stores them. An h-ary operation section 35 calculates k-multiplication of the point P in h-ary system wherein the h-multiplication of the point P by an h-multiplication operation section 36 and the addition of integral multiple points equal to or less than (h-1)-folds with respect to the point P by an addition operation section 38 are combined. COPYRIGHT: (C)2005,JPO&NCIPI