One-way transformation of information

• US 4,841,570 A
• Filed: 05/11/1987
• Issued: 06/20/1989
• Est. Priority Date: 05/11/1987
• Status: Expired due to Fees

• Current Assignee: United States Of America As Represented By The Department Of Energy
• Original Assignee: United States Department of Energy (Government of the United States of America)
• Inventors: Cooper, James A.
• Primary Examiner(s): Buczinski, Stephen C.
• Assistant Examiner(s): GREGORY, BERNARR E
• Application Number:
  US07/048,433
• Time in Patent Office: 771 Days
• Field of Search: 380/28, 380/30, 380/50, 380/49
• US Class Current: 380/30
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems

Abstract

Method and apparatus are provided for one-way transformation of data according to multiplication and/or exponentiation modulo a prime number. An implementation of the invention permits the one way residue transformation, useful in encryption and similar applications, to be implemented by n-bit computers substantially with no increase in difficulty or complexity over a natural transformation thereby, using a modulus which is a power of two.

Claims

1. A method for one-way transformation of data to generate an encrypted form thereof by obtaining a modulo-k representation of a product of at least first and second numbers in an n-bit computer where 2ⁿ ≠

k, said computer having a multiplying apparatus including an n-bit accumulator register and an n-bit carry register, comprising the steps of;

inputting a first number G from an input source to the computer,

obtaining a second number H,

using said multiplying apparatus to obtain a product J-G*H,

storing said product in said accumulator and carry registers,

transforming the product to obtain a unique one-way encrypted transform thereof,

said transforming step comprising the step of obtaining a modulo-k representation, J_k =(G*H)mod k, of the product by performing the further steps of;

comparing the contents of said accumulator and carry registers to determine a relation therebetween,

selecting a function dependent on the results of said comparing step,

applying the selected function to the contents of said carry register,

generating signals representative of the selected function of the contents of said carry register,

transferring said generated signals to the accumulator register,

altering said accumulator register in response to said signals transferred thereto,

generating signals representative of the altered contents of said accumulator register and

outputting said signals representative of the altered contents of said accumulator register as the transformed representation J_k.

2. A method as recited in claim 1 wherein said number k differs by an integer d from a power of two, 2^p, and comprising the further step of disabling n-p bits of said accumulator and carry registers, if n>

p.

3. A method as recited in claim 2 wherein said number k is greater than said power of 2 by said integer d, said selecting step comprises selecting a decrementing function and said altering step comprises the step of decrementing said accumulator and carry registers until the contents of said carry register are zero, thereby subtracting the contents of said carry register from the contents of said accumulator register.

4. A method as recited in claim 2 wherein n=p, said number k is a prime number one more than 2ⁿ, said comparing step comprises the step of comparing the contents of said accumulator and carry registers to determine which register contains a larger number, and said selecting and generating steps comprise the step of generating signals representative of the contents of said carry register if the contents of said accumulator register are greater than or equal to the contents of said carry register.

5. A method as recited in claim 4 wherein said selecting and generating steps comprise the step of generating signals representative of a number one less than the contents of said carry register if the contents of said carry register are greater than or equal to one more than the contents of said accumulator register, and

wherein said altering step comprises the step of decrementing said accumulator register thereby subtracting one less than the contents of said carry register from the contents of said accumulator register.

6. A method as recited in claim 2 wherein said number k is less than said power of 2 by said integer d, said selecting step comprises selecting a combined incrementing and decrementing function, and said altering step comprises the step of incrementing said accumulator register while decrementing said carry register until the contents of said carry register are zero, thereby adding the contents of said carry register to the contents of said accumulator register.

7. A method as recited in claim 6 wherein p=n-t, t an integer, said number k is a prime number one less than 2^p, and said comparing step comprises the step of comparing the contents of said accumulator and carry registers to determine whether a sum of said contents is or is not less than k and, if the sum is not less than k, incrementing said accumulator register upon noting an overflow when the contents of said carry register are zero.

8. A method as recited in claim 1 wherein said step of using said multiplying apparatus to obtain a product comprises the step of obtaining an exponential product of at least said first and second numbers.

9. A method for encrypting data by obtaining a truncated modulo-k representation of an exponential product of first and second numbers in an n-bit computer where 2ⁿ ≠

k, said computer having a multiplying apparatus including an n-bit accumulator register and an n-bit carry register, comprising the steps of;

inputting a first number G from an input source to the computer,

obtaining a second number H,

using said multiplying apparatus to obtain an exponential product J=G^H of said first and second numbers,

storing a truncated portion of said exponential product in said accumulator and carry registers,

transforming the exponential product to obtain a unique one-way encrypted transform thereof,

said transforming step comprising the step of obtaining a modulo-k representation, J_k =(G^H)mod k, of the exponential product by performing the further steps of;

comparing the contents of said accumulator and carry registers to determine a relation therebetween,

selecting a function dependent on the results of said comparing step,

applying the selected function to the contents of said carry register,

generating signals representative of the selected function of the contents of said carry register,

