One-way transformation of information
First Claim
Patent Images
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 2n ≠
- 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, Jk =(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 andoutputting said signals representative of the altered contents of said accumulator register as the transformed representation Jk.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
22 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 2n ≠
- 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, Jk =(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 Jk. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
- k, said computer having a multiplying apparatus including an n-bit accumulator register and an n-bit carry register, comprising the steps of;
-
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 2n ≠
- 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=GH 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, Jk =(GH)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 Jk. - View Dependent Claims (10, 11, 12, 13, 14, 15)
- k, said computer having a multiplying apparatus including an n-bit accumulator register and an n-bit carry register, comprising the steps of;
-
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 2n ≠
- k and k differs by an integer d from a power of two 2p, 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, Jk=(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 Jk. - View Dependent Claims (17, 18, 19, 20, 21, 22)
- k and k differs by an integer d from a power of two 2p, p≦
Specification