Patent ID: 7505587

Claim:
An elliptic curve cryptosystem apparatus, comprising: an obtaining unit obtaining coordinate of a point P on an elliptic curve over a finite field and an n-bit natural number d; register Q[ 2 ]; register Q[ 1 ]; register Q[ 0 ]; an arithmetic unit concurrently performing an elliptic curve addition ECADD and an elliptic curve doubling ECDBL when obtaining d×P by repeatedly performing steps (1) through (4) listed below a predetermined number of times based on the coordinates of the point P and the natural number d obtained by said obtaining unit: Q[ 2 ]=ECDBL ( Q[d[i ]]) (1) Q[ 1 ]=ECADD ( Q[ 0 ],Q[ 1]) (2) Q[ 0 ]=Q[ 2 −d[i]] (3) Q[ 1 ]=Q[ 1 +d[i]] (4) where an initial value of the register Q[ 0 ] is P, an initial value of the register Q[ 1 ] is 2×P, and a coefficient of a binary expression of a natural number d obtained by said obtaining unit is d[i] (d[n−1]˜d[ 0 ], d[i]=0, 1), wherein said arithmetic unit performs a conditional set of operations comprising storing an arithmetic result of the elliptic curve doubling ECDBL stored in the register Q[ 2 ] into the register Q[ 0 ] in step (3) and stores an arithmetic result of the elliptic curve addition ECADD stored in the register Q[ 1 ] into the register Q[ 1 ] in step (4) when d[i]=0; and stores the arithmetic result of the elliptic curve addition ECADD stored in the register Q[ 1 ] into the register Q[ 0 ] in step (3) and stores the arithmetic result of the elliptic curve doubling ECDBL stored in the register Q[ 2 ] into the register Q[ 1 ] in step (4) when d[i]=1; and an encryption unit generating encrypted data using the result stored in the register Q[ 1 ].