A Matrix Extension of the RSA Cryptosystem

Andrew Pangia
December 12, 2014

Abstract
We propose a variation on the RSA Cryptosystem: namely, an extension of the RSA en-
cryption and decryption methods to matrix values in addition to scalars. We first explore the
mathematics behind the RSA Cryptosystem, after which, we investigate the theory of the pro-
posed variation to the system. The concept of extending the RSA Cryptosystem to apply to
matrices originated in a paper released by IEEE in 2008 but the method given contained sev-
eral errors. In our investigation, we correct those errors and establish limitations of the method
which we have found.

1 Introduction
Throughout human history, a necessity to secretly exchange messages has existed. The methods of
disguising the message are referred to as ciphers, or cryptosystems. Prior to being disguised, the
message is referred to as the plaintext, while the disguising process itself is referred to as encryp-
tion and typically involves an integer or group of integers called a key. After being encrypted, the
message is is referred to as a ciphertext, and the process of returning the ciphertext to the plaintext
is referred to as decryption. In the past, cryptosystems were utilised primarily during military en-
deavors where a commander needed to communicate with his peers without having the opposition
learning any information. In this current age of information, however, cryptosystems are far more
ubiquitous, ranging from checking email, to making a purchase online, to withdrawing money
from an ATM.
Some of the first ciphers were relatively simple, in which decrypting is simply reversing the
encryption process. A typical example of an early cipher is the Caesar Cipher. This cipher begins
by representing the desired character list in an integer system and selecting as a key a positive
integer less than the number of characters. This integer must be known to both the sender and
receiver. The sender converts his message into its integer form using the number correspondence
and adding the key to each integer in congruence addition. The resulting values are converted to
their corresponding characters and the resulting ciphertext is then sent. The receiver decrypts by
converting the ciphertext to integers, subtracting the key from each integer, and converting back to
character form. As an example, we use the English alphabet as our character list with the number
correspondence in Table 1 (on page 2).
Suppose the plaintext cryptography is being sent (this example is to show the process of the ci-
pher; we are not overly concerned with the applicability of the example). The sender selects the in-
teger k = 3 as his key and converts cryptography to the integers 3, 18, 25, 16, 20, 15, 7, 18, 1, 16, 8, 25

1
 a b c d e f g h i j k l m n o p
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16

q r s t u v w x y z
17 18 19 20 21 22 23 24 25 26

Table 1: Alphabetic Correspondence

using Table 1. He converts each plaintext integer p using the congruence

c⌘p+k ⌘p+3 (mod 26)

where c is the ciphertext value. Note that congruence modulo 26 is used since there are twenty-six
characters in our list. The integer form of the ciphertext is 6, 21, 2, 19, 23, 18, 10, 21, 4, 19, 11, 2,
which corresponds to fubswrjudskb. The receiver recreates the plaintext by use of the congruence

p⌘c k⌘c 3 (mod 26).

In the past, simple ciphers such as the Caesar Cipher were sufficient to enable private com-
munications. However, as technology has improved, the requirement for improved cryptosystems
became apparent. To see the evidence of this need, observe that regardless of which key is used
(or how many), the Caesar cipher can be cracked in a matter of microseconds using an exhaustive
search method with even an older computer.

2 The RSA Cryptosystem

2.1 Theory
Developed in 1977 by Ronald L. Rivest, Adir Shamir, and Leonard Adleman, the RSA Cryptosys-
tem is an asymmetric cipher; that is, the RSA system decrypts a message by use of a key other
than the key used to encrypt the message [2]. This asymmetricity enables the user to publish his
key and allow everyone to communicate with him, yet at the same time, prevents anyone from
knowing what he has been told. The RSA system involves the receiver choosing two large prime
numbers p and q and obtaining the integer n = pq. She next calculates (n) = (p 1)(q 1),
where (n) is the number of positive integers less than or equal to n which are relatively prime
to n. The receiver then selects an integer e such that gcd(e, (n)) = 1. The purpose of selecting
the number e in this manner is to ensure that e 1 exists modulo (n). The receiver now computes
d ⌘ e 1 (mod (n)) by using the Euclidean Algorithm or another preferred method for comput-
ing inverses. The ordered pair (e, n) is made public (and is in fact referred to as the public key)
while the ordered pair (d, (n)) remains private (and is referred to as the private key).
To encrypt a message, the sender converts the plaintext message using a pre-arranged conver-
sion method to an integer (or group of integers) modulo n, here denoted m such that m < n, and
calculates the ciphertext c ⌘ me (mod n). In the case that the plaintext message is too large for
one calculation, the sender simply breaks the message into components (in general i components)
and apply the exponentiation to each submessage.
 For decryption, the receiver computes m ⌘ cd (mod n). Before proving that this decryption