transferring said generated signals to the accumulator register,

altering said accumulator register in response to said signals transferred thereto,

generating signals representative of the altered contents of said accumulator register and

outputting said signals representative of the altered contents of said accumulator register as the transformed representation J_k.

10. A method as recited in claim 9 wherein said number k differs by an integer d from a power of two, 2^p, and comprising the further step of disabling n-p bits of said accumulator and carry registers when n>

p.

11. A method as recited in claim 10 wherein said number k is greater than said power of 2 by said integer d, said selecting step comprises selecting a decrementing function, and said altering step comprises the step of decrementing said accumulator and carry registers until the contents of said carry register are zero, thereby subtracting the contents of said carry register from the contents of said accumulator register.

12. A method as recited in claim 10 wherein n=p, said number k is a prime number one more than 2ⁿ, said comparing step comprises the step of comparing the contents of said accumulator and carry registers to determine which register contains a larger number, and said selecting and generating steps comprise the step of generating signals representative of the contents of said carry register if the contents of said accumulator register are greater than or equal to the contents of said carry register.

13. A method as recited in claim 12 wherein said selecting and generating steps comprise the step of generating signals representative of a number one less than the contents of said carry register if the contents of said carry register are greater than or equal to one more than the contents of said accumulator register, and

wherein said altering step comprises the step of decrementing said accumulator register thereby subtracting one less than the contents of said carry register from the contents of said accumulator register.

14. A method as recited in claim 10 wherein said number k is less than said power of 2 by said integer d, said selecting step comprises selecting a combined incrementing and decrementing function, and said altering step comprises the step of incrementing said accumulator register while decrementing said carry register until the contents of said carry register are zero, thereby adding the contents of said carry register to the contents of said accumulator register.

15. A method as recited in claim 14 wherein p=n-t, t an integer, said number k is a prime number one less than 2^p, and said comparing step comprises the step of comparing the contents of said accumulator and carry registers to determine whether a sum of said contents is or is not less than k and, if the sum is not less than k, incrementing said accumulator register upon noting an overflow when the contents of said carry register are zero.

16. Apparatus for one-way transformation of data to generate an encrypted form thereof as a modulo-k representation of a product of first and second numbers in an n-bit computer means where 2ⁿ ≠

k and k differs by an integer d from a power of two 2^p, p≦

n, said computer means having a multiplying apparatus, an n-bit accumulator register and an n-bit carry register, comprising;

means for inputting first and second numbers G and H to said multiplying apparatus to obtain a truncated product J=G*H in said accumulator and carry registers,

said computer means including modulo residue generating means for obtaining a modulo-k representation, J_k=(G*H)mod k, of the product, including;

comparing means for comparing the contents of said accumulator and carry registers to determine a relation therebetween,

altering means for altering the contents of said accumulator register in response to the contents of said carry register according to the relation determined between the contents of said accumulator and carry registers,

signal generating means for generating signals representative of the altered contents of said accumulator register and

outputting means for outputting said signals representative of the altered contents of said accumulator register as the modulo-k representation J_k.

17. Apparatus as recited in claim 16 further comprising selecting means for selecting a function dependent on the relation determined by said comparing means,

applying means for applying the selected function to the contents of said carry register,

second signal generating means for generating signals representative of the selected function of the contents of said carry register, and

transferring means for transferring said generated signals to the accumulator register.

18. Apparatus as recited in claim 17 wherein said number k is greater than said power of 2 by said integer d, said selecting means being operable for selecting a decrementing function, and said altering means comprises decrementing means for decrementing said accumulator and carry registers until the contents of said carry register are zero, thereby subtracting the contents of said carry register from the contents of said accumulator register.

19. Apparatus as recited in claim 17 wherein n=p, said number k is a prime number one more than 2ⁿ, said comparing means comprises means for comparing the contents of said accumulator and carry registers to determine which register contains a larger number, and said second signal generating means is operable for generating signals representative of the contents of said carry register if the contents of said accumulator register are greater than or equal to the contents of said carry register.

20. Apparatus as recited in claim 19 wherein said second generating means is further operable for generating signals representative of a number one less than the contents of said carry register if the contents of said carry register are greater than or equal to one more than the contents of said accumulator register, and

wherein said altering means comprises decrementing means for decrementing said accumulator register thereby subtracting one less than the contents of said carry register from the contents of said accumulator register.

21. Apparatus as recited in claim 17 wherein said number k is less than said power of 2 by said integer d, said selecting means being operable for selecting a combined incrementing and decrementing function, and wherein said altering means comprises means for incrementing said accumulator register while decrementing said carry register until the contents of said carry register are zero, thereby adding the contents of said carry register to the contents of said accumulator register.

22. Apparatus as recited in claim 21 wherein p=n-t, t an integer, said number k is a prime number one less than 2^p, and said comparing means comprises means for comparing the contents of said accumulator and carry registers to determine whether a sum of said contents is or is not less than k and, if the sum is not less than k, for incrementing said accumulator register upon noting an overflow when the contents of said carry register are zero.