Scalar multiplication calculation method and scalar multiplication calculation apparatus in elliptic curve cryptography

摘要

PROBLEM TO BE SOLVED: To provide a fast elliptic scalar multiplication computing method in a scalar multiplication computing device using an elliptic curve, capable of executing self homomorphism which is different from integer multiplication on the elliptic curve and to provide the device using the same.;SOLUTION: In the scalar multiplication computing device for computing a point on the elliptic curve, in which the endomorphism , being different from integer multiplication on the elliptic curve defined on a definition body F_q having a characteristic polynomial ²-+q (q is power of an odd prime number) is executed, and a scalar multiplication point from a scalar value, expansion which is a first numerical sequence from the scalar value is computed, and only if adjacent two digits in the expansion of the scalar value do not satisfy a predetermined condition, a computing is performed on two digits and one digit next to two digits, or each of two digits. Thereby, a second numerical sequence is computed from the scalar value, and fast computing is performed by executing the scalar multiplication from the second numerical sequence and the point from the elliptic curve.;COPYRIGHT: (C)2007,JPO&INPIT