Back to results
US 7,412,062 B2Granted
Method and apparatus for elliptic curve scalar multiplication
AssigneeCerticom Corp.
InventorsRobert J. Lambert, Ashok Vadekar, Adrian Antipa
Life of this patent
Estimating the term…
Loading patent…
Loading patent…
AssigneeCerticom Corp.
InventorsRobert J. Lambert, Ashok Vadekar, Adrian Antipa
Estimating the term…
The applicants have recognized an alternate method of performing modular reduction that admits precomputation. The precomputation is enabled by approximating the inverse of the truncator T, which does not depend on the scalar. The applicants have also recognized that the representation of a scalar in a τ-adic representation may be optimized for each scalar that is needed. The applicants have further recognized that a standard rounding algorithm may be used to perform reduction modulo the truncator. In general terms, there is provided a method of reducing a scalar modulo a truncator, by pre-computing an inverse of the truncator. Each scalar multiplication then utilizes the pre-computed inverse to enable computation of the scalar multiplication without requiring a division by the truncator for each scalar multiplication.
A computer readable medium having computer executable instructions for causing an arithmetic logic unit in a cryptographic system to compute a point multiple to be used in performing cryptographic operations, said point multiple being derived from a scalar and a point on an elliptic curve having an equation of the form y2+xy=x3+a1x2+1, where a1 is either 0 or 1, said instructions configured for:
A cryptographic system comprising at least one entity having an arithmetic logic unit configured to compute a point multiple to be used in performing cryptographic operations, said point multiple being derived from a scalar and a point on an elliptic curve having an equation of the form y2+xy=x3+a1x2+1, where a1 is either 0 or 1, said point multiple computed by:
A computer readable medium having computer executable instructions for causing an arithmetic logic unit in a cryptographic system to compute a key for use in said cryptographic system, said key being derived from a scalar and a point on an elliptic curve having an equation of the form y2+xy=x3+a1x2+1, where a1, is either 0 or 1, said instructions configured for:
Dependencies are inferred from the claim text.