This paper describes a new method for performing secure encryption of blocks of streaming data. This algorithm is an extension of the RSA encryption algorithm . Instead of using a public key (𝑒,𝑛) where 𝑛 is the product of two large primes and e is relatively prim e to the Euler Totient function, 𝜑(𝑛), one uses a public key ( 𝑛,𝑚,𝐸), where m is the rank of the matrix 𝐸 and E is an invertible matrix in 𝐺𝐿(𝑚,𝜑(𝑛)). When m is 1, this last condition is equivalent to saying that E is relatively prime to 𝜑(𝑛), which is a requirement for standard RSA encryption . Rather than a secret private key ( d,𝜑(𝑛)) where d is the inverse of e (mod 𝜑(𝑛)), the private key is (D,𝜑(𝑛)), where D is the inverse of E (mod (𝜑(𝑛)). The key to making this generalization work is a matrix generalization of the scalar exponentiation operator that maps 𝑍𝑛𝑚, the set of 𝑚-dimensional vectors with integer coefficients modulo 𝑛, onto itself. 1. Background In public key encryption systems, a transmitter and receiver share a public key and the receiver possesses a secret key known only to himself. The transmitter encrypts and sends a secret message using the public key. Without expending considerable time a nd resources, o nly the receiver with the private key is capable of decrypting the secret message . The RSA algorithm, named after its inventors, Rivest -Shamir -Adleman, is a public key encryption system described in [ Rivest, 1983 ]. In its simplest form, key s are generated as follows: Step 1: Choose two large primes, 𝑝 and 𝑞 and compute 𝑛=𝑝∗𝑞. Step 2: Compute 𝜑(𝑛)=(𝑝−1)∗(𝑞−1). Step 3: Find an exponent 𝑒 such that 𝑔𝑐𝑑(𝜑(𝑛),𝑒)=1. Step 4: Compute 𝑑=𝑒−1 𝑚𝑜𝑑(𝜑(𝑛)). Step 5: Publish (𝑛,𝑒) as the public key, and keep (𝑑,𝜑(𝑛)) as the secret private key. To encrypt, the sender first maps the message to a value M between 1 and 𝑛−1. 𝑀 is then encrypted according to the formula 𝐶=𝑀𝑒(𝑚𝑜𝑑 𝑛). (1) The receiver decrypts the message by computing (𝑀𝑒)𝑑(𝑚𝑜𝑑 𝑛)= 𝑀𝑒𝑑 (𝑚𝑜𝑑 𝑛)=𝑀 (𝑚𝑜𝑑 𝑛) (2) by Fermat’s little theorem, since 𝑒𝑑=1 𝑚𝑜𝑑(𝜑(𝑛)). The RSA algorithm is not use d on plaintext messages of arbitrary length for several reasons. First, note from above that each data block must be mapped to a value 𝑀 between 1 and 𝑛−1. This prevents outright encryption of an entire message unless the message is small. However, breaking the message into smaller data blocks creates other problems. W e see from (1) that repeated encryption of the same text with the same encryption key always yields the same result. T his can make the technique vulnerable to both frequency analysis attack s and chosen ciphertext attack s. To see an example of a frequency analysis attack , suppose that a long message is encrypted using standard RSA encryption, and that each letter in the message i s individually encrypted using the same RSA encryption key. Since each encryption of the letter “e” is the same, one might be able to discern which encryption represented the letter “ e” from a frequency analysis. To illustrate the RSA vulnerability to a chosen cipher text attack, suppose that an attacker knew a value k which was easily invertible ( 𝑚𝑜𝑑 𝑛). Suppose also that he did not know the decryption of an encrypted message (𝑀)𝑒 (𝑚𝑜𝑑 𝑛), but he was given access to the decryption of 𝑘(𝑀)𝑒 (𝑚𝑜𝑑 𝑛) for some scalar k. The decryption is given by (𝑘(𝑀)𝑒)𝑑=𝑘𝑑𝑀𝑒𝑑=𝑘𝑑𝑀=𝑘−𝑒𝑀(𝑚𝑜𝑑 𝑛). But since k is easily invertible and e is known, 𝑘−𝑒 can also be computed and hence M can be discovered. Therefore, repeated application of the standard RSA algorithm with the same encryption key is not recommended for decrypting streaming data. Instead , a more secure approach is to use the RSA encryption to agree on a block hash. This hash is then us ed in a block encryption algorithm (such as AES, see [ NIST, 2001 ]), where the message is broken into data blocks of fixed length, and each data block is en crypted using a function dependent on the hash and the previous data blocks. This paper describes a matrix generalization of the RSA encryption algorithm that overcomes these obstacles . This generalization permits encryption of a data block to be depen dent on previous data blocks or random nonce, guaranteeing that repeated encryption of the same message does not yield the same ciphertext. This blocks the chosen ciphertext and frequency analysis attack vulnerabilities described above. Previously proposed m atrix-based public key encryption systems (such as [Backal, 2001 ], [Chuang, 1991 ], [Singh, 2004 ] and [ Slavin, 2008 ]) have mapped a message into one or more matrices, and then performed encryption on these matrices. For example, [Chuang, 1991 ] encrypts by mapping the message into the off -diagonal elements of a triangular matrix, and applies the Cayley -Hamilton theorem to perform scalar exponentiat ion of the matrix. This approach is different, because it generalizes the RSA algorithm to operate on entire matrices, instead of applying standard RSA to operate on scalar data that resides within a matrix. For example, the key generation process is mod ified to choose an invertible matrix 𝐸 in the general linear group of 𝑚x𝑚 invertible matrices (𝑚𝑜𝑑 𝛷(𝑛)) instead of a scalar 𝑒. In step 4, the matrix inverse 𝐷 is computed instead of a scalar 𝑑. With appropriately defined vector exponentiation, equations (1) and (2) continue to hold. Th ese changes allow for confusion across encrypted data blocks , and allow RSA encryption on streaming data. 1.1. Mathematical Notation Throughout this paper, we use 𝛷(𝑛) to represent the number of positive integers not e xceeding the integer 𝑛 and relatively prime to 𝑛. This is commonly known as Euler’s Totient function. We also use the expression 𝐺𝐿(𝑚,𝑠) to represent the general linear group of invertible 𝑚 𝑥 𝑚 matrices with coefficients in the field of integers modulo s . For integer x and z, the expression 𝑥(𝑚𝑜𝑑 𝑧) denotes the integral remainder when x is divided by z. When the expression preceding (𝑚𝑜𝑑 𝑧) is a matrix, the integral remainder is computed fo r each component of the matrix. Hence (1327 41−4)= (37 16)(𝑚𝑜𝑑 10). Now we define a generalization of scalar exponentiation that can be applied to vectors of length 𝑚>1. Let 𝑍𝑠be the ring of integers modulo s, and let 𝐴=[𝑎1,1 𝑎2,1 ⋮ 𝑎𝑚,1𝑎1,2 𝑎2,2 ⋮ 𝑎𝑚,2⋯ ⋱ 𝑎𝑚,1 𝑎𝑚,2 ⋮ 𝑎𝑚,𝑚] be an 𝑚𝑥𝑚 matrix with coeffici ents in 𝑍𝑠. Suppose that 𝑋=(𝑥1 𝑥2 ⋮ 𝑥𝑚) is an 𝑚-dimensional vector with non -zero components which are also in 𝑍𝑠. We denote the transpose of 𝑋 by 𝑋𝑇=(𝑥1,𝑥2,…,𝑥𝑚) and note that (𝑋𝑇)𝑇=𝑋. Next, define a new operator - the vector exponentiation operator “^^”. This operator maps the set of 𝑚-dimensional vectors with non -zero components over 𝑍𝑠 to itself, by: 𝑋^^𝐴= ( ∏𝑥𝑗𝑎1,𝑗 𝑚 𝑗=1 ∏𝑥𝑗𝑎2,𝑗 𝑚 𝑗=1 ⋮ ∏𝑥𝑗𝑎𝑚,𝑗 𝑚 𝑗=1) , (3) Note that ( 3) confuses the inputs; each output 𝑦𝑖 depends on all inputs 𝑥𝑗 for which 𝑎𝑖,𝑗≠0. Two additio nal important properties of the definition (3) are: 𝑋^^𝐼=𝑋 (4) and ((𝑋^^𝐴)^^𝐵) = (𝑋^^(𝐵∗𝐴)) (5). Equation (4) follows directly from (3). For (5), note that the 𝑖-th component of (𝑋^^𝐴)^^𝐵 is given by 𝑧𝑖=∏ 𝑚 𝑘=1(∏𝑥𝑗𝑎𝑘,𝑗 𝑚 𝑗=1)𝑏𝑖,𝑘= ∏ 𝑚 𝑘=1(∏𝑥𝑗𝑎𝑘,𝑗𝑏𝑖,𝑘 𝑚 𝑗=1 ) =∏𝑥𝑗∑𝑎𝑘,𝑗𝑏𝑖,𝑘𝑚 𝑘=1𝑚 𝑗=1 (6). But the (𝑖, 𝑗) component of 𝐵𝐴 is given by (𝐵𝐴)𝑖,𝑗= ∑𝑏𝑖,𝑘𝑎𝑘,𝑗𝑚 𝑘=1 (7). Hence, combining (6) and (7), 𝑧𝑖=∏𝑥𝑗∑𝑎𝑘,𝑗𝑏𝑖,𝑘𝑚 𝑘=1𝑚 𝑗=1 =∏𝑥𝑗(𝐵𝐴)𝑖,𝑗 𝑚 𝑗=1 , whic h proves (5). 1.2. Paper Overview Section 2 provides a high -level overview of how matrix -based RSA encryption works, and illustrates encryption and decryption of a simple message using this approach. A detailed description of the algorithm is provided in section 3. Section 3.1 presents several alternatives for key generation, including randomized selection of matrix components, similarity transformat ion on diagonal matrices, and LU compositions with randomized off -diagonal elements. Streaming data encryption approaches are outlined in section 3.2, and include encryption with previously encrypted data blocks, encryption with random nonce, and combinati ons of both previous data blocks and random nonce. Section 3.3 describes the decryption process steps. Security and performance notes are found in section 4, and the author’s summary and conclusions are found in section 5.