COMPUTATIONAL METHOD, COMPUTATIONAL DEVICE ANDCOMPUTER SOFTWARE PRODUCT FOR MONTGOMERY DOMAIN

摘要

In Elliptic Curve Cryptography (ECC), one performs a great number of modular multiplications. These are usually done by Montgomery Multiplication algorithm, which needs the operands to be preprocessed (namely, converted to the Montgomery Domain), which is normally done by an equivalent of a long division. We provide a method to perform this conversion by a single Montgomery multiplication on the raw data. The method is formulated for elliptic curve points represented in Jacobian coordinates but can be extended to other representations.

主权项

1. A method for computation, comprising:
receiving, in a Montgomery multiplier circuit, a pair of input coordinates (x,y) specifying a point on an elliptic curve in a canonical form; converting the pair of the input coordinates to a quotient-based representation comprising three alternative coordinates (X′,Y′,Z′) in a Montgomery form by performing first Montgomery multiplications of the input coordinates by selected conversion factors; and carrying out one or more elliptic curve operations by applying second Montgomery multiplications to the alternative coordinates in the Montgomery form.