Method for calculating compressed RSA moduli
AssigneeThomson Licensing
InventorsEric Diehl, Marc Joye
Life of this patent
Estimating the term…
Abstract
A method for generating a compressed RSA modulus, allowing up to two thirds of the bits of a modulus N to be fixed. N has a predetermined portion NH, which comprises two parts Nh and Nm. A candidate RSA modulus that shares the Nh part is generated, and the candidate is then modified using Euclidian-type computations until it shares both Nh and Nm. Also provided is an apparatus for calculating compressed RSA moduli according to the method and a computer program product.
Claims8
A method for generating factors of a RSA modulus comprising a predetermined portion that can be larger than one half of the RSA modulus, the RSA modulus comprising at least two factors, the method comprising the steps of:
- a processor receiving a value of a predetermined portion that the RSA modulus is to share;
- the processor generating at least two candidate factors whose product shares at least a first part of the predetermined portion;
- the processor modifying the at least two candidate factors using Euclidean type computations until the resulting factors are prime and a product of the resulting factors fully shares the predetermined portion by:
- using an extension of the Extended Euclidean Algorithm to evaluate a correcting value for each of the at least two factors;
- wherein the extension of the Extended Euclidean Algorithm uses a sequence {ui, vi, di} obtained by the Extended Euclidean Algorithm satisfying a ui+b vi=di with a=q0 and b=p0 to derive two companion sequences {xi} and {yi};
- and
- adding respectively the correcting values to the at least two candidate factors to obtain at least two resulting factors;
- wherein the product of the resulting factors comprises the first shared part and shares the second part of the predetermined portion;
- and
- the processor outputting the resulting factors in order to allow cryptographic operations using the resulting factors.
An apparatus for calculating factors of a RSA modulus comprising a predetermined portion that can be larger than one half of the RSA modulus, the RSA modulus comprising at least two factors, the apparatus comprising a processor adapted to:
- receive a value of a predetermined portion that the RSA modulus is to share;
- generate at least two candidate factors whose product shares at least a first part of the predetermined portion;
- modify the at least two candidate factors using Euclidean type computations until the resulting factors are prime and a product of the resulting factors fully shares the predetermined portion by:
- using an extension of the Extended Euclidean Algorithm to evaluate a correcting value for each of the at least two factors;
- wherein the extension of the Extended Euclidean Algorithm uses a sequence {ui, vi, di} obtained by the Extended Euclidean Algorithm satisfying a ui+b vi=di with a=q0 and b=p0 to derive two companion sequences {xi} and {yi};
- and
- adding respectively the correcting values to the at least two candidate factors to obtain at least two resulting factors;
- wherein the product of the resulting factors comprises the first shared part and shares the second part of the predetermined portion;
- and
- output the resulting factors in order to allow cryptographic operations using the resulting factors.
Dependencies are inferred from the claim text.