Public key cryptographic apparatus and method

Abstract

A method and apparatus are disclosed for improving public key encryption and decryption schemes that employ a composite number formed from three or more distinct primes. The encryption or decryption tasks may be broken down into sub-tasks to obtain encrypted or decrypted sub-parts that are then combined using a form of the Chinese Remainder Theorem to obtain the encrypted or decrypted value. A parallel encryption/decryption architecture is disclosed to take advantage of the inventive method. REEXAMINATION RESULTS The questions raised in reexamination request No. 90 / 005 , 733 , filed May 18 , 2000 and reexamination request No. 90 / 005 , 776 , filed on Jul. 28 , 2000 , have been considered and the results thereof are reflected in this reissue patent which constitutes the reexamination certificate required by 35 U.S.C. 307 as provided in 37 CFR 1 . 570 ( e ) .

1. 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 athe 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 .  
 
     
     
       2. The method according to  claim 1 , comprising the further step of:  wherein the deciphering step includes
   establishing a number, d, as a multiplicative inverse of e ( mod ( lcm (( p   1   − 1   ) , (   p   2   − 1   ) , . . .  ( p   k   − 1   )))) , and    
 decoding the ciphertext word signal C to the plaintext message word signal M, wherein said decoding step comprises the step of: transforming said ciphertext word signal C,  whereby: 
   M=C d (mod n)M≡C d ( mod n ) .    
 
  where d is a multiplicative inverse of e(mod(lcm((p 1 −1), (p 2 −1), . . . , (p k −1)))). 
 
     
     
       3. A method for transferring a message signal M i  in a  communications of a message signal M i    cryptographically processed with RSA public key encryption in a  system having j terminals, wherein  each terminal is  being characterized by an encoding key E i =(e i , n i ) and a decoding key D i =(d i , n i ), where i=1, 2, . . . , j, and wherein  the message signal M i  corresponds to a number representative of a message-to-be-transmitted  received from the i th  terminal, the method comprising the steps of:
   establishing n   i    where  n i  is a composite number of the form 
   n i =P i,1 ·p i,2 ·, . . . , ·p i,k n i   =p   i,1   ·p   i,2   · . . . ·p   i,k      
 
       where k is an integer greater than 2,
 p i,1 , p i,2 , . . . , p i,k  are distinct random prime numbers,  
 e i  is relatively prime to lcm(p i,1 −1, p i,2 −1, p i,kd −1)  lcm( p   i,1   − 1 , p   i,2   − 1 , . . . , p   i,k   − 1   ) , and    
 d i  is selected from the group consisting of the  a class of numbers equivalent to a multiplicative inverse of 
   e i (mod(lcm((p i,1 −1), (p i,2 −1), . . . , (p i,k −1)))),;  
 
 
       comprising the steps of: receiving by a recipient terminal ( i=y )  from a sender terminal  ( i=x, x≠y )  a ciphertext signal C   x    formed by  encoding a digital message word signal M A  for transmission from a first terminal (i=A) to a second terminal (i=B), said encoding step including the sub-step of:M x   , wherein the encoding includes      transforming said message word signal M A  to one or more message block word signals M A ″  M X ″, each block word signal M A ″  M X   ″  corresponding to a number representative of a portion of said message word signal M A   M X   in the range 0≦M A ″≦n B   −1 0≦M   X   ″≦n   y   − 1   , and    transforming each of said message block word signals M A ″  M X ″ to a ciphertext word signal C A , C A  corresponding  C X    that corresponds  to a number representative of an encoded form of said message block word signal M A ″,  M X ″ whereby : 
   C A ≡M A   ″eB (mod n B .)C x   ≡M   x   ″ey ( mod n   y ) ; and    
     deciphering the received ciphertext word signal C   x    at the recipient terminal having available to it the k distinct random prime numbers p   y,1 , p y,2 , . . . , p y,k  for establishing its d y ;      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 .    
     
     
       4. A cryptographic communications  system for communications of a message cryptographically processed with an RSA public key encryption, comprising:
 a communication medium  channel for transmitting a ciphertext word signal C;  
 an  encoding means coupled to said channel and adapted for transforming a transmit message word signal M to athe ciphertext word signal C using a composite number, n,  
   where n is a product of the form        n=p   1   ·p   2   · . . . ·p   k   ,      
   where k is an integer greater than  2 , and p   1   , p   2   , . . . p   k    are distinct random prime numbers, and for transmitting C on said channel,    
 where the transmit message word signal M corresponds to a number representative of a  the message and 0≦M≦n− 1, where n is a composite number of the form  
   n=p 1 ·p 2 ·. . . ·p k    
 
 
       where k is an integer greater than 2 and p 1 , p 2 , . . . , p k  are distinct prime numbers, and  where the ciphertext word signal C corresponds to a number representative of an enciphered  encoded form of said message and corresponds to  through a relationship of the form 
   C≡M e (mod n), and  
 
       where e is a number relatively prime to lcm(p 1 −1, p 2 −1, . . . , p k −1); and
 a  decoding means coupled to said channel and adapted for receiving the ciphertext word signal C from said channel and, having available to it the k distinct random prime numbers p 1   , p   2   , . . . p   k   ,  for transforming the ciphertext word signal C to a receive message word signal M′ where M′ corresponds to a number representative of a deciphereddecoded form of the ciphertext word signal C and corresponds tothrough a relationship of the form    M′≡C d (mod n)    
 
       where d is selected from the group consisting of the  a class of numbers equivalent to a multiplicative inverse of
   e(mod(lcm((p 1 −1), (p 2 −1), . . . , (p k −1))));  
   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 transforming the ciphertext word signal C to a receive message word signal M′ 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 transforming of the ciphertext word signal C if the k distinct random prime numbers are used, relative to the number of computational cycles for performing a transforming of the ciphertext word signal C if the pair of prime numbers p and q is used instead .  
 
     
     
       5. A cryptographic communications  system for communications of a message cryptographically processed with an RSA public key encryption, the system having a plurality of terminals coupled by a communications channel, including  comprising: 
 a first terminal of the plurality of terminals characterized by an associated  encoding key E A =(e A , n A ) and a decoding key D A =(d A , n A ), wherein  n A  is a composite number of the form 
   n A =p A,1 ·p A,2 ·. . . ·P A,k    
 
 
       where
 k is an integer greater than 2,  
 p A,1 , p A,2 , . . . , p A,k  are distinct random prime numbers,  
 e A  is relatively prime to 
   lcm(p A,1 −1, p A,2 −1, . . . , p A,k −1), and  
 
 d A  is selected from the group consisting of the  a class of numbers equivalent to a multiplicative inverse of 
   e A (mod(lcm((p A,1 −1), (p A,2 −1), . . . , (p A,k −1)))),; and  
 
 and including  a second terminal, comprising:of the plurality of terminals having  
 blocking means for transforming a first message-to-be-transmitted , which is to be transmitted on said communications channel from said second terminal to said first terminal, into one or more transmit message word signals M B , where each M B  corresponds to a number representative of said first message in the range 
   0≦M B ≦n A   −1, and    
 
 encoding means coupled to said channel and adapted for transforming each transmit message word signal M B  to a ciphertext word signal C B  that and for transmitting C B  on said channel,  
 
       where C B   corresponds to a number representative of an enciphered  encoded form of said first message and corresponds to  through a relationship of the form 
   C B =M B   eA (mod n A )C B   ≡M   B   e     A   ( mod n   A ) ,    
 
       wherein  said first terminal comprises:having  decoding means coupled to said channel and adapted for receiving each of said ciphertext word signals C B  from said channel and, having available to it the k distinct random prime numbers p A,1   , p   A,2   , . . . , p   A,k   ,  for transforming each of said ciphertext word signals C B  to a receive message word signal M B   M B ′, and    means for transforming said receive message word signals M′  M B ′ to said first message, where M′ is  M B   ′ corresponds to  a number representative of a deciphered  decoded form of C B  and corresponds to  through a relationship of the form 
   M B ′=C B   d     A   (mod n A )M B   ′≡C   B   d     A   ( mod n   A ) ;    
     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 transforming said receive message word signal M   B   ′ to said first message 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 transforming of said receive message word signal M   B   ′ if the k distinct random prime numbers are used, relative to the number of computational cycles for performing a transforming of said receive message word signal M   B   ′ if the pair of prime numbers p and q is used instead .    
     
     
       6. The system according to  claim 5  wherein said second terminal is characterized by an associated  encoding key E B =(e B , n B ) and a decoding key DB=(D B , d B )  D B =( d   B   , n   B ), where:
 n B  is a composite number of the form 
   n B =p B,1 ·p B,2 ·. . . ·p B,k ,  
 
 where k is an integer greater than 2,  
 p B,1 , p B,2 , . . . , p B,k  are distinct random prime numbers,  
 e B  is relatively prime to 
   lcm(p B,1 −1, p B,2 −1, . . . , p B,k −1), and  
 
 d B  is selected from the group consisting of the  a class of numbers equivalent to a multiplicative inverse of 
   e B (mod(lcm((p B,1 ), (p B,2 −1), . . . , (p B,k −1)))),  
 
 
       wherein  said first terminal comprises:further having  blocking means for transforming a second message-to-be-transmitted , which is to be transmitted on said communications channel from said first terminal to said second terminal, to one or more transmit message word signals M A , where each M A  corresponds to a number representative of said message in the range 
   0≦M A   eB (mod n B ), 0 ≦M A   ≦n   B   − 1 , and    
   encoding means coupled to said channel and adapted for transforming each transmit message word signal M A  to a ciphertext word signal C A  and for transmitting C A  on said channel, where C A  corresponds to a number representative of an enciphered  encoded form of said second message and corresponds to  through a relationship of the form 
   C A =M A   eB (mod n B )C A   ≡M   A   e     B   ( mod n   B ) ; and    
   
       wherein  said second terminal comprises;further having  decoding means coupled to said channel and adapted for receiving each of said ciphertext word signals C A  from said channel and, having available to it the k distinct random prime numbers p B1   , p   B,2   , . . . , p   B,k   ,  for transforming each of said ciphertext word signals to a receive message word signal M A ′, and    means for transforming said receive message word signals M A   M A   ′  to said second message, where M′  M A   ′  corresponds to a number representative of a deciphered  decoded form of and corresponds to  C A    through a relationship of the form  
   M A ′≡C A   dB (mod n B )M A   ′≡C   A   d     B   ( mod n   B ).  
   
     
     
       7. A method for establishing cryptographic communications comprising the step of:
 encoding a digital message word signal M to a cipher text word signal C, where M corresponds to a number representative of a message and 
   0≦M≦n−1,  
   where n is a composite number having at least 3 whole number factors greater than one, the factors being distinct prime numbers, and    where C corresponds to a number representative of an encoded form of message word M,    wherein said encoding step comprises the step of: 
 transforming said message word signal M to said ciphertext word signal C whereby 
   C≡a e M e +a e−1 M e−1 +. . . +a o (mod n)  
 
 where e and a e, a   e−1 , . . . , a o  are numbers.  
   
     
     
       8. In the method according to  claim 7  wherein said encoding step includes the step of transforming M to C by the performance of a first ordered succession of invertible operations on M, the further step of:
 decoding C to M by the performance of a second ordered succession of invertible operations on C, where each of the invertible operations of said second succession is the inverse of a corresponding one of said first succession, and wherein the order of said operations in said second succession is reversed with respect to the order of corresponding operations in said first succession.    
     
     
       9. A communication  system for transferring  communications of message signals M i   cryptographically processed with RSA public key signing, comprising:
 j stations,  terminals including first and second terminals, each of the j stations  terminals being characterized by an encoding key E i =(e i , n i ) and decoding key D i =(d i , n i ), where i=1,2, . . . ,j, and wherein M i  corresponds to a number representative of a message signal to be transmitted from the i th  terminal,  each of the j terminals being adapted to transmit a particular one of the message signals where an i th    message signals M   i  is transmitted from an i th    terminal  and 
   0≦M i ≦n i −1,  
 n i is  being  a composite number of the form 
   n i =pi i,1 ·p i,2 ·. . . p i,k  n   i   =p   i,1   ·p   i,2   ·. . . ·p   i,k    
 
 
 where 
 k is an integer greater than 2,  
 p i,1 , p i,2 , . . . , p i,k  are distinct random prime numbers,  
 e i  is relatively prime to lcm(p i,1 −1,p i,2 −1, . . . , p i,k −1), and  
 d i  is selected from the group consisting of the  a class of numbers equivalent to a multiplicative inverse of 
   e i (mod(lcm((p i,1 −1), (p i,2 −1), . . . , (p i,k −1))));  
 asaid first one of the j terminalsterminal including  
 means for encoding a digital message word signal M A  for transmission  M 1    to be transmitted  from said first terminal (i=A   1 ) to a  said second one of the j terminals  terminal (i=B   2 ), and  
 said encoding means for  transforming said digital message word signal M AS , M AS  corresponding to a number representative of an encoded form of said message word signal M A , whereby:M 1S    using a relationship of the form      M AS ≡M A   dA (mod n A )M 1S   ≡M   1   d     1   ( mod n   1 ) ; and      
 
 
   means for transmitting said signed message word signal M   1S    from said first terminal to said second terminal, wherein said second terminal includes      means for decoding said signed message word signal M   1S    to said digital message word signal M   1   ;        wherein p and q are a pair of prime numbers that product of which equals a composite number m, the k distinct random prime number each smaller than p and q, and the composite number m having the same number of digits as the composite number n;        wherein encoding a digital message word signal M   1    is divided into sub - steps, on sub - step for each of the k distinct random prime numbers; and        wherein for a give number of digits for composite numbers n and m, it takes fewer computational cycles to perform the encoding of the digital message word signal M   i    if the k distinct random prime numbers are used, relative to the number of computational cycles for performing an encoding of the digital message word signal M   1    if the pair of prime numbers p and q is used instead .    
 
     
     
       10. The system of  claim 9 , wherein the means for decoding signed message word signal M 1S    includes means for further comprising:  
 means for transmitting said signal message word signal M AS  from said first terminal to said second terminal, and wherein said second terminal includes means for decoding said signed message word signal M AS  to said message word signal M A , said second terminal including: 
 means for  transforming said signed message word signal M AS   M 1S  to said digital message word signal M A , whereby  M 1    using a relationship of the form  
   M A ≡M AS   eA (mod n A )M i   ≡M   1S   e     1    ( mod n   1 ).  
 
 
 
     
     
       11. A communication system for transferring a message signal M i   cryptographically processed with RSA public key encryption, the communications system comprising: 
 j communication stations including first and second stations, each of the j communication stations being characterized by an encoding key E i =(e i , n i ) and a decoding key D i =(d i , n i ), where i=1, 2, . . . , j, and wherein M i  corresponds to a number representative of a message signal to be transmitted from the i th  terminal,  each of the j communication stations being adapted to transmit a particular one of the message signals where an i th    message signal M   i    is received from an i   th    communication station, and  
       0 ≦M   i   ≦n   i   − 1     
 
 n i  is  being a composite number of the form 
   n i =p i,1 ·p i,2 ·. . . ·p i,k    
 
 
       where
 k is an integer greater than 2,  
 p i,1 , p i,2 , . . . , p i,k  are distinct random prime numbers,  
 e i  is relatively prime to lcm(p i,1 −1,p i,2 −1, . . . ,p i,k −1), and  
 d i  is selected from the group consisting of the  a class of numbers equivalent to a multiplicative inverse of 
   e i (mod(lcm((p i,1 −1), (p i,2 −1), . . . , (p i,k −1)))),  
 
 asaid first one of the j communication stationsstation including  
 means for encoding a digital message word signal M A  for transmission  M 1    to be transmitted  from said first one of the j communication stations  station (l=A   1 ) to a  said second one of the j communication stations  station (l=B  2 ), means for transforming said digital message word signal M A   M 1  to one or more message block word signals M A ″  M 1 ″, each block word signal M A ′  M 1 ″ being a number representative of a portion of said digital message word signal M A ′  M 1  in the range 0≦M A ≦n B   −1,  0≦M   1   ″≦n   2   − 1 ,  and  
 means for transforming each of said message block word signals M A ″  M 1 ″ to a ciphertext word signal C A , C A  corresponding to a number representative of an encoded form of said message block word signal M A ″, whereby:  C 1    using a relationship of the form  
   C A =M A ″ Eb (mod n B )C 1   ≡M   1 ″ e     2   ( mod n   2 ) ; and    
   means for transmitting said ciphertext signals C   1    from said first station to said second station, wherein said second station includes    
   means for deciphering said ciphertext signals C   1    using p   2,1   , p   2,2   , . . . p   2,k    to produce said digital message word signal M   1   ;    
 
   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 deciphering said ciphertext signals C   1    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 of said ciphertext signals C   1    if the k distinct random prime numbers are used, relative to the number of computational cycles for performing a deciphering of said ciphertext signals C   1    if the pair of prime numbers p and q is used instead .  
 
     
     
       12. The communications system of  claim 11  further comprising:
 means for transmitting said ciphertext word signals from said first terminal to said second terminal, and  wherein said second terminal  the deciphering means includes  
 means for decoding said cyphertext word signals C 1  to said message block word signals MA  M 1   ″ using a relationship of the form, said second terminal including:    
 means for transforming each of said ciphertext word signals C A  to one of said message block word signals M A ″, whereby  
   M A ″≡C A   Db (mod n B )M 1   ″≡C   1   d     2   ( mod n   2 ) , and    
 
 means for transforming said message block word signals M A ″  M 1 ″ to said message word signal M A   M 1 .  
 
     
     
       13. In a communications system, including first and second communicating stations interconnected for communication therebetween,
 the first communicating station having 
 encoding means for transforming a transmit message word signal M to a ciphertext word signal C where M corresponds to a number representative of a message and 
   0≦M≦n−1  
 
 where n is a composite number having at least 3 whole number factors greater than one, the factors being distinct prime numbers, and  
 where C corresponds to a number representative of an enciphered form of said message and corresponds to 
   C≡a e M e +a e−1 M e−1 +. . . +a o (mod n)  
 
   where e and a e , a e −1, . . . , a o  are numbers; and 
 means for transmitting the ciphertext word signal C to the second communicating station.  
   
     
     
       14. The method according to  claim 9 , wherein the signed message word signal M 1S   , formed from the digital message word signal M   1    being cryptographically processed at the first terminal with multi - prime  ( k> 2   )  RSA public key signing which is characterized by the composite number n being computed as the product of the k distinct random prime numbers p   1   , p   2   , . . . p   k   , is decipherable at the second terminal with two - prime RSA public key signing characterized by the composite number m being computed as the product of the pair of prime numbers p and q.    
     
     
       15. A method of communicating a message cryptographically processed with an RSA public key encryption, comprising the steps of:
   selecting a public key portion e associated with a recipient intended for receiving the message;        developing k distinct random prime numbers, p   1   , p   2   , . . . p   k   , where k≧ 3 , and checking that each of the k distinct random prime numbers minus  1 , p   1   − 1 , p   2   − 1 , . . . , p   k   − 1 , is relatively prime to the public key portion e;      computing a composite number, n, as a product of the k distinct random prime numbers;          receiving a ciphertext message formed by encoding a plaintext message data M to the ciphertext message data C using a relationship of the form      C≡M e ( mod n )        where M represents the message, where  0 ≦M≦n− 1 , and where the sender knows n and the public key portion e but has no access to the k distinct random prime numbers, p   1   , p   2   , . . . p   k   ; and        deciphering at the recipient the received ciphertext message data C to produce the message, the recipient having access to the k distinct random prime numbers, 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.      
     
     
       16. The method according to  claim 15 , comprising the further step of:
   establishing a private key portion d by a relationship to the public key portion e in the form of d≡e   −1 ( mod (( p   1   − 1   )·( p   2   − 1   )· . . . ·( p   k   − 1   ))) ,        wherein the deciphering step includes decoding the ciphertext message data C to the plaintext message data M using a relationship of the form M≡C   d ( mod n ) .      
     
     
       17. The method according to  claim 15 , wherein a message cryptographically processed by the sender with two- prime RSA public key encryption characterized by the composite number m being computed as the product of the pair of prime numbers p and q, is decipherable with multi - prime  ( k> 2   )  RSA public key encryption characterized by the composite number n being computed as the product of the k distinct random prime numbers p   1   , p   2   , . . . p   k   .    
     
     
       18. The method according to  claim 15 , wherein n and m include values that are more than  600  digits long.  
     
     
       19. A method of communicating a message cryptographically processed with RSA public key encryption, comprising the steps of:
   selecting a public key portion e;        developing k distinct random prime numbers p   1   , p   2   , . . . p   k   , where k≧ 3 , and checking that each of the k distinct random prime numbers minus  1 , p   1   − 1 , p   2   − 1 , . . . p   k   − 1     , is relatively prime to the public key portion e;        establishing a private key portion d by a relationship to the public key portion e in the form of d≡e   −1 ( mod (( p   1   − 1   )·( p   2   − 1   ) . . . ( p   k   − 1   ))) ;        computing a composite number, n, as a product of the k distinct random prime numbers;        receiving a ciphertext message data C representing an encoded form of a plaintext message data M; and        decoding the received ciphertext message data C to the plaintext message data M using a relationship of the form        M≡C   d ( mod n ) ,          the decoding performed by a recipient owning the private key portion d and having access to the k distinct random prime numbers 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 decoding 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 decoding step if the k distinct random prime numbers are used, relative to the number of computational cycles for performing a decoding step if the pair of prime numbers p and q is used instead.      
     
     
       20. The method according to  claim 19 , wherein the ciphertext message data C is formed by encoding the plaintext message data M to the ciphertext message data C using a relationship of the form C≡M e  ( mod n ) , wherein  0 ≦M≦n− 1  and wherein n and the public key portion e are accessible to the sender although it has no access to the k distinct random prime numbers p   1   , p   2   , . . . p   k   .    
     
     
       21. The method according to  claim 19 , wherein a message cryptographically processed by the sender with two- prime RSA public key encryption characterized by the composite number m being computed as the product of the pair of prime numbers p and q, is decipherable by the decoding with multi - prime  ( k> 2   )  RSA public key encryption characterized by the composite number n being computed as the product of the k distinct random prime numbers p   1   , p   2   , . . . p   k   .    
     
     
       22. The method according to  claim 19 , wherein n and m include values that are more than  600  digits long.  
     
     
       23. A method of communicating a message cryptographically processed with RSA public key signing, comprising the steps of:
   selecting a public key portion e;        developing k distinct random prime numbers p   1   , p   2   , . . . p   k   , where k≧ 3 , and checking that each of the k distinct random prime numbers minus  1 , p   1   − 1 , p   2   − 1 , . . . p   k   − 1 , is relatively prime to the public key portion e;        establishing a private key portion d of a relationship to the public key portion e of the form d≡e   −1 ( mod (( p   1   − 1   )·( p   2   − 1   ) . . . ( p   k   − 1   )))) ;        computing a composite number, n, as product of the k distinct random prime numbers;        encoding a plaintext message data M with the private key portion d to produce a signed message M   S    using a relationship of the form      
        M S   ≡M   d ( mod n ) ,  
   where  0 ≦M≦n− 1 ;    
   receiving the signed message M   S   ; and    
   deciphering the signed message to produce the plaintext message data M;    
   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 encoding 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 encoding step if the k distinct random prime numbers are used, relative to the number of computational cycles for performing an encoding step if the pair of prime numbers p and q is used instead.    
 
     
     
       24. The method of  claim 23 , wherein the deciphering step includes:
   decoding the signed message M   S    with the public key portion e to produce the plaintext message data M using a relationship of the form M≡M   S   e ( mod n ).    
     
     
       25. The method according to  claim 23 , wherein the signed message M S    formed from the plaintext message data M being cryptographically processed at the sender with multi - prime  ( k> 2   )  RSA public key signing which is characterized by the composite number n being computed as the product of the k distinct random prime numbers p   1   , p   2   , . . . p   k   , is decipherable by the decoding at the recipient with two - prime RSA public key signing characterized by the composite number m being computed as the product of the pair of prime numbers p and q.    
     
     
       26. The method according to  claim 23 , wherein n and m include values that are more than  600  digits long.  
     
     
       27. A method for communicating a message cryptographically processed with RSA public key encryption, comprising the steps of:
   sending to a recipient a cryptographically processed message formed by assigning a number M to represent the message in plaintext message form, and cryptographically transforming the assigned number M from the plaintext message form to a number C that represents the message in an encoded form, wherein the number C is a function of      the assigned number M,        a number n that is a composite number equaling the product of at least three distinct random prime numbers, wherein  0 ≦M≦n− 1 , and        an exponent e that is a number relatively prime to a lowest common multiplier of the at least three distinct random prime numbers,          wherein the number n and exponent e having been obtained by the sender are associated with the recipient to which the message is intended; and        receiving the cryptographically processed message which is decipherable by    the recipient based on        the number n,        another exponent d, and        the number C,          wherein the exponent d is a function of the exponent e and the at least three distinct random prime numbers;          wherein p and q are a pair of prime numbers that product of which equals a composite number m, the at least three 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 deciphering the cryptographically processed message is divided into sub - steps, one sub - step for each of the at least three 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 if the at least three distinct random prime numbers are used, relative to the number of computational cycles for performing a deciphering if the pair of prime numbers p and q is used instead.      
     
     
       28. The method according to  claim 27 ,
   wherein the cryptographically transforming step includes using a relationship of the form C≡M   e  ( mod n ) ,        wherein the exponent d is established based on the at least three distinct random prime numbers p   1   , p   2   , . . . p   k   , using a relationship of the form d≡e   −1 ( mod (( p   1   − 1   )·( p   2   − 1   ) . . . ( p   k   − 1   ))) , and        wherein the cryptographically processed message is deciphered using a relationship of the form M≡C   d ( mod n ) .      
     
     
       29. The method according to  claim 27 , wherein a message cryptographically processed by the sender with two- prime RSA public key encryption characterized by the composite number m being computed as the product of the pair of prime numbers p and q, is decipherable at the recipient with multi - prime RSA public key encryption characterized by the composite number n being computed as the product of the at least three distinct random prime numbers.    
     
     
       30. The method according to  claim 27 , wherein n and m include values that are more than  600  digits long.  
     
     
       31. A method for communicating a message cryptographically processed with RSA public key encryption, comprising the steps of:
   receiving from a sender a cryptographically processed message, in the form of a number C, which is decipherable by the recipient based on a number n, an exponent d, and the number C; and        deciphering the cryptographically processed message,      wherein a number M represents a plaintext form of the message,        wherein the number C represents a cryptographically encoded form of the message and is a function of      the number M,        the number n that is a composite number equaling the product of at least three distinct random prime numbers, wherein  0 ≦M≦n− 1 , and        an exponent e that is a number relatively prime to a lowest common multiplier of the at least three distinct random prime numbers,          wherein the number n and exponent e are associated with the recipient to which the message is intended, and        wherein the exponent d is a function of the exponent e and the at least three distinct random prime numbers;          wherein p and q are a pair of prime numbers that product of which equals a composite number m, the at least three distinct random prime numbers each smaller than p and q, the composite number m having the same number of digits as the composite number n;        wherein deciphering the cryptographically processed message is divided into sub - steps, one sub - step for each of the at least three 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 if the at least three distinct random prime numbers are used, relative to the number of computational cycles for performing a deciphering if the pair of prime numbers p and q is used instead.      
     
     
       32. The method according to  claim 31 ,
   wherein the number C is formed using a relationship of the form C≡M   e  ( mod n ) ,        wherein the exponent d is established based on the at least three distinct random prime numbers p   1   , p   2   , . . . p   k   , using a relationship of the form d≡e   −1 (( p   1   − 1   )·( p   2   − 1   ) . . . ( p   k   − 1   ))) ,        and wherein the number M is obtained using a relationship of the form M≡C   d ( mod n ) .      
     
     
       33. The method according to  claim 31 , wherein a message cryptographically processed by the sender with two- prime RSA public key encryption characterized by the composite number m being computed as the product of the pair of prime numbers p and q, is decipherable at the recipient with multi - prime RSA public key encryption characterized by the composite number n being computed as the product of the at least three distinct random prime numbers.    
     
     
       34. The method according to  claim 31 , wherein n and m include values that are more than  600  digits long.  
     
     
       35. A cryptography method for local storage of data by a private key owner, comprising the steps of:
   selecting a public key portion e;        developing k distinct random prime numbers, p   1   , p   2   , . . . p   k   , where k≧ 3 , and checking that each of the k distinct random prime numbers minus  1 , p   1   − 1 , p   2   − 1 , . . . , p   k   − 1 , is relatively prime to the public key portion e;        establishing a private key portion d by a relationship to the public key portion e in the form of d≡e   −1 ( mod (( p   1   − 1   )·( p   2   − 1   ) . . . ( p   k   − 1   ))) ;        computing a composite number, n, as a product of the k distinct random prime numbers that are factors of n, where only the private key owner knows the factors of n; and        encoding plaintext data M to ciphertext data C for the local storage, using a relationship of the form        C≡M   e ( mod n ),        wherein  0 ≦M≦n− 1 , whereby the ciphertext data C is decipherable only by the private key owner having available to it the factors of n;        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 encoding 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 encoding step if the k distinct random prime numbers are used, relative to the number of computational cycles for performing an encoding step if the pair of prime numbers p and q is used instead.      
     
     
       36. The cryptography method in accordance with  claim 35 , further comprising the steps of:
   decoding the ciphertext data C from the local storage to the plaintext data M using a relationship of the form M≡C   d  ( mod n ) .      
     
     
       37. A cryptographic communications system, comprising:
   a plurality of stations;        a communications medium; and        a host system adapted to communicate with the plurality of stations via the communications medium sending and receiving messages cryptographically processed with an RSA public key encryption, the host system including at least one cryptosystem configured for      developing k distinct random prime numbers p   1   , p   2   , . . . , p   k   , where k≧ 3 ,        checking that each of the k distinct random prime numbers minus  1 , p   1   − 1 , p   2   − 1 , . . . p   k   − 1 , is relatively prime to a public key portion e that is associated with the host system,        computing a composite number, n, as a product of the k distinct random prime numbers,        establishing a private key portion d by a relationship of the public key portion e in the form of d≡e   −1 ( mod (( p   1   − 1   )·( p   2   − 1   ) . . . ( p   k   − 1   ))) ,        in response to an encoding request from the host system, encoding a plaintext message data M producing therefrom a ciphertext message data C to be communicated via the host system, the encoding using a relationship of the form        C≡M   e ( mod n ) ,          where  0 ≦M≦n− 1 , and        in response to a decoding request from the host system, decoding a ciphertext message data C′ communicated via the host producing therefrom a plaintext message data M′ using a relationship of the form        M′≡C′   d ( mod n ) ;            wherein p and q are a pair of prime numbers that product of which equals a composite number, 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 decoding the ciphertext message data C′ 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 decoding of the ciphertext message data C′ if the k distinct random prime numbers are used, relative to the number of computational cycles for performing a decoding of the ciphertext message data C′ if the pair of prime numbers p and q is used instead.      
     
     
       38. The system of  claim 37 , wherein the at least one cryptosystem includes a plurality of exponentiators configured to operate in parallel in developing respective subtask values corresponding to the message.  
     
     
       39. The system of  claim 37 , wherein the at least one cryptosystem includes
   a processor,        a data - address bus,        a memory coupled to the processor via the data - address bus,        a data encryption standard  ( DES )  unit coupled to the memory and the processor via the data - address bus, and        a plurality of exponentiator elements coupled to the processor via the DES unit, the plurality of exponentiator elements being configured to operate in parallel in developing respective subtask values corresponding to the message.      
     
     
       40. The system of  claim 39 , wherein the memory and each of the plurality of exponentiator elements has its own DES unit that cryptographically processes message data received/returned from/to the processor.  
     
     
       41. The system of  claim 39 , wherein the memory is partitioned into address spaces addressable by the processor, including secure, insecure and exponentiator elements address spaces, and wherein the DES unit is configured to recognize the secure and exponentiator elements address spaces and to automatically encode message data therefrom before it is provided to the exponentiator elements, the DES unit being bypassed when the processor is accessing the insecure memory address spaces, the DES unit being further configured to decode encoded message data received from the memory before it is provided to the processor.  
     
     
       42. The system of  claim 39 , wherein the at least one cryptosystem meets FIPS ( Federal Information Processing Standard )    140   -   1  level  3 .    
     
     
       43. The system of  claim 39 , wherein the processor maintains in the memory the public key portion e and the composite number n with its factors p 1   , p   2   , . . . p   k   .    
     
     
       44. A system for communications of a message cryptographically processed with RSA public key encryption, comprising:
   a bus; and        a cryptosystem communicatively coupled to and receiving from the bus encoding and decoding requests, the cryptosystem being configured for      providing a public key portion e,        developing k distinct random prime numbers p   1   , p   2   , . . . , p   k   , where k≧ 3 ,        checking that each of the k distinct random prime numbers minus  1 , p   1   − 1 , p   2   − 1 , . . . p   k   1   , is relatively prime to the public key portion e,        computing a composite number, n, as a product of the k distinct random prime numbers,        establishing a private key portion d by a relationship to the public key portion e in the form of d≡e   −1 ( mod (( p   1   − 1   )·( p   2   − 1   ) . . . ( p   k   − 1   ))) ,        in response to an encoding request from the bus, encoding a plaintext form of a first message M to produce C, a ciphertext form of the first message, using a relationship of the form        C≡M   e ( mod n ) ,          wherein  0 ≦M≦n− 1 , and        in response to a decoding request from the host system, decoding C′, a ciphertext form of a second message, to produce M′, a plaintext form of the second message, using a relationship of the form      M′≡C′ d ( mod n ) ,        the first and second messages being distinct or one and the same;            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 decoding C′ 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 decoding of C′ if the k distinct random prime numbers are used, relative to the number of computational cycles for performing a decoding of C′ if the pair of prime numbers p and q is used instead.      
     
     
       45. A system for communications of a message cryptographically processed with RSA public key encryption, comprising:
   a bus; and        a cryptoplasm receiving from the system via the bus encoding and decoding requests, the cryptosystem including      a plurality of exponentiator elements configured to develop subtask values,        a memory, and        a processor configured for      receiving the encoding and decoding requests, each encoding request providing a plaintext message M to be encoded,        obtaining a public key that includes an exponent e and a modulus n, a representation of the modulus n existing in the memory in the form of its k distinct random prime number factors p   1   , p   2   , . . . p   k   , where k≧ 3 ,        constructing subtasks, one subtask for each of the k factors, to be executed by the exponentiator elements for producing respective ones of the subtask values C   1   , C   2   , . . . C   k   , and        forming a ciphertext message C from the subtask values C   1   , C   2   , . . . C   k   ,        wherein the ciphertext message C is decipherable using a private key that includes the modulus n and an exponent d which is a function of e;            wherein p and q are a pair of prime numbers that product of which equals a modulus m, the k distinct random prime numbers each smaller than p and q, and the modulus m having the same number of digits as the modulus n; and        wherein for a given number of digits for modulus n and modulus m, it takes fewer computational cycles to form the ciphertext message C if the k distinct random prime numbers are used, relative to the number of computational cycles for forming a ciphertext message C′ if the pair of prime numbers p and q is used instead.      
     
     
       46. The system of  claim 45 , wherein each one of the subtask values C 1   , C   2   , . . . C   k    is developed using a relationship of the form C   i   ≡M   i   e     i    ( mod p   i ) , where M   i   ≡M ( mod p   i ) , and e   i   ≡e ( mod p   i   − 1   ) , and where i= 1 ,  2 , . . . k.    
     
     
       47. A system for communications of a message cryptographically processed with RSA public key encryption, comprising:
   a bus; and        a cryptosystem receiving from the system via the bus encoding and decoding requests, the cryptosystem including      a plurality of exponentiator elements configured to develop subtask values,        a memory, and        a processor configured for      receiving the encoding and decoding requests, each encoding/decoding request provided with a plaintext/ciphertext message M/C to be encoded/decoded and with or without a public/private key that includes an exponent e/d and a modulus n representation of which exists in the memory in the form of its k distinct random prime number p   1   , p   2   , . . . p   k   , where k≧ 3 ,        obtaining the public/private key from the memory if the encoding/decoding request is provided without the public/private key,        constructing subtasks to be executed by the exponentiator elements for producing respective ones of the subtask values M   1   , M   2   , . . . M   k   /C   1   , C   2   , . . . C   k   , and        forming the ciphertext/plaintext message C/M from the subtask values C   1   , C   2   , . . . C   k   /M   1   , M   2   , . . . M   k   ;            wherein p and q are a pair of prime numbers that product of which equals a modulus m, the k distinct random prime numbers each smaller than p and q, and the modulus m having the same number of digits as the modulus n; and      wherein for a given number of digits for modulus n and modulus m, it takes fewer computational cycles to form the ciphertext/plaintext message C/M if the k distinct random prime numbers are used, relative to the number of computational cycles for forming a ciphertext/plaintext message C′/M′ if the pair of prime numbers p and q is used instead.        
     
     
       48. The system of  claim 47  wherein when produced each one of the subtasks C 1   , C   2   , . . . C   k    is developed using a relationship of the form C   i   ≡M   i   e     i    ( mod p   i ) , where C   i   ≡C ( mod p   i ) , and    e   i   ≡e ( mod p   i   − 1   ) , and where i= 1 ,  2 , . . . , k.    
     
     
       49. The system of  claim 47  wherein when produced each one of the subtasks M 1   , M   2   , . . . M   k    is developed using a relationship of the form M   i   ≡C   i   d     i    ( mod p   i ) , where M   i   ≡M ( mod p   i ) , and    d   i   =d ( mod p   i   − 1   ) , and where i= 1 ,  2 , . . . , k.    
     
     
       50. The system of  claim 49 , wherein the private key exponent d relates to the public key exponent e via d≡e −1 ( mod (( p   1   − 1   )·( p   2   − 1   ) . . . ( p   k   − 1   ))) .    
     
     
       51. A system for communications of a message cryptographically processed with RSA public key encryption, comprising:
   means for selecting a public key portion e;        means for developing k distinct random prime number p   1   , p   2   , . . . p   k   , where k≧ 3 , and for checking that each of the k distinct random prime numbers minus  1 , p   1   − 1 , p   2   − 1 , . . . p   k   − 1 , is relatively prime to the public key portion e;        means for establishing a private key portion of d by a relationship to the public key portion e in the form of d≡e   −1 ( mod (( p   1   − 1   )·( p   2   − 1   ) . . . ( p   k   − 1   ))) ;        means for computing a composite number, n, as a product of the k distinct random prime numbers;        means for receiving a ciphertext message data C; and        means for decoding the ciphertext message data C to a plaintext message data M using a relationship of the form        M≡C   d ( mod n ) ;          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 decoding said ciphertext message data C 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 decoding of said ciphertext message data C if the k distinct random prime numbers are used, relative to the number of computational cycles for performing a decoding of said ciphertext message data C if the pair of prime numbers p and q is used instead.      
     
     
       52. The system according to  claim 51 , further comprising:
   means for encoding the plaintext message data M to the ciphertext message data C, using a relationship of the form C≡M   e  ( mod n ) , where  0 ≦M≦n− 1 .      
     
     
       53. A system for communications of a message cryptographically processed with RSA public key signing, comprising:
   means for selecting a public key portion e;        means for developing k distinct random prime numbers p   1   , p   2   , . . . p   k   , where k≧ 3 , and for checking that each of the k distinct random prime numbers minus  1 , p   1   − 1 , p   2   − 1 , . . . p   k   − 1     , is relatively prime to the public key portion e;        means for establishing a private key portion d by a relationship to the public key portion e of the form d≡e   −1 ( mod (( p   1   − 1   )·( p   2   − 1   ) . . . ( p   k   − 1   ))) ;        means for computing a composite number, n, as a product of the k distinct random prime numbers; and        means for encoding a plaintext message data M with the private key portion d to produce a signed message M   S   , using a relationship of the form        M   S   ≡M   d ( mod n ) ,        
       
         where  0 ≦M≦n− 1 , the signed message M 
         S  
         being decipherable using the public key portion e;  
         
           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 encoding said plaintext message data M 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 encoding of said plaintext message data M if the k distinct random prime numbers are used, relative to the number of computational cycles for performing an encoding of said plaintext message data M if the pair of prime numbers p and q is used instead.  
         
       
     
     
       54. The system of  claim 53  further comprising:
   means for decoding the signed message M   S    with the public key portion e to produce the plaintext message data M using a relationship of the form M≡M   S   e ( mod n ) .      
     
     
       55. The system of  claim 52 , wherein the system can communicate the cryptographically processed message to another system that encodes/decodes data with RSA public key encryption using a modulus value equal to n independent of the k distinct prime numbers.  
     
     
       56. The system of  claim 54 , wherein the system can communicate the cryptographically processed message to another system that encodes/decodes data with RSA public key signing using a modulus value equal to n independent of the k distinct prime numbers.