Patent ID: RE40530

Claim:
A method for establishing cryptographic communications of a message cryptographically processed with RSA ( Rivest, Shamir & Adleman ) public key encryption, comprising the step steps of: developing k distinct random prime numbers p 1 , p 2 , . . . , p k , wherein k is an integer greater than 2 ; providing a number e relatively prime to ( p 1 − 1 )·( p 2 − 1 )· . . . ·( p k − 1 ); providing a composite number n equaling the product p 1 ·p 2 · . . . ·p k ; receiving a ciphertext word signal C which is formed by encoding a plaintext message word signal M to a ciphertext word signal C, where M corresponds to a number representative of a the message and 0≦M≦n−1 n being a composite number formed from the product of p 1 ·p 2 ·. . . ·p k where k is an integer greater than 2, p 1 , p 2 , . . . p k are distinct prime numbers, and where C is a number representative of an encoded form of the plaintext message word signal M such that C≡M e ( mod n ) and where e is associated with an intended recipient of the ciphertext word signal C; and , wherein said encoding step comprises the step of: transforming said message word signal M to said ciphertext word signal C whereby C=M e (mod n) where e is a number relatively prime to (p 1 −1)·(p 2 −1). deciphering the received ciphertext word signal C at the intended recipient having available to it the k distinct random prime number p 1 , p 2 , . . . p k ; wherein p and q are a pair of prime numbers that product of which equals a composite number m, the k distinct random prime numbers each smaller than p and q, and the composite number m having the same number of digits as the composite number n; wherein the deciphering step is divided into sub - steps, one sub - step for each of the k distinct random prime numbers; and wherein for a given number of digits for composite numbers n and m, it takes fewer computational cycles to perform the deciphering step if the k distinct random prime numbers are used, relative to the number of computational cycles for performing a deciphering step if the pair of prime numbers p and q is used instead .