Patent ID: 7991162
Filing Date: 2011-08-02
Classification: G06F

Abstract:
1. A method of accelerating scalar multiplication in an elliptic curve cryptosystem (ECC) over prime fields, the method comprising the steps of: a) identifying multiplication operations within an ECC point operation that can be replaced by one field squaring and other cheaper field operations when applying algebraic substitutions; b) determining if field multiplication operations in step a) are even or odd field multiplications; c) modifying the ECC point operation with an equivalent point representation utilizing multiples of two if step b) identified odd field multiplications or keeping the ECC point operation unchanged if there is an efficient division by two available; and d) performing algebraic substitutions of the field multiplication operations from step a) with field operations comprising the one field squaring operations and other cheaper field operations selected from addition, subtraction and multiplication or division by a small constant, wherein steps a)-d) are executed by a processor.