Public key cryptographic system and method

• US 5,142,579 A
• Filed: 01/29/1991
• Issued: 08/25/1992
• Est. Priority Date: 01/29/1991
• Status: Expired due to Fees

• Current Assignee: Walter M. Anderson
• Original Assignee: Walter M. Anderson
• Inventors: Anderson, Walter M.
• Primary Examiner(s): Buczinski, Stephen C.
• Application Number:
  US07/647,447
• Time in Patent Office: 574 Days
• Field of Search: 380/21, 380/30, 380/43, 380/45, 380/46
• US Class Current: 380/30
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/16 Obfuscation or hiding, e.g. involving white box
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme

Abstract

A public key cryptographic system and method includes an insecure communications channel connecting at least two communicating complexes, a sender and a receiver. The sender possesses an encoding device and the receiver possesses a decoding device. The sender uses a public key that may be known by an unauthorized receiver and that is generated by random processes known only to the receiver to encrypt a plain text destined for the receiver. The transformation of plain text to encrypted text using the public key is easily performed, but the inversion of that transformation using only the public key information and the knowledge of the operations of encryption and decryption is extremely difficult and computationally infeasible. The receiver uses the knowledge of the randomly generated transformation set components (the private key) to easily and incrementally invert the encrypted text and recover the plain text. The inversion of the encryption process using the public key is known to be computationally "hard" and an NP-complete problem.

Claims

1. A method of communicating securely over an insecure communications channel including the steps of:

A. generating a private key at a receiver that consists of a multiplicity of transformation steps of a plain text variable vector of fixed, but arbitrary length, wherein all steps are under the control of a random number source and wherein all operations of addition, subtraction, and multiplication are performed modulo a prime number, P, and wherein each transformation step comprises;

a. multiplying a linear matrix by an input vector to yeild an intermediate vector, wherein the linear matrix contains its non-zero elements only in a multiplicity of submatrices along its principal diagonal and each submatrix possesses an inverse;

b. substituting the input vector in a multiplicity of substitution vectors in which a variable of the input vector may appear more than once or not at all and where each substitution vector location contains only variables of the input vector that lie in locations entirely above the submatrix of the linear matrix to which they correspond;

c. multiplying the substitution vectors by each other and a first constant vector to yield a product vector;

d. adding the intermediate vector to the product vector and to a second constant vector to yield a sum vector;

e. permuting the sum vector with a permutation vector to yield an output vector in which each element of the sum vector appears once, but in a usually different position than in the sum vector;

f. generating an inverse linear matrix as the inverse of the linear matrix;

g. generating an inverse permutation as the inverse of the permutation vector;

B. hiding the private key by generating a public key at the receiver that represents the private key as a set of non-linear polynomial equations modulo the prime P by symbolically solving the multiplicity of transformation steps in terms of the plain text variable vector and reducing the set of non-linear polynomial equations to simplest terms;

C. transmitting the public key to a sender via an insecure key channel;

D. encrypting a plain text vector at the sender according to the public key by substituting the plain text vector into the set of non-linear polynomial equations to produce a ciphertext;

E. transmitting the ciphertext via an insecure communications channel to the receiver;

F. decrypting the ciphertext at the receiver with the private key with a private key decryption process to produce the plain text thereby achieving secure communications;

wherein the private key decryption process operates by reversing the multiplicity of transformation steps of the private key in a reverse order to which they were applied and wherein reversing a transformation step comprises;

a. reversing the permutation of an input vector using the inverse permutation to create an inverse permutation vector;

b. starting from the top of the inverse linear matrix and considering each submatrix in turn;

c. subtracting from the inverse permutation vector the sum of the product of the first constant vector and the multiplicity of substitutions of an output vector and the second constant vector to create an intermediate subvector, wherein operations are restricted to the range of the current submatrix;

d. multiplying the intermediate subvector by the submatrix of the inverse linear matrix to create a corresponding subvector of the output vector;

e. repeating the steps F.c. and F.d. until all of the inverse linear matrix has been exhausted and the output vector contains the reversion of the transformation step.

