Notation used in this discussion is as in Flannery's original paper.
Key generation Like RSA, Cayley-Purser begins by generating two large primes
p and
q and their product
n, a
semiprime. Next, consider
GL(2,
n), the
general linear group of 2×2 matrices with integer elements and
modular arithmetic mod
n. For example, if
n=5, we could write: :\begin{bmatrix}0 & 1 \\ 2 & 3\end{bmatrix} + \begin{bmatrix}1 & 2 \\ 3 & 4\end{bmatrix} = \begin{bmatrix}1 & 3 \\ 5 & 7\end{bmatrix} \equiv \begin{bmatrix}1 & 3 \\ 0 & 2\end{bmatrix} :\begin{bmatrix}0 & 1 \\ 2 & 3 \end{bmatrix} \begin{bmatrix}1 & 2 \\ 3 & 4\end{bmatrix} = \begin{bmatrix}3 & 4 \\ 11 & 16\end{bmatrix} \equiv \begin{bmatrix}3 & 4 \\ 1 & 1\end{bmatrix} This group is chosen because it has large order (for large semiprime
n), equal to (
p2−1)(
p2−
p)(
q2−1)(
q2−
q). Let \chi and \alpha be two such matrices from GL(2,
n) chosen such that \chi\alpha \not= \alpha\chi. Choose some natural number
r and compute: :\beta = \chi^{-1}\alpha^{-1}\chi, :\gamma = \chi^r. The public key is n, \alpha, \beta, and \gamma. The private key is \chi.
Encryption The sender begins by generating a random natural number
s and computing: :\delta = \gamma^s :\epsilon = \delta^{-1}\alpha\delta :\kappa = \delta^{-1}\beta\delta Then, to encrypt a message, each message block is encoded as a number (as in RSA) and they are placed four at a time as elements of a plaintext matrix \mu. Each \mu is encrypted using: :\mu' = \kappa\mu\kappa. Then \mu' and \epsilon are sent to the receiver.
Decryption The receiver recovers the original plaintext matrix \mu via: :\lambda = \chi^{-1}\epsilon\chi, :\mu = \lambda\mu'\lambda. == Security ==