VECTOR OPERATION UNIT, DIVISION VALUE OPERATION UNIT, ELLIPTIC CURVE SCALAR MULTIPLE OPERATION UNIT, ELLIPTIC CURVE CRYPTOSYSTEM OPERATION UNIT, VECTOR OPERATION METHOD AND PROGRAM, AND COMPUTER READABLE RECORDING MEDIUM WITH THE PROGRAM RECORDED THEREON

摘要

PPROBLEM TO BE SOLVED: To perform scalar multiple operation at high speed, that is, to search for shorter VSB1/SB, VSB2/SBin order to perform elliptic curve cryptosystem operation at high speed. PSOLUTION: A vector operation unit 400 for calculating vector VSB1/SBand vector VSB2/SBused for obtaining division values kSB1/SBand kSB2/SBfor dividing scalar K used for scalar multiplying a point on an elliptic curve by the scalar K by using a special homomorphic mapping ϕ is provided with: a vector VSB1/SBoperation section 402 for calculating the vector VSB1/SBby using an extended Euclidean algorithm; a vector V2 operation section 420 for calculating a set ASBh/SBof a plurality of integers by using the extended Euclidean algorithm, and calculating the vector VSB2/SBby using a plurality of integer values α contained in the calculated set ASBh/SBof a plurality of integers; and an output section 411 for outputting the calculated vector VSB1/SBand vector VSB2/SB. PCOPYRIGHT: (C)2005,JPO&NCIPI