Cayley–Purser algorithm: Difference between revisions

Revision as of 03:37, 5 February 2008

Revision as of 22:23, 19 April 2008

Line 7:

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

On advice from her mathematician father, Flannery 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]]ial step. For her Intel Science Fair project Flannery 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, Flannery formalised Cayley-Purser's runtime and analyzed a variety of known attacks, none of which were determined to be effective.

Line 67:

== 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 sytemsystem 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:

Line 83:

[[Category:Asymmetric-key cryptosystems]]

[[de:Cayley-Purser-Algorithmus]]