Cayley–Purser algorithm
   HOME

TheInfoList



OR:

The Cayley–Purser algorithm was a
public-key cryptography Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
published in early 1999 by 16-year-old
Irishwoman The Irish ( ga, Muintir na hÉireann or ''Na hÉireannaigh'') are an ethnic group and nation native to the island of Ireland, who share a common history and culture. There have been humans in Ireland for about 33,000 years, and it has been c ...
Sarah Flannery Sarah Flannery (born 1982, County Cork, Ireland) was, at sixteen years old, the winner of the 1999 Esat Young Scientist Exhibition for her development of the Cayley–Purser algorithm, based on work she had done with researchers at Baltimore Tec ...
, based on an unpublished work by Michael Purser, founder of
Baltimore Technologies Baltimore Technologies was a leading Irish internet security firm, with its headquarters in Dublin, Ireland. It was listed on the London Stock Exchange and was briefly part of the FTSE 100 Index during 2000. Fran Rooney was the CEO for a period ...
, a
Dublin Dublin (; , or ) is the capital and largest city of Republic of Ireland, Ireland. On a bay at the mouth of the River Liffey, it is in the Provinces of Ireland, province of Leinster, bordered on the south by the Dublin Mountains, a part of th ...
data security company. Flannery named it for
mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...
Arthur Cayley Arthur Cayley (; 16 August 1821 – 26 January 1895) was a prolific United Kingdom of Great Britain and Ireland, British mathematician who worked mostly on algebra. He helped found the modern British school of pure mathematics. As a child, C ...
. It has since been found to be flawed as a public-key algorithm, but was the subject of considerable media attention.


History

During a work-experience placement with Baltimore Technologies, Flannery was shown an unpublished paper by Michael Purser which outlined a new
public-key Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
cryptographic scheme using
non-commutative In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
multiplication. She was asked to write an implementation of this scheme in
Mathematica Wolfram Mathematica is a software system with built-in libraries for several areas of technical computing that allow machine learning, statistics, symbolic computation, data manipulation, network analysis, time series analysis, NLP, optimizat ...
. Before this placement, Flannery had attended the 1998 ESAT Young Scientist and Technology Exhibition with a project describing already existing cryptographic techniques from the 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 The Regeneron International Science and Engineering Fair (ISEF) is an annual science fair in the United States. It is owned and administered by the Society for Science, a 501(c)(3) non-profit organization based in Washington, D.C. Each May, more tha ...
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
matrices Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
to implement Purser's scheme as
matrix multiplication In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...
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 Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to re ...
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. Flannery did not make any claims that the Cayley–Purser algorithm would 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.


Overview

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 In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers. Because there are infinitely many prime nu ...
. Next, consider GL(2,''n''), the
general linear group In mathematics, the general linear group of degree ''n'' is the set of invertible matrices, together with the operation of ordinary matrix multiplication. This forms a group, because the product of two invertible matrices is again invertible, ...
of 2×2 matrices with integer elements and
modular arithmetic In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book ...
mod ''n''. For example, if ''n''=5, we could write: :\begin0 & 1 \\ 2 & 3\end + \begin1 & 2 \\ 3 & 4\end = \begin1 & 3 \\ 5 & 7\end \equiv \begin1 & 3 \\ 0 & 2\end :\begin0 & 1 \\ 2 & 3 \end \begin1 & 2 \\ 3 & 4\end = \begin3 & 4 \\ 11 & 16\end \equiv \begin3 & 4 \\ 1 & 1\end This group is chosen because it has large order (for large semiprime ''n''), equal to (''p''2−1)(''p''2−''p'')(''q''2−1)(''q''2−''q''). Let \chi and \alpha be two such matrices from GL(2,''n'') chosen such that \chi\alpha \not= \alpha\chi. Choose some natural number ''r'' and compute: :\beta = \chi^\alpha^\chi, :\gamma = \chi^r. The public key is n, \alpha, \beta, and \gamma. The private key is \chi.


Encryption

The sender begins by generating a random natural number ''s'' and computing: :\delta = \gamma^s :\epsilon = \delta^\alpha\delta :\kappa = \delta^\beta\delta 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 \mu. Each \mu is encrypted using: :\mu' = \kappa\mu\kappa. Then \mu' and \epsilon are sent to the receiver.


Decryption

The receiver recovers the original plaintext matrix \mu via: :\lambda = \chi^\epsilon\chi, :\mu = \lambda\mu'\lambda.


Security

Recovering the private key \chi from \gamma is computationally infeasible, at least as hard as finding square roots mod ''n'' (see
quadratic residue In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that: :x^2\equiv q \pmod. Otherwise, ''q'' is called a quadratic no ...
). It could be recovered from \alpha and \beta if the system \chi\beta = \alpha^\chi 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 \chi' of \chi by solving for d in the following congruence: :d \left(\beta - \alpha^\right) \equiv \left(\alpha^\gamma - \gamma\beta\right) \pmod n Observe that a solution exists if for some i, j \in \left, \gamma\ and x, y \in \mathbb_n :x\left(\beta_^ - \alpha_\right) \equiv y \pmod n. If d is known, d \mathrm + \gamma = \chi' — a multiple of \chi. Any multiple of \chi yields \lambda = \kappa^ = v^\chi^ \epsilon v\chi. 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 \epsilon secretly, but this approach presents no advantage over the common approach of transmitting a
symmetric encryption Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between th ...
key using a public-key encryption scheme and then switching to symmetric encryption, which is faster than Cayley-Purser.


See also

*
Non-commutative cryptography Non-commutative cryptography is the area of cryptology where the cryptographic primitives, methods and systems are based on algebraic structures like semigroups, Group (mathematics), groups and Ring (mathematics), rings which are non-commutative. On ...


References

* Sarah Flannery and David Flannery. ''In Code: A Mathematical Journey''. {{DEFAULTSORT:Cayley-Purser algorithm Public-key encryption schemes Broken cryptography algorithms