Cayley–Purser algorithm: Difference between revisions

Revision as of 16:26, 25 January 2008

Revision as of 03:32, 5 February 2008

Line 1:

The '''Cayley-Purser algorithm''' was a [[public-key cryptography]] [[algorithm]] published in early [[1999]] by 16-year-old [[Ireland|Irishwoman]] [[Sarah Flannery]], whobased wason sixteenan yearsunpublished oldwork atby the[[Michael time.Purser]], Shefounder named theof [[cryptography|cryptographicBaltimore Technologies]], a [[algorithmDublin]] data security company. Flannery named it for [[mathematician]] [[Arthur Cayley]]. andIt [[Michaelhas Purser]],since founderbeen offound [[Baltimoreto Technologies]]be flawed, abut [[Dublin]]was datathe securitysubject companyof considerable media attention.

== BookHistory ==

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, SarahFlannery 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.

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, SarahFlannery 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, SarahFlannery asked Michael Purser for permission to include work based on his cryptographic scheme.

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, SarahFlannery 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 SarahFlannery 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.

Returning to the ESAT Young Scientist and Technology Exhibition in 1999, Sarah expanded further on the new material she had been working on. She formalised the estimated time the new algorithm would take in comparison to RSA to add to the empirical data from running them against each other. She also attempted to determine whether the new algorithm was vulnerable to any attacks which would make it easy to break. To achieve this she had to do a comprehensive investigation of possible attacks and had found none which worked.

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.

SarahFlannery 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, 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.

== Book ==

Sarah Flannery and David Flannery, ''In Code: A Mathematical Journey'', ISBN 0-7611-2384-9

== External linksOverview ==

Notation used in this discussion is as in Flannery's original paper.

see also: <a href="http://cryptome.org/flannery-cp.pdf">

=== Key generation ===

* [http://cryptome.org/flannery-cp.htm Sarah Flannery's description of the Cayley-Purser algorithm]

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&times;2 matrices with integer elements and [[modular arithmetic]] mod ''n''. For example, if ''n''=5, we could write:

[[Category:Asymmetric-key cryptosystems]]

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

[[de:Cayley-Purser-Algorithmus]]

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

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

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

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

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

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

This group is chosen because it has large order for large semiprime ''n'', equal to:

:<math>n\phi(n)^2(p+1)(q+1)</math>

{{crypto-stub}}

where <math>\phi</math> is [[Euler's totient function]].

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>

:<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 sytem is large as long as the matrix group has large order, which we ensured.

However, the system was broken when a method for finding a multiple <math>\chi'</math> of <math>\chi</math> using the public parameters by solving the congruence:

:<math>\delta\left(\beta_{11}^{-1} - \alpha_{11}\right) \equiv e \pmod n</math>

where <math>\alpha_{11}, \beta_{11}</math> are the top-left elements of <math>\alpha, \beta</math>. Since any multiple of <math>\chi</math> can be used to decipher, this presents a fatal weakness for the system that has not yet been reconciled.

== References ==

* Sarah Flannery. [http://cryptome.org/flannery-cp.htm Cryptography: An Investigation of a New Algorithm vs. the RSA]. ([http://cryptome.org/flannery-cp.pdf original pdf])

* Sarah Flannery and David Flannery,. ''In Code: A Mathematical Journey'',. ISBN 0-7611-2384-9

[[Category:Asymmetric-key cryptosystems]]

[[de:Cayley-Purser-Algorithmus]]