process is indeed successful, we state Euler’s Theorem, which is integral to the RSA Cryptosystem
(for a proof, see [2]).

Theorem 1. Euler’s Theorem. Let a 2 Z and n 2 N. If gcd(a, n) = 1, then a (n)

⌘ 1 (mod n).

In addition to Euler’s Theorem, the proof that RSA decryption results in the plaintext also
requires the following lemma, which is stated in [3].

Lemma 1. Let x, y, a, b 2 Z+ such that gcd(a, b) = 1. If x ⌘ y (mod a) and x ⌘ y (mod b),

then x ⌘ y (mod ab).

Proof. Let x, y, a, b 2 Z+ such that gcd(a, b) = 1. Suppose x ⌘ y (mod a) and x ⌘ y (mod b).
We will show that x ⌘ y (mod ab). Since x ⌘ y (mod a), we deduce that x = y + ka and since
x ⌘ y (mod b), we deduce that x = y + jb for some j, k 2 Z. By the transitive property of
equality
y + ka = x = y + jb.
By the cancellation property of equality, we obtain that

ka = jb,

which means that a|jb. Furthermore, since gcd(a, b) = 1, we conclude that a|j; hence, by defini-
tion of divides, j = la for some l 2 Z. By substitution, we obtain that x = y + jb = y + l(ab).
Consequently by definition of congruence, we deduce that x ⌘ y (mod ab).
We now proceed to prove that decryption in the RSA Cryptosystem does indeed result in the
plaintext method (stated in the following theorem).

Theorem 2. Let n = pq where p and q are distinct prime integers, let m 2 {0, 1, 2, . . . , n 1},
e, d 2 Z such that ed ⌘ 1 (mod (n)), and let c ⌘ me (mod n). Then cd ⌘ m (mod n).

Proof. Let e, d, n, m be as defined above and let c ⌘ me (mod n). We will show that
cd ⌘ m (mod n). Observe that cd ⌘ (me )d ⌘ med (mod n). Since ed ⌘ 1 (mod (n)), there
exists an integer k such that ed = k (n) + 1. Then

med ⌘ mk (n)+1
(mod n).

Observe that by definition, n = pq where p, q are distinct prime numbers. Then (n) = (p) (q)
and mk (n)+1 = mk (p) (q)+1 . Note that gcd(m, q) = 1 or gcd(m, q) = q. If m and q are relatively
prime, then by Euler’s Theorem m (q) ⌘ 1 (mod q) so

mk (n)+1
= mk (p) (q)+1
⌘ (m (q) k (p)
) m ⌘ 1k (p)
m⌘m (mod q).

If gcd(m, q) = q, then q|m, so m ⌘ 0 (mod q); hence

mk (n)+1
⌘0⌘m (mod q).

Consequently, mk (n)+1
⌘ m (mod q).
 In the same exact manner, we obtain that mk (n)+1 ⌘ m (mod p). Because p, q are distinct
primes (and thus relatively prime), by Lemma 1 we conclude that mk (n)+1 ⌘ m (mod pq), or
mk (n)+1 ⌘ m (mod n). Ergo, since cd ⌘ mk (n)+1 (mod n) and mk (n)+1 ⌘ m (mod n), by
transitivity we conclude that
cd ⌘ m (mod n).

The encryption key (e, n) is publicly known (so that all can send messages), whereas the de-
cryption key ( (n), d) is kept private. For decryption, the receiver exponentiates the ciphertext (the
message after being encrypted) as demonstrated in the proof of the theorem to obtain

