Cayley–Purser algorithm: Difference between revisions

Revision as of 14:44, 3 October 2019

Revision as of 14:36, 7 May 2021

Line 22:

=== Key generation ===

Like RSA, Cayley-Purser begins by generating two large primes ''p'' and ''q'' and their product ''n'', a [[semiprime]]. Next, consider [[general linear group|GL]](2,''n''), the [[general linear group]] of 2×22×2 matrices with integer elements and [[modular arithmetic]] mod ''n''. For example, if ''n''=5, we could write:

:<math>\left[\begin{matrixbmatrix}0 & 1 \\ 2 & 3\end{matrixbmatrix}\right] +

\left[\begin{matrixbmatrix}1 & 2 \\ 3 & 4\end{matrixbmatrix}\right] =

\left[\begin{matrixbmatrix}1 & 3 \\ 5 & 7\end{matrixbmatrix}\right] =\equiv

\left[\begin{matrixbmatrix}1 & 3 \\ 0 & 2\end{matrixbmatrix}\right]</math>

:<math>\left[\begin{matrixbmatrix}0 & 1 \\ 2 & 3 \end{matrixbmatrix}\right]\left[ \begin{matrixbmatrix}1 & 2 \\ 3 & 4\end{matrixbmatrix}\right] =

\left[\begin{matrixbmatrix}3 & 4 \\ 11 & 16\end{matrixbmatrix}\right] =\equiv

\left[\begin{matrixbmatrix}3 & 4 \\ 1 & 1\end{matrixbmatrix}\right]</math>

This group is chosen because it has large order (for large semiprime ''n''), equal to (''p''²-1−1)(''p''²-−''p'')(''q''²-1−1)(''q''²-−''q'').

Let <math>\chi</math> and <math>\alpha</math> be two such matrices from GL(2,''n'') chosen such that <math>\chi\alpha^{-1} \not= \alpha\chi</math>. Choose some natural number ''r'' and compute:

Line 74:

:<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> &mdash;— 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.

==See also==

* [[Non-commutative cryptography]]

== References ==