WO/1996/021295 | SPREAD-SPECTRUM SYSTEM AND METHOD |
JPH04142142 | CORDLESS TELEPHONE SYSTEM |
WO/2003/061186 | IDENTITY VERIFICATION METHOD USING A CENTRAL BIOMETRIC AUTHORITY |
US6396926B1 | 2002-05-28 | |||
US7221757B2 | 2007-05-22 | |||
US7248692B2 | 2007-07-24 | |||
US6772184B2 | 2004-08-03 | |||
US5987131A | 1999-11-16 | |||
US6091819A | 2000-07-18 | |||
US6396926B1 | 2002-05-28 | |||
US7221757B2 | 2007-05-22 | |||
US7248692B2 | 2007-07-24 | |||
US6772184B2 | 2004-08-03 | |||
US5987131A | 1999-11-16 | |||
US6091819A | 2000-07-18 |
CLAIMS What is claimed is: 1. A system for encrypting/decrypting messages, comprising: a public key cryptosystem having a predetermined number of prime factors used for the generation of a modulus N and an exponent e; wherein a proper subset of the prime factors of the modulus N, along with the exponent e>, are required to decrypt messages that are encrypted using the public exponent e and the public modulus N, where e and N are calculated using RSA methods, and encryption occurs using RSA methods. 2. A method for encrypting/decrypting messages comprising the steps of: providing a public key cryptosystem having a predetermined number of prime factors used for the generation of a modulus N arid an exponent e; wherein a proper subset of the prime factors of the modulus N are required to decrypt messages that are encrypted using the public exponent e and the public modulus N, where e andN are calculated using RSA methods, and encryption occurs using RSA methods. 3. A method for encrypthig/decrypting messages comprising the steps of: Encrypting a plaintext message M into a ciphertext message C using any method that produces a value equivalent to C = Me mod N, where 0 < M < Na, such that the ciphertex.1 C can be decrypted into the plaintext message M using only e and the prime factors of Nd N being the product of all of the numbers in the set S; S being a set of at least two prime numbers, P1...pk, where k is an integer greater than 1; e being a number; Sd being a proper subset of S; Na being the product of all of the numbers in the set Sd. 4. The method of claim 3, wherein, the step of generating the exponent e includes calculating the exponent e as a number that is relatively prime to the product of each distinct prime factor of N minus 1, (N1 — I)*...(Nj - 1) for distinct prime factors of N 1 to j, where j is the number of distinct prune factors in N, or choosing the exponent e as a small prime number. 5. A method for decrypting encrypted messages comprising the steps of: determining if a derived modulus Ndis a squarefree number, and if so, decrypting ciphertext C into message M using any method that produces a value equivalent to M = Cd modNd, where d is generated using the following steps: calculating the number Zd as the product of each prime factor of Nd minus 1, (Ndi - I)* ...(Ndj - 1) for prime factors of Na 1 to j, where j is the number of prime factors in Nd; generating the exponent d such that the following relationship is satisfied: e*d = 1 mod Zd. 6. The method according to claim 5, further including the step of: directly calculating M = Cd modNd. 7. The method according to claim 5, further including the steps of: calculating separate decryption exponents dndi- ..dndj for all prime factors of Nd 1 to j, where j is the number of prime factors in Nd so that the following relationship is satisfied for each member of Nd: e*dn(1i = 1 mod (Ndi - 1); and performing decryptions of the form Mi = Cflndi mod Ndi for all prime factors of Nd from 1 to j, where j is the number of prime factors in Nd, and then using the values of each Mi andNdi to reconstruct M. 8. The method of claim 7, wherein the values of each Mi and Ndi restore the plaintext message M using the Chinese Remainder Theorem and/or Garner's algorithm. 9. A method for decrypting encrypted messages, comprising the steps of: decrypting the ciphertext message C to the plaintext message M by determining if the derived modulus Nais squareful number, and if so; calculating separate decryption exponents dndt.-.dndj for all distinct prime factors of Nd 1 to j, where j is the number of distinct prime factors in Nd so that the following relationship is satisfied for each distinct member of Nd: e*dndi = 1 mod (Ndi - 1); for each distinct prime factor of Nd, Ndi, calculating a value bdi as the number of times that Ndi occurs as a prime factor in Na; calculating Mi for each distinct prime factor of Nd, N^; and using all values of Mi, Ndi, dndi, and bdi to restore the plaintext message M. 10. The method of claim 9, further including the steps of: using Hensel Lifting to calculate Mi for each distinct prime factor of Nd, Ndi. 11. The method of claim 9, further including using techniques such as the Chinese Remainder Theorem and/or Garner's algorithm to use all value of Mi, Ndi, dndi, and bdito restore the plaintext message M. 12. A public key cryptosystem where messages are decrypted using a set of prime numbers S and the public exponent e, and messages are encrypted using a modulus Np that is calculated as the product of a set of numbers that is a proper superset of S, and encryption occurs with, standard RSA methods using the public exponent e and the modulus Np. 13. A method for encrypting/decrypting messages, comprising the steps of: Encrypting a plaintext message M into a ciphertext message C using any method that produces a value equivalent to C = Me modNp, where 0 < M <N, such that the ciphertext C can be decrypted into the plaintext message M using e and the prime factors ofN N being the product of all of the numbers in the set S; S being a set of at least one prune number, P1...pk, where k is an integer greater than 0; Sp being a proper superset of S; Np being the product of all of the numbers in the set Sp; e being a number; 14. The method of claim 13, wherein the step of generating the exponent e includes calculating the exponent e as a number that is relatively prime to the product of each distinct prime factor of Np minus 1, (Npl - I)*...(NPj - 1) for distinct prime factors of Np 1 to j, where j is the number of distinct prime factors in Np. 15. The method of claim 13, wherein the step of generating the exponent e includes choosing the exponent e as a small prime number. 16. A method for decrypting encrypted messages, including the steps of: Decrypting the ciphertext message C to the plaintext message M by: determining if the derived modulus Nis squareful number; if so then, calculating separate decryption exponents dnl ...dnJ- for all distinct prime factors ofN 1 toj , where j is the number of distinct prime factors in N so that the following relationship is satisfied for each distinct member of N: e*dni = 1 mod (Ni - 1); for each distinct prime factor of N, Ni, calculating a value b; as the number of times that Ni occurs as a prime factor in N; calculating Mi for each distinct prime factors of N, Ni; and using each value of Mi, N;, bi and dm to restore the plaintext message M; 17. The method of claim 16, where Hensel Lifting is used to calculate Mj for each distinct prime factor of N, Ni. 18. The method of claim 16, further including using techniques such as the Chinese Remainder Theorem and/or Garner's algorithm to use all value of Mi, Ni, dni, and bito restore the plaintext message M. 19. A method of decrypting encrypted messages, including the steps of: Decrypting the ciphertext message C into the plaintext message M by: determining if the modulus Nis a squarefree number; and if so then, decrypting ciphertext C into message M using any method that produces a value equivalent to M = Cd mod N, where d is generated using the following steps: Calculating the number Z as the product of each prime factor of N minus 1, (N1 — I)*...(Nj - 1) for prime factors of N 1 to j, wherej is the number of prime factors in N; then generating the decryption exponent d such that the following relationship is satisfied: e*d = 1 mod Z; 20. The method according to claim 19, further including the step of: directly calculating M = Cd mod N. 21. The method according to claim 19, further including the steps of: calculating separate decryption exponents (I1...dj for all prime factors of N 1 to j, where j is the number of prime factors in Nso that the following relationship is satisfied for each member of N: e*dj = 1 mod (Ni - 1); and performing decryptions of the form Mi = Cdi modNi for all prime factors of N from 1 to j, where j is the number of prime factors in N, and then using the values of each Mj andNi to reconstruct M. 22. The method of claim 21 , wherein the values of each Mi and Ni reconstruct M using the Chinese Remainder Theorem and/or Garner's algorithm. 23. A method for encrypting/decrypting messages comprising the steps of: Encrypting a plaintext message M into a ciphertext message C using any method that produces a value equivalent to C = Me mod Np, where 0 < M <N, such that the ciphertext C can be decrypted into the plaintext message M using e and the prime factors of N. N being the product of all of the members of set S; S being a set of at least two numbers, P1...pk where k is an integer greater than 1 and all members of S are equal to ps, which is a prime number; Sp being a superset of S; Np being the product of all of the numbers in the set Sp; e being a number; 24. The method of claim 23, wherein the step of generating the exponent e further includes: Calculating the exponent e as a number that is relatively prime to the product of all of the distinct prime factors of Np minus 1, (Npl - 1)* ...( NPj - 1) for distinct prime factors of Np 1 to j, where j is the number of distinct prime factors in Np. 25. The method of claim 23, wherein the step of generating the exponent e includes choosing the exponent e as a small prime number. 26. A method of decrypting encrypted messages, including the steps of: Decrypting the ciphertext message C to the plaintext message M by: Calculating b as the number of times that the number ps occurs as a prime factor in N; Generating an exponent d such that the following equation is satisfied: e*d= 1 mod (ps - l); Using Hensel Lifting to transform C into M with d, ps, and b as input values. 27. A method for encrypting/decrypting messages, comprising the steps of: Encrypting a. plaintext message M into a ciphertext message C using any method that produces a value equivalent to C = Me mod Np, where 0 < M < p, such that the ciphertext C can be decrypted into the plaintext message M using e and p p being a prime number; S being a set containing only the number p; Sp being a superset of S; Np being the product of all members of the set Sp; e being a number; 28. The method of claim 27, wherein the step of generating th.e exponent e further includes: Calculating the exponent e as a number that is relatively prime to the product of each distinct prime factor ofNp minus 1, (Npl - I)*...( NPJ- - 1) for distinct prime factors ofNp 1 toj, where j is the number of distinct prime factors in Np. 29. The tnethod of claim 27, wherein the step of generating trie exponent e includes choosing the exponent e as a small prime number. 30. A method for decrypting encrypted messages, comprising the steps of: Decrypting using any method that produces a value equivalent to as M = Cd mod p, where d is generated using the following step: Calculating d such that the following equation is satisfied: e*d = l mod (p - l). 31. A method for establishing cryptographic communications, comprising the steps of: calculating a composite number N, which is formed from the product of distinct prime numbers S, pi, ...pk where k> 1. Encoding a plaintext message M, to a cipkertext C, where M corresponds to a number representative of a message and 0 < M < S; generating an exponent e; transforming said plaintext, M, into said ciphertext, C, where C is developed using any method that produces a value equivalent to C = Me mod N, such that ciphertext C can be decrypted into plaintext M using only e and S. 32. The method of claim 31 , wherein the step of generating the exponent e further includes: Calculating the exponent e as a number that is relatively prime to the product of each distinct prime factor of N minus 1, (N1 - 1),. ..( Nj - 1) for distinct prime factors of N 1 to j, where j is the number of distinct prime factors in N. 33. The method of claim 31 , wherein the step of generating the exponent e includes choosing the exponent e as a small prime number. 34. A method for decrypting encrypted messages, comprising the steps of: decoding the ciphertext message C to the plaintext message M, wherein said decoding comprises the step of: transforming said ciphertext message C to plaintext M, using any method that produces a value equivalent to M = Cd mod S, where d is generated using the following step: generating d such that e*d = 1 mod (S - 1); 35. A system for encrypting and decrypting electronic communications including a network of computers and/or computer-type devices, such as personal data assistants (PDAs), mobile phones and other devices, in particular mobile devices capable of communicating on the network; generating at least one private key and at least one public key, wherein the at least one private key is determined based upon any one of a multiplicity of prime numbers that when multiplied together produce N, which is the modulus for at least one of the public keys. 36. A method for public key decryption where less than all of the distinct prime factors of a number N are used to decrypt a ciphertext message C into plaintext message M, where encryption occurs with the public key {e, N} using any method that produces a value equivalent to C = Me modN. 37. A method for public key encryption with a public key {e, N} where a plaintext message M is encrypted into a ciphertext message C using any method that produces a value equivalent to C = Me mod (N*X), where N is the public modulus andX is any integer greater than 1. 38. A method for public key decryption of a message that has been encrypted with the public key {e, N} where a ciphertext message C is decrypted into a plaintext message M using any method that produces a value equivalent to M = Cd mod Nd, where Nd is the product of less than all of the prime factors of the public modulus N and d satisfies the equation e*d = 1 mod Z5 where Z is the product of each of the k prime factors of Nd minus 1, (pi - l)*-..(Pk— 1)- 39. A method for public key decryption of a message that has been encrypted using any method that produces a value equivalent to C = Me mod N, where a ciphertext message C is decrypted into a plaintext message M using any method that produces a value equivalent to M = Cd mod Nd, where Nd is the product of less than all of the prime factors of the public modulus N and d satisfies the equation e*d = 1 mod Z, where Z is the product of each ofthe kprime factors of Nd minus 1, Cp1 - l)*...(pk - I)- |
Design Examples Example #1 Generating prime rrumbers p and q as the members of set S, and calculating N = p*q. It is preferred that p is set to the minimum bit length, given existing security constraints and the expected message size, and that q is set to a bit length such that the bit length of N reaches its recommended size. Calculating e as a small prime number, such as 65537. Including p as the only member of the proper subset, Sd- Setting Nd = p. Calculating the private exponent d such that e*d = 1 mod (p - 1). Encrypting plaintext M into ciphertext C as C = Me modN5 where 0 < M <Nd- Decrypting ciphertext C into plaintext M as M = Cd mod Nd. Example #2 Generating prime number p as the only member of set S, and setting N = p. It is preferred that p is set to the minimum bit length given existing security constraints and the expected message size. Calculating e as a small prime number, such as 65537. Creating the set Sp as a proper superset of set S containing members p and q, and calculating Np = pq. It is preferred that q is large enough so that the bit length of the Np reacbies its recommended size. Calculating the private exponent d such that e*d = 1 mod (p - 1). Encrypting plaintext M into ciphertext C as C = Me modNp, where 0 < M <N. Decrypting ciphertext C into plaintext M as M = Cd mod N. Example #3 Generating prime number p and choosing the members of set S as {p,p}, and setting N =
It is preferred that p is set to the minimum bit length given existing security constraints and expected message size. Calculating e as a small prime number, such as 65537. Creating the set Sp as a proper superset of set S containing members {p,p,q}, and calculating Np = p2q. It is preferred that q is large enough so that the bit length of the Np reach.es its recommended size. Calculating the private exponent d such that e*d = 1 mod (p - 1). Encrypting plaintext M into ciphertext C as C = Me modNp, where 0 < M <N. Decrypting ciphertext C into plaintext M by: Precomputing the value e_inv_p = e'1 mod p; Calculating Q3 = C mod p2; Calculating Mi = Csα " ' modp; Calculating Ko = (M1*CS) modp; Calculating A = (C - K06) modp2; Calculating M2 = (Mi*A) modp2; Calculating M3 = (M2*e_inv_p) modp2; Decoding plaintext message M = (M3-+- Ko) mod p2; Example #4 Generating distinct prime numbers p and q, and choosing the members of set S as {p,q}, and setting N = p*q. Calculating e as a small prime number, such as 65537. Creating the set Sp as a proper superset of set S containing members {p,q,r}, and calculating Np = pqr, with q chosen so that that N is a squarefree number (all prime factors are distinct). Calculating the private exponent d such that e*d = 1 mod (p — l)(q- 1). Encrypting plaintext M into ciphertext C as C = Me modNp, where 0 < M < Np. Decrypting ciphertext C into plaintext M by: Calculating Mp = M mod p; Calculating Mq = M modp; Calculating p_inv_q = p"1 mod q; Calculating V = (Mq- Mp) mod q; Calculating Vi = V*p_inv_q mod q; Calculating Mi = V*p modN; Calculating plaintext M = (Mi + Mp) modN; Example #5 Being provided a public key {e, N} ; Generating a number X as a large prime number; Encrypting a plaintext message M into a ciphertext message C as: C= Me mod (NT*X); Provided that M < X and M < N, decryption can occur in either of two ways: M = Cd mod N, using the private key that corresponds to the public key {e, N} Or M = Cdχ mod X, where d.x is calculated such that e* dx = 1 mod (X- I) Certain modifications and improvements will occur to those skilled in the art upon a reading of the foregoing description. AU modifications and improvements have been deleted herein for the sake of conciseness and readability but are properly within the scope of the following claims.
Next Patent: INTERFERENCE LIMITATION FOR RETRANSMISSIONS