Editing Cayley–Purser algorithm (section)

== 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.