Cayley–Purser algorithm: Difference between revisions

Revision as of 14:43, 3 October 2019

Latest revision as of 08:53, 19 October 2022

(4 intermediate revisions by 4 users not shown)

Line 1:

{{Short description|1999 public-key cryptography algorithm}}

{{One source|date=October 2019}}

The '''Cayley–Purser algorithm''' was a [[public-key cryptography]] [[algorithm]] published in early 1999 by 16-year-old [[Ireland|Irishwoman]] [[Sarah Flannery]], based on an unpublished work by [[Michael Purser]], founder of [[Baltimore Technologies]], a [[Dublin]] data security company. Flannery named it for [[mathematician]] [[Arthur Cayley]]. It has since been found to be flawed as a public-key algorithm, but was the subject of considerable media attention.

Line 21 ⟶ 23:

=== Key generation ===

Like RSA, Cayley-Purser begins by generating two large primes ''p'' and ''q'' and their product ''n'', a [[semiprime]]. Next, consider [[general linear group|GL]](2,''n''), the [[general linear group]] of 2×22×2 matrices with integer elements and [[modular arithmetic]] mod ''n''. For example, if ''n''=5, we could write:

:<math>\left[\begin{matrixbmatrix}0 & 1 \\ 2 & 3\end{matrixbmatrix}\right] +

\left[\begin{matrixbmatrix}1 & 2 \\ 3 & 4\end{matrixbmatrix}\right] =

\left[\begin{matrixbmatrix}1 & 3 \\ 5 & 7\end{matrixbmatrix}\right] =\equiv

\left[\begin{matrixbmatrix}1 & 3 \\ 0 & 2\end{matrixbmatrix}\right]</math>

:<math>\left[\begin{matrixbmatrix}0 & 1 \\ 2 & 3 \end{matrixbmatrix}\right]\left[ \begin{matrixbmatrix}1 & 2 \\ 3 & 4\end{matrixbmatrix}\right] =

\left[\begin{matrixbmatrix}3 & 4 \\ 11 & 16\end{matrixbmatrix}\right] =\equiv

\left[\begin{matrixbmatrix}3 & 4 \\ 1 & 1\end{matrixbmatrix}\right]</math>

This group is chosen because it has large order (for large semiprime ''n''), equal to (''p''²-1−1)(''p''²-−''p'')(''q''²-1−1)(''q''²-−''q'').

Let <math>\chi</math> and <math>\alpha</math> be two such matrices from GL(2,''n'') chosen such that <math>\chi\alpha^{-1} \not= \alpha\chi</math>. Choose some natural number ''r'' and compute:

:<math>\beta = \chi^{-1}\alpha^{-1}\chi,</math>

Line 73 ⟶ 75:

:<math>x\left(\beta_{ij}^{-1} - \alpha_{ij}\right) \equiv y \pmod n.</math>

If <math>d</math> is known, <math>d \mathrm{I} + \gamma = \chi'</math> &mdash;— a multiple of <math>\chi</math>. Any multiple of <math>\chi</math> yields <math>\lambda = \kappa^{-1} = v^{-1}\chi^{-1} \epsilon v\chi</math>. This presents a fatal weakness for the system, which has not yet been reconciled.

This flaw does not preclude the algorithm's use as a mixed private-key/public-key algorithm, if the sender transmits <math>\epsilon</math> secretly, but this approach presents no advantage over the common approach of transmitting a [[symmetric encryption]] key using a public-key encryption scheme and then switching to symmetric encryption, which is faster than Cayley-Purser.

==See also==

* [[Non-commutative cryptography]]

== References ==

Line 87 ⟶ 89:

{{DEFAULTSORT:Cayley-Purser algorithm}}

[[Category:Public-key encryption schemes]]

[[Category:Broken cryptography algorithms]]