cd ⌘ m (mod n)

and reconverts m to the message in the pre-determined manner.

RSA Cryptography is not the quickest encryption method currently in use due to the process-
ing time of calculating such large exponents; as such, RSA is more useful for transmitting small
amounts of data. One method is to use RSA Cryptography to encrypt a symmetric key used in
a swifter encryption method and send the symmetric key between communicants. This results in
the symmetric key being reasonably well protected from interception while still allowing for fast
communications.
Another use of the RSA cryptosystem lies in the verification of digital signatures. Under the
digital signature method, a person encrypts a message (his name for example) for his friend by use
of his own private decryption exponent. To verify that the message is indeed genuine, the receiver
of the message applies the encryption exponent which corresponds to the supposed sender. If
the message decrypts correctly, then the receiver knows that her friend did indeed send her the
message.

2.2 Example
As an example of how the RSA Cryptosystem operates, take cryptography as our plaintext; we
apply the correspondence stated with the Caesar Cipher.
The receiver selects prime integers

p = 503, and q = 499,

which yields
n = pq = 250997.
Next, the receiver computes

(n) = (p 1)(q 1) = 249996

and chooses her encryption exponent to be e = 19. Finally, she computes her decryption exponent
to be d = 210523 where ed ⌘ 1 (mod (n)). The encryption key which the receiver makes public
is (e, n) = (19, 250997).
If the sender wishes to send the message cryptography (as we assume he does for the purposes
of our example), he obtains m = 31825162015071801160825 using Table 1.
 He breaks m into four submessages less than n to obtain

m1 = 31825, m2 = 162015, m3 = 71801, m4 = 160825.

The sender then calculates the following ciphertexts and forwards them to his friend.

c1 ⌘ m1 e ⌘ 3182519 ⌘ 92363 (mod n);

c2 ⌘ m2 e ⌘ 16201519 ⌘ 13977 (mod n);
c3 ⌘ m3 e ⌘ 7180119 ⌘ 165966 (mod n);
c4 ⌘ m4 e ⌘ 16082519 ⌘ 56661 (mod n).

The receiver calculates the plaintexts by computing

m1 ⌘ c1 d ⌘ 92363210523 ⌘ 31825 (mod n);

d 210523
m2 ⌘ c2 ⌘ 13977 ⌘ 162015 (mod n);
m3 ⌘ c3 d ⌘ 165966210523 ⌘ 71801 (mod n);
d 210523
m4 ⌘ c4 ⌘ 56661 ⌘ 160825 (mod n).

We chose to use the correspondence of a to 01, b to 02 and so on for the sake of simplicity. The
American Standard Code for Information Interchange (ASCII), however, is frequently used as the
numerical correspondence; ASCII has integers {0, 1, ..., 127} to represent 128 characters, visible
characters beginning at 32 (for ‘space’) and ending at 126 (for ‘⇠’) with the remaining integers
referring to computer commands (backspace, newline, etc.).

3 Matrix Modification
3.1 Prior Work
Next we consider modification to the RSA Cryptosystem which involves storing the plaintext inside
a 2 ⇥ 2 matrix. This modification still utilises an integer n = pq where p, q are distinct prime
integers, but involves replacing the plaintext scalar value m with a 2 ⇥ 2 matrix, M and, rather than
relying on the value (n) = (p 1)(q 1), instead relies on the value

(p2 1)(p2 p)(q 2 1)(q 2 q)

which is created from the product of the orders of GL2 (Zp ) and GL2 (Zq ), general linear groups of
degree 2. A general definition of the General Linear Group is given below.

Definition 1. The General Linear Group of order s, denoted GLs (Zn ), is the monoid of invertible
s ⇥ s matrices containing elements from Zn with respect to multiplication such that the determi-
nants of the matrices and n are relatively prime.

Note that the identity matrix I is in GLs (Zn ). Furthermore, matrix multiplication is associative
for all matrices. Since the determinants of the matrices and n are relatively prime, every element
of GLs (Zn ) has a mulitplicative inverse in GLs (Zn ). Consequently, GLs (Zn ) is a group.
 The inspiration for this method comes from [1], which proposed this method for all square
