The Cayley-Purser algorithm is a public-key cryptography algorithm that relies on the fact that matrix multiplication is not commutative. It was devised by Sarah Flannery (then age 16), inspired by ideas of Michael Purser, for a Young Scientist competition in 1998. Flannery named the algorithm after Purser and Arthur Cayley (the inventor of matrices).
The Cayley-Purser algorithm uses only modular matrix multiplication instead of modular exponentiation, and is much faster than other public-key algorithms for large moduli (e.g., about 20 times faster than RSA encryption for a 200-digit modulus). While the algorithm at first seemed to be as secure as RSA, it was subsequently shown that messages encrypted with this algorithm can be readily decrypted by knowledge of public data alone.
Setup for the Cayley-Purser algorithm proceeds as follows.
1. Choose two large primes 
and 
, and let 
. The primes 
and 
should both be of the form 
, where 
is also prime.
2. Choose matrices 
and 
at random from 
(the general linear
group of 
invertible matrices whose entries are integers modulo 
) so that 
.
3. Choose 
and let 
.
4. Let 
.
5. Publish 
,
,
,
and 
.
Keep secret the matrix 
, which is needed for decryption.
To encrypt, use the following procedure.
1. Represent the message as a 
matrix 
with entries in 
.
2. Choose 
at random.
3. Let 
.
4. Let 
.
5. Encrypt 
as 
.
6. Transmit the pair 
.
Decryption is performed as follows.
1. Let 
.
2. Then 
.
Since 
and 
commute, we have
 |  |  |
(1)
|
 |  |  |
(2)
|
 |  |  |
(3)
|
Because 
is the product of two large, unknown primes, it is computationally difficult to determine
the original matrix 
via 
. In addition, solving
 |
(4)
|
for 
is intractable since, as a result of the way 
and 
are chosen, the order of the center of 
in 
will be at least 
with probability 
.
However, it is not necessary to know 
to decrypt messages; knowledge of a multiple of 
is sufficient, since if 
, it follows that
 |
(5)
|
If the matrix 
is derogatory, (that is, if 
is reduced modulo 
or modulo 
, the result is a scalar multiple of the identity), then 
can be factored as 
. With a factorization of
in hand, determining the solution to 
in 
is not difficult.
If 
is nonderogatory, then a multiple of 
of 
can be determined as follows. Since 
, then by the Cayley-Hamilton
theorem, there are integers 
and 
so that 
. Consequently, there is a matrix 
for some as yet unknown value of 
.
Also observe that
 |
(6)
|
so
 |
(7)
|
Thus,
 |
(8)
|
 |
(9)
|
 |
(10)
|
This allows 
,
and hence 
,
to be determined. The matrix 
can be used in place of 
in the decryption step.
