Back to results
US 7,657,029 B2Granted
Systems and methods for generating random addition chains
AssigneeMicrosoft Corporation
InventorsAnton Mityagin, Ilya Mironov, Yaacov Nissim Kobliner
Life of this patent
Estimating the term…
Abstract
An addition chain is first generated, and then an integer x is derived from it. Doubling and star steps may be implemented in the addition chain. This approach eliminates the computationally expensive step of generating the addition chain from an exponent, and therefore can greatly reduce the computation time of the modular exponentiation.
Claims14
A method comprising:
- receiving, by a processor of a computing system, input parameters that are used by the computing system and the processor to generate an exponent for a cryptographic process, wherein said generating said exponent comprises;
- generating an addition chain based on the input parameters by:
- (a) initiating a chain;
- (b) flipping a biased coin;
- (c) performing a doubling step or a star step on the chain based on the biased coin flip;
- (d) when said star step is performed, choosing a random element and adding the random element to a set of random elements;
- (e) determining whether the size of the set of random elements is outside a bounded interval;
- and
- repeating steps (b)-(d) a number of times based on a length of the chain, wherein when the size of the set of random elements is outside the bounded interval, determining that generation of the chain is complete;
- deriving said exponent from the generated addition chain;
- and
- storing the exponent.
9 more elements
A method comprising:
- receiving, by a computing system, input parameters that are used by a processing system for generating an addition chain that is then used by a processor of the computing system to derive an exponent from said generated addition chain for a cryptographic process;
- generating, by said processor of the computing system, the addition chain based on the input parameters, wherein said generating the addition chain comprises:
- (a) initializing a chain;
- (b) flipping a biased coin;
- (c) performing a doubling step or a star step on the chain based on the biased coin flip;
- (d) when said star step is performed, then choosing a random element and adding the random element to a set of random elements;
- (e) determining whether the size of the set of random elements is outside a bounded interval;
- and
- repeating steps (b)-(d) a number of times based on a length of the chain, wherein when the size of the set of random elements is outside the bounded interval, determining that generation of the chain is complete.
6 more elements
A computer readable storage medium having computer executable instructions stored thereon which are executed by a computer for performing steps of:
- receiving input parameters for generating an exponent for a cryptographic process;
- generating an addition chain based on the input parameters by;
- (a) initiating a chain;
- (b) flipping a biased coin;
- (c) performing a doubling step or a star step on the chain based on the biased coin flip;
- (d) when said star step is performed, choosing a random element and adding the random element to a set of random elements;
- (e) determining whether the size of the set of random elements is outside a bounded interval;
- and
- repeating steps (b)-(d) a number of times based on a length of the chain, wherein when the size of the set of random elements is outside the bounded interval, determining that generation of the chain is complete;
- deriving an the exponent from the generated addition chain;
- and
- storing the exponent.
9 more elements
Dependencies are inferred from the claim text.