Since 1800 the most widely-used methods for secret communications have been Secret Key encryption methods. Messages are encrypted using a secret key known only to the communicating parties. These keys needed to be distributed to all of the communicating parties, and kept strictly secret from all unauthorized third parties.
Since about 1975 new methods for secret communications, called Public Key methods, have been developed. Each party has a public key, which anyone may use to send them a secret message, and a private key which is used to read the message. The security comes from the presumption that, given a public encryption key, it is not computationally feasible to determine the private decryption key. The use of public key cryptography requires the distribution of the public keys, typically by establishing a key distribution authority or network.
The main difficulty with both Secret Key encryption and Public Key encryption is the distribution of the keys. A great deal of effort has gone into solving this problem. U.S. Pat. Nos. 4,200,770; 5,159,632; 5,271,061; 5,987,130; 6,212,279; 6,363,154; 6,377,689; 6,987,855; 6,993,136; 7,020,282; 7,120,696; 7,149,308; and 7,156,299 all deal with various proposed solutions to the key-distribution problem.
Another, more-recently developed class of methods for secret communications, called Private Key methods eliminate the key distribution problem altogether. For each message each party independently chooses a private, secret key which is used to encrypt the message. The inverse of this secret key is used to decrypt the message. These private keys are never distributed or divulged to anyone else, so that the sender does not know the receiver's private key, and vice-versa. After each message has been sent, the private keys are discarded and never used again.
Private Key methods use an exchange of 3 transmitted messages, to be designated here as SM, RSM and RM. The unencrypted message to be sent is designated as M. The sender forms the first transmitted message SM by encrypting the original, or plaintext, message M with the sender's private encryption function S (that is, the fixed encryption function using the sender's private key). So, the transmitted message denoted SM, is formed by applying the encryption function S to the message M. The receiver forms the second transmitted message RSM by encrypting SM with the receiver's secret encryption function R. This process is sometimes called superencryption. The message SM encrypted with R may be denoted RSM. This message is then sent back to the sender. The sender forms the third transmitted message RM by decrypting RSM using the sender's private decryption function S′ which is the inverse of S. This strips off the first encryption, leaving RM encrypted with only the receiver's encryption function.
This procedure will result in the correct transmission of the message if the sender's encryption function and the receiver's encryption function commute. That is, RSM would be the same as SRM. Then when the sender applies the decryption function S′ it produces S′RSM=S′SRM=RM. This third message is then sent back to the receiver who can remove the encryption by applying the receiver's private decryption function R′ resulting in R′RM=M, which is the plaintext message.
This exchange of 3 messages is commonly called the Three-Pass Protocol. It may be described abstractly as follows: Let ES, ER, DS and DR be the sets of sender encryption functions, receiver encryption functions, sender decryption functions and receiver decryption functions, respectively. For each encryption function eS in ES or eR in ER there will be a corresponding decryption function dS in DS or dR in DR. Let eS and eR be any sender and receiver encryption functions, and let dS and dR, be their corresponding sender and receiver decryption functions. The three messages in the three-pass protocol will be eSM, eReSM and dSeReSM. The final decrypted message will be dRdSeReSM. The requirement for decrypting the message is that dRdSeReSM must be identical to M. This would be true if the encryption functions commuted with each other, that is, if eReSM were the same as eSeRM for all eS in ES and eR in ER. Similarly, it would be true if the decryption functions commuted with one another, or if the sender's decryption function commuted with the receiver's encryption function. (There are other possibilities. For example, the receiver's encryption function could consist of two steps, one of which commutes with the sender's encryption function, and one of which commutes with the sender's decryption function, for example eR=fRgR so that dRdSeReSM=dRdSfRgReSM=dRfRdSeSgRM=dRfRgRM=dReRM=M. This sort of commutativity is possible in theory, but is rare, or perhaps unknown, in practice. However, it does demonstrate that it is not strictly necessary for the encryption functions themselves to commute.)
The first three-pass method is due to Adi Shamir and described in Konheim, Allen G., “Cryptography—A Primer,” John Wiley & Sons, 1981, pp 346-7, and also, in Menezes, A., van Oorschot, P., and Vanstone, S., “Handbook of Applied Cryptography,” CRC Press, 1996, page 500. In the Shamir method, encryption consists of raising each block of the message to a large power modulo a large prime p, and decryption consists of raising each block to a power modulo the same prime, such that (Me)d=M (mod p). Since (Me)d=(Md)e the encryption and decryption functions all commute. There is a commercial encryption product called NK-Crypt from Master Software Corporation based on this method (NK-CRYPT Message Encryption System, www.mastersoftware.biz/nkcrypt.htm).
Given the modulus n and the values x and xm (mod n), determining the exponent m is called the Discrete Logarithm Problem. The fastest algorithm now known for solving the discrete logarithm problem modulo n is called the Index Calculus algorithm, and takes time proportional to exp(C(log n)1/3(log log n)2/3) where C is between 1.5 and 2. (The exact value of C depends on the form of n and certain details of the method which affect the storage required, so the value of C for any given n is determined by a space versus time trade-off.) The security of the Shamir method and the NK-Crypt software product rely on the assumption that no faster method for solving the Discrete Logarithm Problem will be discovered soon.
The chief drawback of the Shamir and related methods is that raising a large number to a large power modulo a large prime is very time-consuming.
U.S. Pat. No. 4,567,600 addresses the speed problem by using multiplication in a Galois field GF(2m) in place of multiplication modulo a prime p. This choice makes raising a number to a power faster, but it still requires a lot of multiplications of very large numbers, so the method is still slow.
There are two Private Key methods using the three-pass protocol which are very fast. These are the Bisi method disclosed in WO 03/007540 A1, and a freeware program called keylilla developed by Chanda Hedvikar-Hedvikar (see, e.g., www.bindhast.com/keylilla.htm). Both Bisi and keylilla use a random encryption key which is as long as the message itself. In Bisi, encryption consists of multiplying the message byte-by-byte by the secret key, and decryption consists of multiplying by the multiplicative inverse of that key. (Obviously all key bytes must be selected to have multiplicative inverses, otherwise the message cannot be decrypted.) In keylilla, encryption consists of exclusive-oring each byte of the message with the corresponding byte of the secret key, and decryption is identical to encryption, since exclusive-or is a self-inverse operation.
Let S and R represent the sender's and receiver's encryption keys, and S′ and R′ represent their decryption keys. In the Bisi method the 3 transmitted messages can therefore be represented as SM, RSM and RM=S′RSM. For each message character m which has a multiplicative inverse, the corresponding byte RSm will have the inverse (RSm)′=R′S′m′. If an eavesdropper has intercepted all three messages, multiplying (Sm)(RSm)′(Rm)=(Sm)(R′S′m′)(Rm)=m. In other words, every character of the message which has a multiplicative inverse can be recovered by multiplying the first and third message by the multiplicative inverse of the second message.
In the keylilla method it is even simpler for the eavesdropper. Let + represent bytewise exclusive-or. Then the 3 transmitted messages are M+S, M+S+R and M+S+R+S=M+R. If an eavesdropper has intercepted all 3 messages, then simply taking the exclusive-or of the 3 messages together will recover the plaintext message, namely (M+S)+(M+S+R)+(M+R)=(M+M+M)+(R+R)+(S+S)=M.
To summarize, the Shamir and NK-Crypt method and the Massey-Omura method are secure, but not fast, while the Bisi method and the keylilla method are fast but not secure. The purpose of this invention is to provide a Private Key encryption method which is both fast and secure.
To lay the foundation for the disclosure of the invention, it is helpful to review some computer and mathematics basics which underlie the invention. In most modern computers, data, such as letters and numbers, are represented as binary numbers, that is, numbers in the base 2. Each binary digit, or bit, in a binary number may take either the value 0 or the value 1. A group of 8 bits, called a byte, is commonly used to represent small numbers or letters. For example, the byte 01000001 represents the number 65, or the letter “A” in ASCII code.
In a message, each character of the text is represented as one byte, and the entire message is represented as a string of bytes. A message of n characters is thus represented by a string of n bytes, or 8n bits. For some computers it may be more convenient to view the message as a string of larger or smaller units, such as 4-bit or 16-bit or 32-bit units, commonly called nibbles, halfwords and words, respectively. In some cases, it is advantageous to use single bits as units because multiple bits can be packed into one computer word and can be operated on in parallel. Any string of units can also be viewed as a sequence of blocks of units. The blocks can be, but do not necessarily need to be, the same length.
The ordinary operations of addition, subtraction, multiplication and division can be performed on binary numbers. There are also bitwise logical operations, also called Boolean operations, that can be performed on binary numbers, namely bitwise “and”, bitwise “or” and bitwise “exclusive-or” or “xor”. These operations are performed separately for each corresponding bit position. For example
ANDORXOR000011110000111100001111010101010101010101010101-------------------------------------000001010101111101011010In a byte the leftmost bit is called the high-order bit, or most significant bit, and has the numeric value 27 or 128, while the rightmost bit is called the low-order bit, or least-significant bit, and has the numeric value 20 or 1.
In terms of the underlying mathematics, if m and n are positive integers, then the residue of n modulo m means the remainder when n is divided by m. The residue of n modulo m is denoted n (mod m) and m is called the modulus. So 42 (mod 10)=2. If x and y have the same residue modulo m this is denoted x=y (mod m). For example, 32=42 (mod 10). The operation which calculates the residue is called modulus division.
Any number which evenly divides m is called a factor of m. If n is a factor of m then m=0 (mod n), for example 12=0 (mod 4). If a positive integer p has no factors except 1 and p itself, then p is called a prime number, or simply a prime. For example, 2, 3, 5 7 and 11 are primes, but 9 is not prime because it is evenly divisible by 3. The factorization of an integer n expresses n as a product of primes. For example, the factorization of 90 is 2·32·5. If m and n have no factors in common then they are called relatively prime or coprime. For example, 8 and 15 are relatively prime.
A mathematical ring, or simply a ring, is a set of elements, or scalars, for which two operations are defined, commonly called scalar addition and scalar multiplication. Scalar addition, or simply addition, is usually denoted x+y, and scalar multiplication, or simply multiplication, is denoted xy. Scalar addition is commutative, that is x+y=y+x. Scalar addition and multiplication are associative. That is, (x+y)+z=x+(y+z) and (xy)z=x(yz). Scalar multiplication is also distributive over scalar addition. That is, x(y+z)=xy+xz and (x+y)z=xz+yz.
Every ring has an additive identity, usually denoted 0, such that x+0=0+x=x, and a multiplicative identity, usually denoted 1, for which 1x=x1=x for all x.
Each ring element x has an additive inverse. The additive inverse of the scalar x is denoted −x and addition of an additive inverse a+(−x) is usually shortened to a−x, with x−x=0. If x is an element of a ring, any element x′ for which x′x=1 is called a left multiplicative inverse of x, and any element x′ for which xx′=1 is called a right multiplicative inverse of x. An element may have more than one left multiplicative inverse or more than one right multiplicative inverse. If x has both a left multiplicative inverse x′ and a right multiplicative inverse x″, then they will be equal because (x′x)x″=x′(xx″) so (1)x″=x′(1) or x″=x′. In that case x′ is unique, and it is called the multiplicative inverse, or simply the inverse of x. If every element in the ring, except 0, has a multiplicative inverse, then the ring is called a field.
The best-known example of a ring is the integers using standard addition and multiplication. Every integer n has an additive inverse −n, but only the integers 1 and −1 have multiplicative inverses. A well-known example of a field is the rational numbers m/n, where m and n are integers and n is not equal to 0. The additive inverse of the rational number m/n is −m/n, and exists for all rational numbers. The multiplicative inverse (m/n)′ of the rational number m/n is n/m and exists for every rational number except 0. If the ring multiplication is commutative, that is if xy=yx, then the ring is called a commutative ring.
Another example of a ring is the integers modulo some integer m. The additive inverse of x modulo m is 0 when m=0, and m−x otherwise. Every integer n which is mutually prime to m will have a multiplicative inverse n′ such that nn′=1 (mod m). In particular, if m is of the form 2u then n will have a multiplicative inverse when n is odd. If m is prime, then the integers modulo m form a field which is denoted GF(p) standing for Galois Field of order p (in honor of Évariste Galois, 1811-1832).
A matrix is a rectangular array of elements from a ring. A matrix A with m rows and n columns is called a matrix of order m×n, or simply an m×n matrix, and the element in the i-th row and j-th column is designated Aij where i can range from 1 to m, and j can range from 1 to n. A matrix with only 1 row is called a row matrix or a row vector, a matrix with only 1 column is called a column matrix or a column vector, and a matrix with an equal number of rows and columns is called a square matrix. That is, a row matrix is 1×n, a column matrix is n×1, and a square matrix is n×n.
An m×n matrix A and an n×p matrix B can be multiplied to produce an m×p matrix C. This is denoted AB=C and C is called the matrix product of A and B. The element Cij in the i-th row and j-th column of C is formed from the i-th row of A and the j-th column of B by summing Ai1B1j+Ai2B2j+ . . . +AinBnj. The addition and multiplication in this expression is the ring addition and multiplication for the type of scalars used in the matrix. They may be the ordinary addition and multiplication of real numbers, they may be addition and multiplication of integers modulo some number, or they may be other mathematical operations.
Matrix multiplication is associative. That is, if A is an m×n matrix, B is an n×p matrix and C is a p×r matrix, then (AB)C=A(BC). Consequently, the set of n×n square matrices over a ring is itself a ring.
In a square n×n matrix A an element Aii is called a diagonal element, and the set of elements A11, A22, . . . , Ann are called the diagonal of the matrix. A diagonal matrix is a matrix whose only non-zero elements all lie on the diagonal. The diagonal matrix I whose diagonal elements are all 1 is called the identity matrix. The identity matrix has the property that AI=A and IA=A for any square matrix A. Any matrix A′, if one exists, for which A′A=I is called a left inverse of A, and any matrix A′ for which AA′=I is called a right inverse of A. A matrix may have more than one left inverse, or more than one right inverse. A matrix which has a left inverse is called left invertible, and a matrix which has a right inverse is called right invertible. If A has at least one left inverse and at least one right inverse matrix, then all of its inverse matrices will be equal, and this unique inverse matrix is simply called the inverse of A. A matrix which has an inverse is called invertible. (It is beyond the scope of this discussion, but a matrix over a commutative ring will be invertible whenever the value of its determinant has a multiplicative inverse in the ring.)
In the matrix product AB we say that B is left-multiplied by A and that A is right-multiplied by B. Two square matrices A and B commute if AB=BA. In general, matrix multiplication is not commutative. That is, in most cases the matrix product AB will not be the same as BA. If all of the matrices in a set F of square matrices commute with each other, then F is called a commutative family of matrices. If the ring is commutative, then the diagonal matrices are a commutative family, but other commutative families, containing non-diagonal matrices, may also exist. It is possible to have a commutative family of matrices over a ring even when the ring itself is not commutative.
If A and B are matrices in a commutative family F, then their product AB could also be in that family. This is because if C is any matrix in the family then C(AB)=(CA)B=(AC)B=A(CB)=A(BC)=(AB)C. So AB commutes with C. Henceforth it will be assumed that each commutative family F is closed under matrix multiplication, that is, if A and B are members, then AB is also a member.
A linear equation over a commutative ring is an equation of the form is an equation of the form a1x1+a2x2+ . . . +anxn+b=0 where a1, a2, . . . , an and b are constant ring elements and x1, x2, . . . , xn are variables. If L1, L2, . . . , Lm are linear equations, then L=c1L1+c2L2+ . . . +cmLm is a linear combination of the equations L1, L2, . . . , Lm. If L cannot be expressed as a linear combination of L1, L2, . . . , Lm then it is linearly independent of them. In a system of linear equations, the maximum number of linearly independent equations is called the rank of the system.
There are several forms for linear equations over a non-commutative ring. The form best suited for this disclosure is a1x1+a2x2+ . . . +anxn+x1b1+x2b2+ . . . +xnbn+c=0 where a1, a2, . . . , an, b1, b2, . . . bn and c are constant ring elements and x1, x2, . . . , xn are variables.
If F is a commutative family of n×n square matrices over a ring, and M is any matrix in that family, then the matrix X can belong to the family only if XM=MX. The matrix X has n2 entries, each of which is an element of the ring. The relationship XM=MX is equivalent to a set of n2 linear equations over the ring, however these equations are not linearly independent. For most familiar rings, the set of commutativity equations will contain n(n−d) linearly independent equations. For the largest possible commutative family of matrices over the ring d will be 1 If s is the size of this maximal family, then for a commutative family with a different value of d the size of the family will be about s1/d or d√s.