2. A method of claim 1 in which the prime, P, is chosen as P=2 whereby all of the operations of multiplication, addition, and subtraction modulo the prime reduce to logical AND, XOR and XOR operations respectively.

3. An apparatus for communicating securely over an insecure communications channel comprising:

A. a means of generating a private key at a receiver that consists of a multiplicity of transformation means of a plain text variable vector of fixed, but arbitrary length, wherein all means are under the control of a random number source means and wherein all means of addition, subtraction, and multiplication are performed modulo a prime number, P, and wherein each transformation means comprises;

a. a means of multiplying a linear matrix by an input vector to yield an intermediate vector, wherein the linear matrix contains its non-zero elements only in a multiplicity of submatrices along its principal diagonal and each submatrix possesses an inverse;

b. a means for substituting the input vector in a multiplicity of substitution vectors in which a variable of the input vector may appear more than once or not at all and where each substitution vector location contains only variables of the input vector that lie in locations entirely above the submatrix of the linear matrix to which they correspond;

c. a means of multiplying the substitution vectors by each other and a first constant vector to yield a product vector;

d. a means for adding the intermediate vector to the product vector and to a second constant vector to yield a sum vector;

e. a means for permuting the sum vector with a permutation vector to yield an output vector in which each element of the sum vector appears once, but in a usually different position than in the sum vector;

f. a means for generating an inverse linear matrix as the inverse of the linear matrix;

g. a means for generating an inverse permutation as the inverse of the permutation vector;

B. a means for hiding the private key by generating a public key at the receiver that represents the private key as a set of non-linear polynomial equations modulo the prime P by a means for symbolically solving the multiplicity of transformation steps in terms of the plain text variable vector and a means for reducing the set of non-linear polynomial equations to simplest terms;

C. a means for transmitting the public key to a sender via an insecure key channel;

D. a means for encrypting a plain text vector at the sender according to the public key by a means for substituting the plain text vector into the set of non-linear polynomial equations to produce a ciphertext;

E. a means for transmitting the ciphertext via an insecure communications channel to the receiver;

F. a means for decrypting the ciphertext at the receiver with the private key with a private key decryption means to produce the plain text thereby achieving secure communications;

wherein the private key decryption means operates by reversing the multiplicity of transformation means of the private key in a reverse order to which they were applied and wherein reversing a transformation means comprises;

a. a means of reversing the permutation of an input vector using the inverse permutation to create an inverse permutation vector;

b. a means for starting from the top of the inverse linear matrix and considering each submatrix in turn;

c. a means of subtracting from the inverse permutation vector the sum of the product of the first constant vector and the multiplicity of substitutions of an output vector and the second constant vector to create an intermediate subvector, wherein operations are restricted to the range of the current submatrix;

d. a means of multiplying the intermediate subvector by the submatrix of the inverse linear matrix to create a corresponding subvector of the output vector;

e. a means of repeating the means for subtracting and the means for multiplying until all of the inverse linear matrix has been exhausted and the output vector contains the reversion of the transformation step.

4. An apparatus of claim 3 in which the prime, P, is chosen as P=2 whereby all of the means of multiplication, addition, and substraction modulo the prime reduce to means of performing logical AND, XOR, and XOR means respectively.

5. A method of communicating securely over an insecure communications channel in which authenticity of a message is provided including the steps of:

A. generating a private key of the receiver at a receiver that consists of a multiplicity of transformation steps of a plain text variable vector of fixed, but arbitrary length, wherein all steps are under the control of a random number source and wherein all operations of addition, subtraction, and multiplication are performed modulo a prime number, P, and wherein each transformation step comprises;

a. multiplying a linear matrix by an input vector to yield an intermediate vector, wherein the linear matrix contains its non-zero elements only in a multiplicity of submatrices along its principal diagonal and each submatrix possesses an inverse;

b. substituting the input vector in a multiplicity of substitution vectors in which a variable of the input vector may appear more than once or not at all and where each substitution vector location contains only variables of the input vector that lie in locations entirely above the submatrix of the linear matrix to which they correspond;

c. multiplying the substitution vectors by each other and a first constant vector to yield a product vector;

