Patent ID: 8218760

Claim:
A method of generating factors of a RSA modulus N with a predetermined portion N h and a non-predetermined portion N l , the RSA modulus N comprising at least two factors, the method being performed by a device and comprising steps of: generating a first prime p; obtaining a value N h that forms a part of the RSA modulus N; generating a second prime q; and outputting at least a lossless compressed representation of the RSA modulus N that enables unambiguous recovery of the RSA modulus N; wherein the second prime q is randomly generated in a predetermined interval dependent from p and N h so that pq is a RSA modulus that shares N h ; wherein the predetermined portion N h heads the RSA modulus N; wherein the RSA modulus N is a n-bit modulus and the predetermined portion N h comprises k bits; wherein the first prime p is generated in an interval pε[2 n-n 0 -1/2 ,2 n-n 0 −1] so that gcd(p−1,e)=1, wherein e is a public exponent and wherein 1<n 0 <n; wherein the second prime q is generated in an interval q ε [ 2 n - k ⁢ N h + 1 p , 2 n - k ⁢ ( N h + 1 ) - 1 p ] , so that gcd(q−1,e)=1; and wherein N=N h ∥N l , where N l =(pq)mod 2 n-k .