matrices and stated the use of the General Linear Group. The exponentiation modulus proposed in
[1] was taken to be
Ys 1 s 1
Y
s k
g= (p p )+ (q s q k )
k=0 k=0
where s is the degree of the General Linear Group over Zp and the General Linear Group over Zq ;
furthermore, [1] claimed that
s 1
Y
(ps pk )
k=0
is the order of the General Linear Group of degree s. As an example, [1] took p = 43, q = 47. The
encryption modulus is n = pq = 2021, while the exponentiation modulus is
g = (p2 p)(p2 1) + (q 2 q)(q 2 1) = 8111184.
The encryption exponent was chosen to be e = 17 such that gcd(e, g) = 1 and the decryption
exponent was found to be d = 954257.
When we refer to a matrix A (mod n) for a positive integer n, we mean that each entry of A
belongs to Zn . We take as an example

13 1
M= .
20 7
Note that the matrix corresponds to the plaintext math. Then, according to the method proposed in
[1], the ciphertext is 
e 1473 884
C⌘M ⌘ (mod n).
1512 211
However, on decrypting this matrix, we obtain that

d 791 1460
C ⌘ (mod n).
906 115
Note that this matrix is not the original matrix M .

3.2 Conjecture
Aboud et al took their exponentiation modulus to be the sum of the orders of the general linear
groups of degree s over Zp and Zq . However, on noticing that this does not decompose to Euler’s
Phi Function for the 1 ⇥ 1 (scalar) case, we modified the exponentiation modulus to be
s 1
Y s 1
Y
s k
g= (p p )· (q s q k ).
k=0 k=0

To simplify investigation of our modification, we fixed s = 2 to obtain

g = (p2 p)(p2 1)(q 2 q)(q 2 1).
In order for our modified RSA system to be operable, we first prove that the order of GL2 (Zn )
be relatively calculable.
Theorem 3. The order of the General Linear Group GL2 (Zp ) is given by

|GL2 (Zp )| = (p2 1)(p2 p),

where p is a prime integer.

⇢
a b
Proof. Let S = : a, b, c, d 2 Zp . Note that GL2 (Zp ) ⇢ S. We will count the number
c d
of matrices in GL2 (Zp ) by subtracting the number of matrices not in the linear group from the
total possible number of matrices in S. Let A 2 S; since there are p choices for each entry in A,
we deduce that |S| = p4 . Let k denote the number of matrices not in GL2 (Zp ); then there will
be p4 k matrices in GL2 (Zp ). Suppose that A is not in GL2 (Zp ). Then det(A) ⌘ 0 (mod p);
that is, ad bc ⌘ 0 (mod p) or bc ⌘ ad (mod p). Either bc ⌘ 0 (mod p) or bc 6⌘ 0 (mod p).
We begin counting by taking bc ⌘ 0 (mod p); then there are 2p 1 ways to choose b and c such
that bc ⌘ 0 (mod p) and accordingly 2p 1 ways to choose a and d such that ad ⌘ bc (mod p).
Hence, there are (2p 1)2 ways to obtain ad ⌘ bc ⌘ 0 (mod p).
Now take bc ⌘ i (mod p) where i 2 {1, 2, ..., p 1} = Z⇤p . Observe that Z⇤p is a group with
respect to multiplication, so by the uniqueness of solutions in groups, we obtain that for a single i,
there are p 1 ways to obtain bc ⌘ i (mod p) and accordingly p 1 ways to obtain
ad ⌘ bc (mod p). Note that there are p 1 unique choices for i, so by applying the basic multi-
plication rule of combinatorics, we obtain that there are (p 1)(p 1)(p 1) = (p 1)3 different
ways to obtain bc ⌘ ad (mod p) for all nonzero bc.
Since zero and nonzero bc choices are disjoint, we obtain that k = (2p 1)2 + (p 1)3 , and
substituting yields that

|GL2 (Zp )| = p4 k = p4 ((2p 1)2 + (p 1)3 ).

Simplifying then yields that