d. adding the intermediate vector to the product vector and to a second constant vector to yield a sum vector;

e. permuting the sum vector with a permutation vector to yield an output vector in which each element of the sum vector appears once, but in a usually different position than in the sum vector;

f. generating an inverse linear matrix as the inverse of the linear matrix;

g. generating an inverse permutation as the inverse of the permutation vector;

B. hiding the private key of the receiver by generating a public key of the receiver at the receiver that represents the private key of the receiver as a set of non-linear polynomial equations modulo the prime P by symbolically solving the multiplicity of transformation steps in terms of the plain text variable vector and reducing the set of non-linear polynomial equations to simplest terms;

C. transmitting the public key of the receiver to a sender via an insecure key channel;

D. generating a private key of the sender at the sender via steps that are the same as the generating of the private key of the receiver but using a different random number source;

E. hiding the private key of the sender by generating a public key of the sender at the sender that represents the private key of the sender as a set of non-linear polynomial equations modulo the prime P by symbolically solving the multiplicity of transformation steps in terms of the plain text variable vector and reducing the set of non-linear polynomial equations to simplest terms;

F. transmitting the public key of the sender to the receiver via the insecure key channel;

G. encrypting a plain text vector at the sender as a first step, according to the private key of the sender applied as the inverse of the multiplicity of transformation steps of the private key of the sender in reverse order to produce an intermediate ciphertext vector wherein reversing a transformation step consist of;

a. reversing the permutation of an input vector using the inverse permutation to create an inverse permutation vector;

b. starting from the top of the inverse linear matrix and considering each submatrix in turn;

c. subtracting from the inverse permutation vector the sum of the product of the first constant vector and the multiplicity of substitutions of an output vector and the second constant vector to create an intermediate subvector, wherein operations are restricted to the range of the current submatrix;

d. multiplying the intermediate subvector by the submatrix of the inverse linear matrix to create a corresponding subvector of the output vector;

e. repeating the steps G.c. and G.d. until all of the inverse linear matrix has been exhausted and the output vector contains the reversion of the transformation step;

H. completing the encryption of the plain text as a second step according to the public key of the receiver by substituting the intermediate ciphertext vector into the set of non-linear polynomial equations of the public key of the receiver to produce the ciphertext;

I. transmitting the ciphertext via an insecure communications channel to the receiver;

J. decrypting the ciphertext at the receiver as a first step, according to the private key of the receiver with a private key decryption process to produce the intermediate ciphertext vector;

wherein the private key decryption process operates by reversing the multiplicity of transformation steps of the private key of the receiver in a reverse order to which they were applied and wherein reversing a transformation step comprises;

a. reversing the permutation of an input vector using the inverse permutation to create an inverse permutation vector;

b. starting from the top of the inverse linear matrix and considering each submatrix in turn;

c. subtracting from the inverse permutation vector the sum of the product of the first constant vector and the multiplicity of substitutions of an output vector and the second constant vector to create an intermediate subvector, wherein operations are restricted to the range of the current submatrix;

d. multiplying the intermediate subvector by the submatrix of the inverse linear matrix to create a corresponding subvector of the output vector;

e. repeating the steps J.c. and J.d. until all of the inverse linear matrix has been exhausted and the output vector contains the reversion of the transformation step; and

as a second step,

K. completing the decryption of the ciphertext according to the public key of the sender by substituting the intermediate ciphertext vector into the set of non-linear polynomial equations of the public key of the sender to produce the plain text and thereby achieving secure communications since only the receiver possessing the private key of the receiver can recover the intermediate ciphertext vector and authenticating the message since only the sender possessing the private key of the sender can generate the intermediate ciphertext vector that is decrypted to the plain text with the public key of the sender.

6. A method of claim 5 in which the prime, P, is chosen as P=2 whereby all of the operations of multiplication, addition, and subtraction modulo the prime reduce to logical AND, XOR, and XOR operations respectively.

7. An apparatus for communicating securely over an insecure communications channel in which authenticity of a message is provided and comprising:

