Patent ID: 8135131

Claim:
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 {u i , v i , d i } obtained by the Extended Euclidean Algorithm satisfying a u i +b v i =d i with a=q 0 and b=p 0 to derive two companion sequences {x i } and {y i }; 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.