|GL2 (Zp )| = (p2 1)(p2 p).

Having obtained the order of GL2 (Zp ) for all prime integers p, we are now able to construct a
modulus which will act in a similar fashion as (n) does in the RSA cryptosystem. We choose to
use
g = (p2 1)(p2 p)(q 2 1)(q 2 q)
where p and q are the prime factors of the aforementioned n and we obtain a result analogous to
Theorem 2. However, in order to do this, we require Lagrange’s Theorem in regards to group order
(for a proof, see [4]):

Theorem 4. Lagrange’s Theorem. Let H be a subgroup of a finite group G. Then |H| divides |G|.

We also require the following lemma.

Lemma 2. Let n = pq where p and q are distinct prime integers. If M 2 GL2 (Zn ), then
M 2 GL2 (Zp ) and M 2 GL2 (Zq ).
Proof. Let n = pq where p and q are distinct prime integers and suppose M 2 GL2 (Zn ). We
proceed by contradiction. Assume that M 2 / GL2 (Zp ). Then by definition of a general linear
group, gcd(det(M ), p) 6= 1. Since p is prime, we have that gcd(det(M ), p) = p; then p| det(M ).
Recall that p|n by definition of n. Then gcd(det(M ), n) p 6= 1, which contradicts that
M 2 GL2 (Zn ). Thus, we conclude that if M 2 GL2 (Zn ), then M 2 GL2 (Zp ). By the same
reasoning, M 2 GL2 (Zq ).
For our modification, we use M to denote the matrix representation of the plaintext, C to
denote the resulting ciphertext, and e and d to denote our encryption and decryption exponents
respectively. We calculate C ⌘ M e (mod n) and M ⌘ C d (mod n) using the fact that
ed ⌘ 1 (mod g).
Theorem 5. Let n = pq where p and q are distinct prime numbers, let M 2 GL2 (Zn ) be a
matrix made up of nonnegative integers less than n, let gp = |GL2 (Zp )| = (p2 1)(p2 p) and
gq = |GL2 (Zq )| = (q 2 1)(q 2 q) and define g = gp gq . Further let e, d 2 Z+ such that
ed ⌘ 1 (mod g), and let C ⌘ M e (mod n). Then C d ⌘ M (mod n).
Proof. Suppose we have all variables and matrices as defined above. We will show that
C d ⌘ M (mod n). Note that C d ⌘ (M e )d ⌘ M ed (mod n) by definition of C. Since
ed ⌘ 1 (mod g), we obtain by definition of congruence that ed = 1 + kg for some integer k.
Hence we obtain that
M ed ⌘ M 1+kg (mod n),
so we obtain that
M ed ⌘ M 1+kg ⌘ M · ((M gp )gq )k (mod p)
by definition of g. But we have that gp is the order of GL2 (Zp ); hence, since hM i is a subgroup
of GL2 (Zp ), we have by Lagrange’s Theorem that x := |hM i| divides gp . Hence we obtain that
gp = jx where j 2 Z, so

C d ⌘ M ed ⌘ M · ((M gp )gq )k ⌘ M · ((M xj )gq )k ⌘ M · (M x )jgq k ⌘ M · I jgq k ⌘ M (mod p).

In the exact same manner, we obtain that C d ⌘ M (mod q). Hence we have that
C d ⌘ M (mod n) by elementwise application of Lemma 1.

3.3 Example
As an example, we revisit the example of encrypting and decrypting cryptography. As before,
our hypothetical message receiver selects prime integers p = 503 and q = 499 and calculates
n = 250997. She now calculates

gp = (p2 1)(p2 p) = 63886038048,

gq = (q 2 1)(q 2 q) = 61876998000,
and
g = gp gq = 3953076248524019904000.
Finally, she selects encryption exponent e = 241 and finds her decryption exponent
d = 1016973972649332921361 such that ed ⌘ 1 (mod g). The publicised key (which comes with
information on how to store the values in the matrix) is still (e, n) while the private key is (d, g).
The sender converts his message cryptography into four submessages (the same four he attained
in the example of RSA Cryptography) and creates the encryption matrix
 
