Cayley–Purser algorithm: Difference between revisions

Revision as of 16:45, 6 June 2014

Revision as of 00:02, 13 February 2015

Line 65:

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>\deltad \left(\beta_{11}^{-1}beta - \alpha_alpha^{11-1}\right) \equiv \epsilonleft(\alpha^{-1}\gamma - \gamma\beta\right) \pmod n</math>

Observe that a solution exists iff for some <math>i, j \in \left|\gamma\right|</math> and <math>x, y \in \mathbb{Z}_n</math>

for <math>\delta</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.

:<math>x\left(\beta_{ij}^{-1} - \alpha_{ij}\right) \equiv y \pmod n.</math>

forIf <math>\deltad</math>, whereis known, <math>d \alpha_mathrm{11I}, + \beta_{11}gamma = \chi'</math> are&mdash; thea top-left elementsmultiple of <math>\alpha, \betachi</math>. Since anyAny multiple of <math>\chi</math> canyields be<math>\lambda used= to\kappa^{-1} decipher,= v^{-1}\chi^{-1} \epsilon v\chi</math>. thisThis presents a fatal weakness for the system, thatwhich 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.