Content deleted Content added
No edit summary |
commutative property, not some inverse thing |
||
| (31 intermediate revisions by 25 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.
During a work-experience placement with Baltimore Technologies, Sarah was shown an unpublished paper by Michael Purser which outlined a new [[public-key]] cryptographic scheme using [[non-commutative]] multiplication. She was asked to write an implementation of this scheme in [[Mathematica]] as part of her duties during her placement.▼
▲During a work-experience placement with Baltimore Technologies,
Before this placement, Sarah had attended the 1998 [[Young Scientist and Technology Exhibition|ESAT Young Scientist and Technology Exhibition]] with a project describing already existing crytographic techniques from [[Caesar cipher]] to [[RSA]]. This had won her the Intel Student Award which included the opportunity to compete in the 1998 [[Intel International Science and Engineering Fair]] in the United States. Feeling that she needed some original work to add to her exhibition project, Sarah asked Michael Purser for permission to include work based on his cryptographic scheme. ▼
▲Before this placement,
On advice from her mathematician father, Sarah decided to use [[Matrix (mathematics)|matrices]] to implement Purser's scheme as [[matrix multiplication]] has the necessary property of being non-commutative. As the resulting algorithm would depend on multiplication it would be a great deal faster than the [[RSA]] algorithm which uses an [[exponent|exponential]] step. For her Intel Science Fair project Sarah prepared a demonstration where the same plaintext was enciphered using both RSA and her new Cayley-Purser algorithm and it did indeed show a significant time improvement.▼
▲On advice from her mathematician father,
Returning to the ESAT Young Scientist and Technology Exhibition in 1999, Flannery formalised Cayley-Purser's runtime and analyzed a variety of known attacks, none of which were determined to be effective.
Sarah did not make any claims that the Cayley-Purser algorithm would definitely replace RSA, knowing that any new cryptographic system would need to stand the test of time before it could be acknowledged as a secure system. The media were not so circumspect however and when she received first prize at the ESAT exhibition, newspapers around the world reported the story that a young girl genius had revolutionised cryptography.▼
▲
In fact an attack on the algorithm was discovered shortly afterwards but she analyzed it and included it as an appendix in later competitions, including a Europe-wide competition in which she won a major award, acknowledging that the work she had done on this algorithm was just as impressive whether or not it resulted in a genuinely secure encipherment system.▼
▲In fact an attack on the algorithm was discovered shortly afterwards but she analyzed it and included it as an appendix in later competitions, including a Europe-wide competition in which she won a major award
▲== Book ==
Sarah Flannery and David Flannery, ''In Code: A Mathematical Journey'', ISBN 0-7611-2384-9▼
==
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 [[general linear group|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:
:<math>\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}</math>
:<math>\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}</math>
This group is chosen because it has large order (for large semiprime ''n''), equal to (''p''<sup>2</sup>−1)(''p''<sup>2</sup>−''p'')(''q''<sup>2</sup>−1)(''q''<sup>2</sup>−''q'').
Let <math>\chi</math> and <math>\alpha</math> be two such matrices from GL(2,''n'') chosen such that <math>\chi\alpha \not= \alpha\chi</math>. Choose some natural number ''r'' and compute:
:<math>\beta = \chi^{-1}\alpha^{-1}\chi,</math>
:<math>\gamma = \chi^r.</math>
The public key is <math>n</math>, <math>\alpha</math>, <math>\beta</math>, and <math>\gamma</math>. The private key is <math>\chi</math>.
=== Encryption ===
The sender begins by generating a random natural number ''s'' and computing:
:<math>\delta = \gamma^s</math>
:<math>\epsilon = \delta^{-1}\alpha\delta</math>
:<math>\kappa = \delta^{-1}\beta\delta</math>
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 <math>\mu</math>. Each <math>\mu</math> is encrypted using:
:<math>\mu' = \kappa\mu\kappa.</math>
Then <math>\mu'</math> and <math>\epsilon</math> are sent to the receiver.
=== Decryption ===
The receiver recovers the original plaintext matrix <math>\mu</math> via:
:<math>\lambda = \chi^{-1}\epsilon\chi,</math>
:<math>\mu = \lambda\mu'\lambda.</math>
== Security ==
Recovering the private key <math>\chi</math> from <math>\gamma</math> is computationally infeasible, at least as hard as finding square roots mod ''n'' (see [[quadratic residue]]). It could be recovered from <math>\alpha</math> and <math>\beta</math> if the system <math>\chi\beta = \alpha^{-1}\chi</math> could be solved, but the number of solutions to this system is large as long as elements in the group have a large order, which can be guaranteed for almost every element.
However, the system can be broken by finding a multiple <math>\chi'</math> of <math>\chi</math> by solving for <math>d</math> in the following congruence:
:<math>d \left(\beta - \alpha^{-1}\right) \equiv \left(\alpha^{-1}\gamma - \gamma\beta\right) \pmod n</math>
Observe that a solution exists if for some <math>i, j \in \left|\gamma\right|</math> and <math>x, y \in \mathbb{Z}_n</math>
:<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> — 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 ==
▲* Sarah Flannery and David Flannery
{{Cryptography navbox | public-key}}
{{DEFAULTSORT:Cayley-Purser algorithm}}
[[Category:Public-key encryption schemes]]
[[Category:Broken cryptography algorithms]]
| |||