Patent ID: 7266197

Claim:
A system for producing asymmetric cryptographic keys, said keys comprising m≧1 private values Q 1 , Q 2 , . . . , Q m and m respective public values G 1 , G 2 , . . . , G m , the system comprising: a processor; and a memory unit coupled to the processor, the memory unit storing a set of instructions which when executed cause the processor to execute the following acts: selecting a security parameter k, wherein k is an integer greater than 1, determining a modulus n, wherein n is a public integer equal to the product of at least two prime factors p 1 , . . . , p f , at least two of these prime factors, say p 1 and p 2 , being such that p 1 ≡3 mod 4 and p 2 ≡3 mod 4; selecting m base numbers g 1 , g 2 , . . . , g m , wherein each base number g i (for i=1, . . . , m) is an integer greater than 1 and is a non-quadratic residue of the ring of integers modulo n, and such that p 2 is complementary to p 1 with respect to one of the base numbers; calculating the public values G i for i=1, . . . , m through G i ≡g i 2 mod n; and calculating the private values Q i for i=1, . . . , m by solving either the equation G i .Q i v ≡1 mod n or the equation G i ≡Q i v mod n, wherein the public exponent v is such that v=2 k .