Public Key Cryptographic Methods and Systems

Abstract

Methods and systems are disclosed for improving public key cryptography schemes, such as RSA and its variants, to allow for decryption of messages using less than all of the prime factors of the modulus that is used for encryption of said messages.

The invention claimed is: 
     
         1 . A computer-based method for encrypting and decrypting at least one message M comprising:
 providing a system including a network and at least two computing devices each having a hardware processor;   the first hardware processor encrypting the at least one message M into a cipher message C using any method that produces the equivalent to C=M.sup.e mod N, M being an integer and 0<M<N, e being a number, and N being the exact product of at least two distinct prime factors;   the first hardware processor transmitting the cipher message C over a network; and   the second hardware processor decrypting the cipher message C using the number e and less than all of the prime factors of N.   
     
     
         2 . The method of  claim 1  wherein e is generated by calculating the exponent e as a number relatively prime to the product of one less than each factor of N. 
     
     
         3 . The method of  claim 1  wherein e is generated by calculating the exponent e as a prime number less than 10 digits. 
     
     
         4 . The method of  claim 1  wherein the step of the second hardware processor decrypting the cipher message C uses any method that produces a value equivalent to M=C.sup.d mod p, where p is not a squareful number and d is generated by calculating d such that the equation e*d=1 mod (p−1) is satisfied. 
     
     
         5 . The method of  claim 1  wherein e and N are calculated using RSA methods. 
     
     
         6 . A computer-based method for encrypting and transmitting at least one message M comprising:
 providing a computing device having a hardware processor;   the hardware processor creating a public key having a number e and a predetermined number of distinct prime factors used for the generation of a modulus N and less than all of the distinct prime factors available for the decryption of message M; and   the hardware processor encrypting the at least one message M into a cipher message C using any method that produces the equivalent to C=M.sup.e mod N, where 0<M<N, wherein N is the exact product of each member of a set of at least two distinct prime numbers.   the hardware processor transmitting the cipher message C over a network.   
     
     
         7 . The method of  claim 6 , wherein the step of the hardware processor generating the exponent e includes the hardware processor calculating the exponent e as a number that is relatively prime to the product of each distinct prime factor of N minus 1, (N.sub.1−1)* . . . (N.sub.j−1) for distinct prime factors of N, 1 to j, where j is the number of distinct prime factors in N, or choosing the exponent e as a small prime number. 
     
     
         8 . The method of  claim 6  further comprising the step of a second hardware processor decrypting the cipher message C into the message M using the public key. 
     
     
         9 . The method of  claim 6  further comprising the step of a second hardware processor decrypting the cipher message C using any method that produces a value equivalent to M=C.sup.d mod p, where d is generated by calculating d such that the equation e*d=1 mod (p−1) is satisfied. 
     
     
         10 . A public key method comprising the steps of:
 providing a network and a pair of computing devices each having a hardware processor;   the first hardware processor establishing a public key;   the first hardware processor encrypting a message, wherein the message includes electronic forms of information, documents, files, data, or any combination thereof;   wherein the step of encrypting includes using a modulus N that is calculated as the product of a set S of unraised distinct prime numbers alone; and   the second hardware processor decrypting the message using a public exponent e and less than all of the prime numbers of the set S.   
     
     
         11 . The method of claim  14 , wherein the step of establishing the public key further includes generating the exponent e as a number that is relatively prime to the product of each distinct prime factor of N minus 1, (N.sub.1−1)* . . . (N.sub.j−1) for distinct prime factors of N, 1 to j, where j is the number of distinct prime factors in N.