A. a means for generating a private key of the receiver at a receiver that consists of a multiplicity of transformation means of a plain text variable vector of fixed, but arbitrary length, wherein all means are under the control of a random number source means and wherein all means of addition, subtraction, and multiplication are performed modulo a prime number, P, and wherein each transformation means comprises;

a. a means of multiplying a linear matrix by an input vector to yield an intermediate vector, wherein the linear matrix contains its non-zero elements only in a multiplicity of submatrices along its principal diagonal and each submatrix possesses an inverse;

b. a means for substituting the input vector in a multiplicity of substitution vectors in which a variable of the input vector may appear more than once or not at all and where each substitution vector location contains only variables of the input vector that lie in locations entirely above the submatrix of the linear matrix to which they correspond;

c. a means of multiplying the substitution vectors by each other and a first constant vector to yield a product vector;

d. a means for adding the intermediate vector to the product vector and to a second constant vector to yield a sum vector;

e. a means for permuting the sum vector with a permutation vector to yield an output vector in which each element of the sum vector appears once, but in a usually different position than in the sum vector;

f. a means of generating an inverse linear matrix as the inverse of the linear matrix;

g. a means of generating an inverse permutation as the inverse of the permutation vector;

B. a means for hiding the private key of the receiver by generating a public key of the receiver at the receiver that represents the private key of the receiver as a set of non-linear polynomial equations modulo the prime P by a means for symbolically solving the multiplicity of transformation means in terms of the plain text variable vector and a means for reducing the set of non-linear polynomial equations to simplest terms;

C. a means for transmitting the public key of the receiver to a sender via an insecure key channel;

D. a means for generating a private key of the sender at the sender via means that are the same as the generating of the private key of the receiver but using a different random number source means;

E. a means of hiding the private key of the sender by generating a public key of the sender at the sender that represents the private key of the sender as a set of non-linear polynomial equations modulo the prime P by a means for symbolically solving the multiplicity of transformation steps in terms of the plain text variable vector and a means of reducing the set of non-linear polynomial equations to simplest terms;

F. a means for transmitting the public key of the sender to the receiver via the insecure key channel;

G. a means for encrypting a plain text vector at the sender by a first means, according to the private key of the sender applied as the inverse of the multiplicity of transformation means of the private key of the sender in reverse order to produce an intermediate ciphertext vector wherein reversing a transformation means comprises;

a. a means of reversing the permutation of an input vector using the inverse permutation to create an inverse permutation vector;

b. a means for starting from the top of the inverse linear matrix and considering each submatrix in turn;

c. a means for subtracting from the inverse permutation vector the sum of the product of the first constant vector and the multiplicity of substitutions of an output vector and the second constant vector to create an intermediate subvector, wherein operations are restricted to the range of the current submatrix;

d. a means for multiplying the intermediate subvector by the submatrix of the inverse linear matrix to create a corresponding subvector of the output vector;

e. wherein the subtracting of the means for subtracting and the multiplying of the means for multiplying are repeated until all of the inverse linear matrix has been exhausted and the output vector contains the reversion of the transformation step;

H. a means of completing the encryption of the plain text by a second means according to the public key of the receiver with a means for substituting the intermediate ciphertext vector into the set of non-linear polynomial equations of the public key of the receiver to produce the ciphertext;

I. a means for transmitting the ciphertext via an insecure communications channel to the receiver;

J. a means for decrypting the ciphertext at the receiver as a third means, according to the private key of the receiver with a private key decryption process to produce the intermediate ciphertext vector;

wherein the private key decryption process operates with a means for reversing the multiplicity of transformation means of the private key of the receiver in a reverse order to which they were applied and wherein reversing a transformation means comprises;

a. a means of reversing the permutation of an input vector using the inverse permutation to create an inverse permutation vector;

b. a means for starting from the top of the inverse linear matrix and considering each submatrix in turn;

c. a means for subtracting from the inverse permutation vector the sum of the product of the first constant vector and the multiplicity of substitutions of an output vector and the second constant vector to create an intermediate subvector, wherein operations are restricted to the range of the current submatrix;

d. a means for multiplying the intermediate subvector by the submatrix of the inverse linear matrix to create a corresponding subvector of the output vector;

