Cayley–Purser algorithm: Difference between revisions

Revision as of 03:10, 28 August 2006

Revision as of 15:45, 13 November 2006

Line 1:

The '''Cayley-Purser algorithm''' was published in early [[1999]] by [[Ireland|Irishwoman]] [[Sarah Flannery]], who was sixteen years old at the time. She named the [[cryptography|cryptographic]] [[algorithm]] for [[mathematician]] [[Arthur Cayley]] and [[Michael Purser]], founder of [[Baltimore Technologies]], a [[Dublin]] data security company. Flannery had the idea for the algorithm during an [[internship]] with Baltimore Technologies.

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.

The Cayler-Purser algorithm should have been some 22 times faster than the [[RSA]] process, because it uses a simpler [[mathematical function]]. For her work, Flannery received first prize in an Irish competition for young scientists. She and the Baltimore researchers subsequently discovered an attack on her algorithm, 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.

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.

Sarah, on advice from her father, 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 then the [[RSA]] algorithm which uses an [[exponent|exponential]] step. For her Intel Science Fair project Sarah prepared a plaintext encipherment using both RSA and her new Cayley-Purser algorithm and it did indeed show a 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 rather than merely running them against each other and she had 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 survey of possible attacks and had found none which worked.

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.

== Book ==