m1 m2 31825 162015
M= = .
m3 m4 71801 160825

The sender forwards the ciphertext matrix

 241 
e 31825 162015 153377 104497
C⌘M ⌘ ⌘ (mod n).
71801 160825 76449 55902

Meanwhile, the receiver decrypts by computing

 1016973972649332921361 
d 153377 104497 31825 162015
M ⌘C ⌘ ⌘ ⌘M (mod n).
76449 55902 71801 160825

3.4 Counterexample
Suppose, now, that we have a plaintext matrix whose determinant is zero modulo n and the sum of
the cross-elements is a multiple of one of the factors of n, that is, let plaintext

a b
M=
c d

such that
a + d = jp = b + c
or
a + d = kq = b + c.
Return to the prime integers used in [1]. The receiver opts to use p = 43, q = 47. The encryption
modulus is n = pq = 2021, while the exponentiation modulus is

g = gp gq = (p2 p)(p2 1)(q 2 q)(q 2 1) = 3337488 · 4773696 = 15932153115648.

The receiver chooses encryption exponent e = 17 such that gcd(e, g) = 1 and calculates the
decryption exponent d = 14994967638257. Suppose her friend sends her the message uvuv, which
becomes the matrix 
21 22
M= (note that 21 + 22 = 43).
21 22
The sender computes the ciphertext

e 1634 172
C⌘M ⌘ (mod n).
1634 172

However, on decrypting this matrix, the receiver obtains that


d 1290 774
C ⌘ (mod n).
1290 774
4 Conclusion
While we demonstrated the Matrix RSA Cryptosystem for GL2 (Zn ), there is no reason that the
Cryptosystem is not extendable to be used on a general linear group of general size s. The Matrix
RSA cryptosystem extends the RSA system by exponentiating a square matrix as opposed to a
scalar modulo n. This has a slight benefit of further complicating the brute force attack on the
decryption exponent since g, the value we use in place of (n) (indeed, applying our cryptosystem
to a scalar yields g = (n)), is vastly larger than (n). Both the RSA and the Matrix RSA
cryptosystems require roughly log2 (ed) exponentiations due to the technique known as successive
squaring. However, whereas a scalar multiplication is one quick action for a computer, an n ⇥ n
matrix multiplication requires at most n3 scalar multiplications and n2 (n 1) = n3 n2 scalar
additions. With special algorithms these numbers can become slightly smaller but still much slower
than the scalar multiplication. Hence the Matrix RSA cryptosystem is much slower than the scalar
RSA system. In addition, the RSA Cryptography method is generally considered to have factoring
n = pq as the weakest point since the easiest method of calculating d is using (n) which is easiest
calculated using p and q. The Matrix RSA cryptosystem is still completely reliant on p and q, so,
similar to RSA, factoring n is still a reliant method of attack.
In addition, we still need to perform more tests on the Matrix RSA system: We found that there
exists a time when the method fails to decrypt the ciphertext. However, does the decryption hold
when the cross-elements of the plaintext do not sum to a multiple of the factors yet the determinant
is zero? Also, we gave a specific example of when the matrix will not decrypt, but this example is
unlikely to occur in reality. As such, we must investigate the probability of an indecryptable matrix
actually occurring.

References
[1] S. Aboud et al, An Efficient RSA Public Key Encryption Scheme, Fifth International Con-
ference on Information Technology: New Generations, (2008), 127-130

[2] Burton, David M., Elementary Number Theory McGraw-Hill Higher Education: 1221 Av-
enue of the Americas, New York, NY 10020 [c2007].

[3] Marshall, David C., Edward Odell, and Michael Starbird, Number Theory Through In-
quiry Mathematical Association of America: MAA Service Center, Washington, DC 20090
[c2007]

[4] Nicholson W. Keith, Introduction to Abstract Algebra John Wiley & Sons, Inc., 111 River
Street, Hoboken NJ 07030 [c2012].

[5] Trappe, Wade and Lawrence C. Washington, Introduction to Cryptography with Coding The-
ory Pearson Education Inc., Upper Saddle River, NJ 07458 [c2006]