e. a means for repeating the means for subtracting and the means for multiplying until all of the inverse linear matrix has been exhausted and the output vector contains the reversion of the transformation step; and

as a fourth means,

K. a means for completing the decryption of the ciphertext according to the public key of the sender with a means for substituting the intermediate ciphertext vector into the set of non-linear polynomial equations of the public key of the sender to produce the plain text and thereby achieving secure communications since only the receiver possessing the private key of the receiver can recover the intermediate ciphertext vector and authenticating the message since only the sender possessing the private key of the sender can generate the intermediate ciphertext vector that is decrypted to the plain text with the public key of the sender.

8. An apparatus of claim 7 in which the prime, P, is chosen as P=2 whereby all of the means of multiplications, addition, and subtraction modulo the prime reduce to means of performing logical AND, XOR, and XOR means respectively.

9. A method for generating private and public keys for use in communications systems that assure secure communications or secure and authenticated communications over an insecure channel that comprises:

A. creating a reversible private key transformation that includes a multiplicity of transformation steps performed solely by arithmetic operations of addition, subtraction, and multiplication modulo a prime, P, where each transformation step comprises;

a. substituting in a multiplicity of substitution vectors a plain text vector, when the substitution is of the plain text vector, and an intermediate vector, when the substitution is of any one of a plurality of intermediate vectors;

b. creating a multiplicity of linear matrix vectors as the products of a multiplicity of linear matrices and the plain text vector, when the multiplication is by the plain text vector, and any one of said intermediate vectors, when the multiplication is by said any one of said plurality of intermediate vectors;

c. permuting the plain text vector, when the permutation is of the plain text vector, and any one of said intermediate vectors, when the permutation is of any one of said plurality of intermediate vectors, in a multiplicity of permutation vectors;

d. combining the substitution vectors, the linear matrix vectors, and the permutation vectors using the operations of addition, subtraction, and multiplication of elements of said vectors in a manner that allows the recovery of said any one of said plurality of intermediate vectors and the plain text vector;

B. hiding the private key transformation in a public key by representing the private key transformation as a set of non-linear polynomial equations modulo the prime P by symbolically solving the multiplicity of transformation steps in terms of the plain text variable vector and reducing the set of non-linear equations to a minimum sum of products canonic form.

10. A method of claim 9 in which the prime, P, is chosen as P=2 whereby all of the operations of multiplication, addition, and subtraction modulo the prime reduce to logical AND, XOR, and XOR operations respectively.

11. An apparatus generating private and public keys for use in communications systems that assure secure communications or secure and authenticated communications over an insecure channel that comprises:

A. a means for creating a reversible private key transformation that includes a multiplicity of transformation means performed solely by arithmetic means of addition, subtraction, and multiplication modulo a prime, P, where each transformation means comprises;

a. a means for substituting in a multiplicity of substitution vectors a plain text vector, when the substitution is of the plain text vector, and an intermediate vector, when the substitution is of any one of a plurality of intermediate vectors;

b. a means for creating a multiplicity of linear matrix vectors as the products of a multiplicity of linear matrices and the plain text vector, when the multiplication is by the plain text vector, and any one of said intermediate vectors, when the multiplication is by said any one of said plurality of intermediate vectors;

c. a means of permuting the plain text vector, when the permutation is of the plain text vector, and any one of said intermediate vectors, when the permutation is of any one of said intermediate vectors, in a multiplicity of permutation vectors;

d. a means of combining the substitution vectors, the linear matrix vectors, and the permutation vectors using the operations of addition, subtraction, and multiplication of elements of said vectors in a manner that allows the recovery of said any one of said plurality of intermediate vectors and the plain text vector;

B. a means for hiding the private key transformation in a public key by representing the private key transformation as a set of non-linear polynomial equations modulo the prime P with a means for symbolically solving the multiplicity of transformation means in terms of the plain text variable vector and a means for reducing the set of non-linear equations to a minimum sum of products canonic form.

12. An apparatus of claim 11 in which the prime, P, is chosen as P=2 whereby all of the means of multiplication, addition, and subtraction modulo the prime reduce to means of performing logical AND, XOR, and XOR means respectively.