Back to results
US 7,680,268 B2Granted
Elliptic curve point octupling using single instruction multiple data processing
AssigneeMicrosoft Corporation
InventorsKristin E. Lauter, Denis X Charles
Life of this patent
Estimating the term…
Abstract
Systems and methods for elliptic curve octupling using Single Instruction Multiple Data (SIMD) processing are described. In one aspect, a weighted projective point P on an elliptic curve, P having coordinates (x, y, z) is identified. Value 8P is computed from P with 12 sets of field multiplications using SIMD processing. Each set of field multiplications includes one to four respective field multiplications. Each set of field multiplications is performed in parallel according to an assigned time-step.
Claims15
A method implemented by a single instruction multiple data (SIMD) computing system, the method comprising:
- Identifying, by a SIMD computing system configured to perform elliptic-curve octupling using SIMD, the coordinates x, y, and z of a weighted projective point P on an elliptic curve;
- computing by the SIMD computing system the coordinates r, s, t for 8P from P, 8P comprising 12 sets of field multiplications, the set of field multiplications comprising one to four particular field multiplications, each particular set of the 12 sets of field multiplications executed by the SIMD computing devices in parallel according to an assigned time-step, wherein computing 8P is determined with a straight-line algorithm;
- initially receiving original data;
- determining 8P for respective points on the elliptic curve with the straight-line elliptic curve point octupling algorithm;
- encrypting or signing the original data based upon the results of the determining of 8P;
- and
- storing the coordinates r, s, t to a computer readable storage medium associated with the computing system for subsequent use by the computing system.
4 more elements
A computer-readable storage medium comprising computer-program instructions executable by a processor for:
- identifying coordinates (x, y, z) corresponding to a weighted projective point P on an elliptic curve;
- and
- determining coordinates (r, s, t) associated with 8P by calculating 8P of P with 12 sets of field multiplications, each respective set of field multiplications comprising one to four field multiplications, each respective set of field multiplications being performed in parallel according to an assigned time-step, wherein the computer-program instructions for computing 8P are determined with a straight-line algorithm;
- receiving original data;
- determining 8P for respective points on the elliptic curve with the straight-line elliptic curve point octupling algorithm;
- decrypting or verifying cryptographically processed data based on results of the determining;
- and
- storing the coordinates r, s, t to a computer readable storage medium associated with the computing system for subsequent use by the computing system.
5 more elements
A computing device comprising:
- a processor configured to support at least in part Single Input Multiple Data processing;
- and
- a memory coupled to the processor, the memory comprising computer-program instructions executable by the processor for:
- identifying coordinates (x, y, z) corresponding to a weighted projective point P on an elliptic curve;
- and
- determining coordinates (r, s, t) corresponding to the result of computing 8P of P with 12 sets of field multiplications, each respective set of field multiplications comprising one to four field multiplications, each respective set of field multiplications being performed in parallel by separate processes of the computing device according to an assigned time-step, wherein the computer-program instructions for computing 8P are determined with a straight-line algorithm;
- receiving original data;
- determining 8P for respective points on the elliptic curve with the straight-line elliptic curve point octupling algorithm;
- encrypting or signing original data based on results of the determining;
- and
- storing the coordinates r, s, & t to a computer readable storage medium associated with the computing system for subsequent use by the computing system.
8 more elements
A method implemented by a single instruction multiple data (SIMD) computing system, the method comprising:
- identifying, by a SIMD computing system configured to perform elliptic-curve octupling using SIMD, the coordinates x, y, and z of a weighted projective point P on an elliptic curve;
- and
- computing by the SIMD computing system the coordinates r, s, t for 8P from P, 8P comprising 12 sets of field multiplications, the set of field multiplications comprising one to four particular field multiplications, each particular set of the 12 sets of field multiplications executed by the SIMD computing devices in parallel according to an assigned time-step, wherein computing 8P is determined with a straight-line algorithm;
- initially receiving original data;
- determining 8P for respective points on the elliptic curve with the straight-line elliptic curve point octupling algorithm;
- decrypting or verifying cryptographically processed the original data based on results of the determining of 8P;
- and
- storing the coordinates r, s, t to a computer readable storage medium associated with the computing system for subsequent use by the computing system.
5 more elements
A computer-readable storage medium comprising computer-program instructions executable by a processor for:
- identifying coordinates (x, y, z) corresponding to a weighted projective point P on an elliptic curve;
- and
- determining coordinates (r, s, t) associated with 8P by calculating 8P of P with 12 sets of field multiplications, each respective set of field multiplications comprising one to four field multiplications, each respective set of field multiplications being performed in parallel according to an assigned time-step, wherein the computer-program instructions for computing 8P are determined with a straight-line algorithm;
- receiving original data;
- determining 8P for respective points on the elliptic curve with the straight-line elliptic curve point octupling algorithm;
- encrypting or signing original data based on results of the determining;
- and
- storing the coordinates r, s, t to a computer readable storage medium associated with the computing system for subsequent use by the computing system.
5 more elements
A computing device comprising:
- a processor configured to support at least in part Single Input Multiple Data processing;
- and
- a memory coupled to the processor, the memory comprising computer-program instructions executable by the processor for:
- identifying coordinates (x, y, z) corresponding to a weighted projective point P on an elliptic curve;
- and
- determining coordinates (r, s, t) corresponding to the result of computing 8P of P with 12 sets of field multiplications, each respective set of field multiplications comprising one to four field multiplications, each respective set of field multiplications being performed in parallel by separate processes of the computing device according to an assigned time-step, wherein computing 8P is determined with a straight-line algorithm;
- receiving original data;
- determining 8P for respective points on the elliptic curve with the straight-line elliptic curve point octupling algorithm;
- decrypting or verifying cryptographically processed data based on results of the determining;
- and
- storing the coordinates r, s, & t to a computer readable storage medium associated with the computing system for subsequent use by the computing system.
8 more elements
Dependencies are inferred from the claim text.