cryptographie 
22 November 1999: Sarah Flannery writes today the good news that she will put her paper online soon, free of any errors which may remain in this version. URL when it's available. 17 November 1999. Many thanks to Erick Wong for countless(!) typos corrected. Add William Whyte message on the successful attack on CayleyPurser. 13 November 1999. Add transcription of Mathematica code of the RSA and CP algorithms, which completes the HTML conversion of the full document. 12 November 1999: Add transcriptions of "The CayleyPurser Algorithm," "Wherein lies the security of the CayleyPurser Algorithm?," "Empirical Runtime Analysis," Post Script attack and Bibliography. Joe Author provided a PDF version of the 18 TIF images in a smaller package: http://cryptome.org/flannerycp.pdf (603KB). 11 November 1999 See press release: http://europa.eu.int/comm/dg12/press/1999/pr2509en.html See related January 1999 report: http://jya.com/flannery.htm In equations single letters are substituted for Greek characters. Double check all equations with original images. Errata welcome; send to jy@jya.com
[Document undated; apparently September 1999. Excerpts.] Cryptography:

[p  1, q  1]  <  (p  1)(q  1) __________ 
=  phi(n) ___ 
2  2 
(as (p  1, q  1) > 2) and since the order of SL (2, Z_{n}) is n phi(n)(p + 1)(q + 1) the maximum achievable order of a matrix in GL(2, Z_{n}) is
Thus if we can show that the probability of an element having a small order in Z_{n} is negligibly small then we will have shown that the order of an element chosen at random from GL(2, Z_{n}) is almost certainly of 'high order.'
If
and
then
with
Now the possible orders of the elements in Z_{n} are divisors of phi(n)/2 = 2p^{1}q^{1} and so are
and all of these orders are achieved by some elements. In fact by counting exactly how many elements correspond to each order we show that the probability of finding a unit in Z_{n} of order less than p^{1}q^{1} is negligibly small.
Recall that if a in Z_{p} has order k and b in Z_{q} has order l then the order of c in Z_{n} where
and
is [k, l], the least common multiple of k and l.
Now the possible orders of a and b in Z_{p} and Z_{q} are divisors of
respectively.
The following table lists the possible orders along with the number of elements of each order.
Z^{*}_{p}  Z^{*}_{q}  
Possible Orders 
No. of elements of that order 
Possible Orders 
No. of elements of that order 
1  1  1  1 
2  1  2  1 
p^{1}  p^{1}  1  q^{1}  q^{1}  1 
2p^{1}  p^{1}  1  2q^{1}  q^{1}  1 
By lifting elements in pairs via the CRT we obtain the elements corresponding to the different orders in Z_{n} along with number of elements of each order.
Order  Number  Reason 
1  1  [1, 1] = 1 
2  3  [1, 2] = [2, 1] = [2, 2] = 2 
p^{1}  p^{1}  1  [p^{1}, 1] = p^{1} 
q^{1}  q^{1}  1  [1, q^{1}] = q^{1} 
2p^{1}  3p^{1}  3  [2p^{1}, 1] = [p^{1}, 2] = [2p^{1}, 2] = 2p^{1} 
2q^{1}  3q^{1}  3  [1, 2q^{1}] = [2, q^{1}] = [2, 2q^{1}] = 2q^{1} 
p^{1}q^{1}  p^{1}q^{1}  p^{1}  q^{1 }+ 1  [p^{1}, q^{1}] = p^{1}q^{1} 
2p^{1}q^{1}  3p^{1}q^{1}  3p^{1 } 3q^{1} + 3  [2p^{1}, q^{1}] = [p^{1}, 2q^{1}] = [2p^{1}, 2q^{1}] = 2p^{1}q^{1} 
Note that if we sum all the individual counts we get exactly 4p^{1}q^{1} which is the number of elements of Z_{n}.
Explanation: To see how the number of elements corresponding to an order is obtained consider the last entry in the above array: An element of order 2p^{1}q^{1} in Z_{n} can be obtained in 3 different ways by lifting pairs of elements from Z_{p} and Z_{q}: One way is lifting the pair (a, b) where a has an order 2p^{1} and b has order q^{1}; another by lifting the pair (a, b) where a has an order p^{1} and b has order 2q^{1} and another by lifting the pair (a, b) where a has an order 2p^{1} and b has order 2q^{1}.
Regarding elements of order less than p^{1}q^{1} as elements of 'low order' we obtain the probability of choosing an element of order less than p^{1}q^{1} to be
4p^{1} + 4q^{1 } 4 ___________ 
4p^{1}q^{1} 
This is equivalent to
In the case where p and q are both of order of magnitude 10^{100} this probability is approximately
which, by any standards, is negligibly small.
1. The most significant difference between the RSA and the CayleyPurser algorithm is the fact that the CayleyPurser algorithm uses only modular matrix multiplication to encipher plaintext messages whereas the RSA uses modular exponentiation which requires a considerably longer computation time. Even with the powerful Mathematica function PowerMod the RSA appears (see Tables I  IX) to be over 20 times slower than the CayleyPurser Algorithm.
2. In the RSA the parameters needed to encipher  (n, e)  are published for the whole world to see and anyone who wishes to send a message to Bob raises their messages' numerical equivalents to the power of e modulo n. However in the CayleyPurser algorithm the enciphering key is not made public! Only the parameters for calculating one's own key are published. This means that every sender in this system also enjoys a certain measure of secrecy with regard to their own messages. One consequence of this is that the CayleyPurser algorithm is not susceptible to a repeated encryption attack because the sender, Alice, is the only one who knows the encryption key she used to encipher. In the RSA, however, if the order of e can be found then an eavesdropper can decipher messages.
3. Alice can choose to use a new enciphering key every time she wishes to write Bob. In the unlikely event that an eavesdropper, Eve, should find an enciphering key, she gains information about only one message and no information about the secret matrix c. By contrast, if a piece of intercepted RSA ciphertext leads to Eve being able to decipher (through repeated encryption, etc.), then she would be able to decipher all intercepted messages which are enciphered using the public exponent e.
4. In the CayleyPurser algorithm the sender, Alice, has the ability to decipher the ciphertext which she generates using Bob's public parameters even if she loses the original message (because she knows d and therefore can get the deciphering key, k^{1} = l!). Contrast this to the RSA  Alice cannot decipher her own message once she has enciphered it using Bob's public key parameters. There is a possible advantage in this for Alice in that she could store encrypted messages on her computer ready for sending to Bob.
Empirical TimeAnalysis
The times taken by the CayleyPurser and RSA algorithms (using a modulus n of the order 10^{200}) to encipher single and multiple copies of the Desiderata (1769 characters) by Max Ehrman are given in the following tables along with the times taken by both algorithms to decipher the corresponding ciphertext.
Running Time (Seconds) Message = 1769 characters 

Trial No.  1  2  3  Average 
RSA encipher  41.94  42.1  41.78  41.94 
RSA decipher  40.99  41.009  41.019  41.009 
CP encipher  1.893  1.872  1.893  1.886 
CP decipher  1.502  1.492  1.492  1.4953 
Table II
Running Time (Seconds) Message = 2 * 1769 = 3538 characters 

Trial No.  1  2  3  Average 
RSA encipher  72.364  72.274  72.364  72.334 
RSA decipher  70.942  70.952  72.144  71.346 
CP encipher  3.305  3.305  3.325  3.3016 
CP decipher  2.734  2.864  2.864  2.8206 
Table III
Running Time (Seconds) Message = 3 * 1769 = 5307 characters 

Trial No.  1  2  3  Average 
RSA encipher  103.078  102.808  103.489  103.125 
RSA decipher  101.246  101.076  104.06  102.1273 
CP encipher  4.757  4.737  4.747  4.747 
CP decipher  3.976  4.086  4.066  4.0426 
Table IV
Running Time (Seconds) Message = 4 * 1769 = 7076 characters 

Trial No.  1  2  3  Average 
RSA encipher  134.434  134.323  134.333  134.363 
RSA decipher  131.128  134.734  134.734  133.532 
CP encipher  6.159  6.048  6.109  6.1053 
CP decipher  5.227  4.967  4.967  5.05536 
Table V
Running Time (Seconds) Message = 12 * 1769 = 21228 characters 

RSA enc  RSA dec  CP enc  CP dec  
Time Taken  378.078  371.254  17.435  14.371 
Table VI
Running Time (Seconds) Message = 24 * 1769 = 42456 characters 

RSA enc  RSA dec  CP enc  CP dec  
Time Taken  509.523  511.455  22.583  18.767 
Table VII
Running Time (Seconds) Message = 48 * 1769 = 84912 characters 

RSA enc  RSA dec  CP enc  CP dec  
Time Taken  1019.24  1023.95  44.894  36.823 
Table VIII
Running Time (Seconds) Message = 144 * 1769 = 254736 characters 

RSA enc  RSA dec  CP enc  CP dec  
Time Taken  3154.21  3036.24  142.775  129.416 
With respect to a 133MHz machine the CayleyPurser Algorithm is on average
approximately 22 times faster than the RSA where in each case the modulus n
is of the order 10^{200}.
The following table illustrates the time taken for the RSA and CP Algorithms to encipher a piece of text (7076 characters in length) with varying size moduli. The ratio of the enciphering speeds is also given.
Running Time (Seconds) Message µ containing 7076 characters 

Modulus  RSA  CP  Ratio 
222 digits  84.641  3.916  21.6:1 
242 digits  104.71  4.036  25.9:1 
262 digits  118.841  4.276  27.8:1 
282 digits  131.739  4.326  30.5:1 
302 digits  145.689  4.487  32.5:1 
Note: The difference in times taken to encipher and ecipher in the RSA depends on the binary weight of the exponents e and d.
Number of Desiderata enciphered
The piece of text used (Desiderata) contains 1769 characters.
This project
Running Time (Seconds) Message = 4 * 1769 = 7076 characters 

Modulus  RSA  CP  Ratio 
222 digits  84.641  3.916  21.6:1 
242 digits  104.71  4.036  25.9:1 
262 digits  118.841  4.276  27.8:1 
282 digits  131.739  4.326  30.5:1 
302 digits  145.689  4.487  32.5:1 
We describe an attack on the CayleyPurser algorithm which shows that anyone with a knowledge of the public parameters a, b and g can form a multiple x' of x. This matrix x' can then be used in conjunction with e to form l = k^{1} which is the deciphering key. Thus the system as originally set out is 'broken'.
If x' = vx for some constant v and if e is known to an adversary then the calculation
yields the deciphering key k^{1}. Thus any multiple of x can be used to decipher.
In the CP system the matrix g is made to commute with with x so as to enable the deciphering process. This is done using the construction g = x^{r} for some r and herein lies the weakness of the algorithm. Were g to be generated more efficiently using a linear combination of x and the identity matrix I (higher order polynomials in l reduce via the CayleyHamilton theorem to linear expressions in l) the system is still compromised.
If the matrix g is nonderogatory (i.e. when g is reduced mod p and mod q neither of the two matrices obtained are scalar multiples of the identity) then
( If the matrix g is derogatory then n can be factorised by calculating GCD (g_{11}  g_{22} , g_{12} , g_{21} , n) )
Now since g is nonderogatory (v, n) = 1 and
for some d in Z_{n}.
Since
= vx^{1}a^{1}v^{1}x
= (v^{1}x)^{1}a^{1}(v^{1}x)
=> b = x'^{1}a^{1}x'
=> x'b = a^{1}x'
Substituting dI + g for x' in this last equation gives
=> db +gb = da^{1} + a^{1}g
=> d[b  a^{1}] = [a^{1}g  gb]
Since a /= b^{1} these matrices differ in at least one position. For argument's sake let a_{11} /= b_{11}^{1}. Comparing the (1, 1) entries in the above matrix identity gives
If (a_{11}  b_{11}^{1})^{1} exists mod n the above linear congruence is uniquely solvable for d. If not a factorisation of n is obtained.
Remark 1: This attack shows that anyone with a knowledge of the public parameters a, b and g can form a multiple x' of x. This matrix x' can then be used to form l = k^{1} provided e is known. If e is transmitted securely on a once off basis then knowledge of a x' on its own is not enough to break the system, though then the CayleyPurser Algorithm would no longer be publickey in nature.
Remark 2: The fact that a derogatory g leads to a factorisation of the modulus n was further investigated on the assumption that knowledge of n might not severely compromise the system. However in this case also a multiple of x is obtainable.
Remark 3: An analysis of the CP algorithm based on 3 x 3 matrices, though slightly more involved in its details, leads to conclusions similar to the ones just described.
Remark 4: For the sake of efficiency s should be calculated as s = ag + bI rather than as s = g^{t}.
_______________________________________________________________ FirstPrimeAbove[n Integer] (Clear[k];k = n;While[! PrimeQ[k],k = k + 1];k) _______________________________________________________________ ConvertString[str_String] := Fold[Plus[256 #1, #2]&, 0, ToCharacterCode[str]] _______________________________________________________________ StringToList[text_string] := Module[{blockLength = Floor[N[Log[256, n]]], strLength = StringLength[text]}, ConvertString /@ Table[StringTake[text,{i, Min[strLength, 1 + blockLength  1]}],{i, 1, strLength, blockLength}]] _______________________________________________________________ ConvertNumber[num_Integer]:= FromCharacterCode /@ IntegerDigits[num,256] _______________________________________________________________ ListToString[l_List] := StringJoin[ConvertNumber /@ 1]
_______________________________________________________________ GeneratePQNED[digits_Integer] := (p = FirstPrimeAbove[ prep = Random[Integer, {10^{(digits1)}, 10^{digits}1}]]; Catch[Do[preq = Random[Integer, 10^(digits1), 10^digits1}]; If[preq[=[re[,Throw[q = FirtPrimeAbove[preq]]], {100}]] n = pq;e = Random[Integer, {p, n}]; While[GCD[e, (p1) (q1) i = 1, e = Random[Integer, {p, n}]]; e; d = PowerMod[e, 1 (p1) (q1)];) _______________________________________________________________ RSAencNumber[num_Integer] := PowerMod[num, e, n] _______________________________________________________________ RSAdecNumber[num_Integer] := PowerMod[num, d, n] _______________________________________________________________ RSAenc[text_String]:= RSAencNumber[#]& /@ StringToList[text] _______________________________________________________________ RSAdec[cipher_List]:=ListToString[RSAdecNumber[#]&/@cipher]
_______________________________________________________________ StringToMatrices[text_String]:= Partition[Parition[Flatten [Append[StringToList[text],{32,32,32}]],2],2] _______________________________________________________________ MatriceToString[l_List] := StringJoin [ ConvertNumber/@Flatten[1]] _______________________________________________________________ CPpqn[digits_Integer] :=Module[{ p1 = FirstPrimeAbove[Random[Integer, {10^(Floor[digits/2]1), 10^(Floor[digits/2])1}]], q1 = FirstPrimeAbove[Random[Integer, {10^(Floor[digits/2]1), 10^(Floor[digits/2])1}]], While[PrimeQ[p = 2p1 +1], p1 = FirstPrimeAbove[p1 + 1]]; p; While[PrimeQ[q = 2q1 +1], q1 = FirstPrimeAbove[q1 + 1]]; q; n = pq; ] _______________________________________________________________ randmatrix := (Catch[ Do[m = Table[Random[Integer, {0, n}], {i, 1, 2}, {j, 1, 2}]; If[GCD[Mod[Det[m], n], n] == 1, Throw[m]], {1000}]]) _______________________________________________________________ inv[a_] := (d = Mod[Det[a], n]; i = PowerMod[d, 1, n]; {{Mod[i * a[[2, 2]], n], Mod[i * a[[1, 2]], n]}, {Mod[i * a[[2, 1]], n], Mod[i * a[[1, 1]], n]}}) _______________________________________________________________ mmul[j_, k_] := Mod[ {{Mod[j[[1, 1]]*k[[1, 1]], n] + Mod[j[[1, 2]]*k[[2, 1]], n], Mod[j[[1, 1]]*k[[1, 2]], n] + Mod[j[[1, 2]]*k[[2, 2]], n}}, {Mod[j[[2, 1]]*k[[1, 1]], n] + Mod[j[[2, 2]]*k[[2, 1]], n], Mod[j[[2, 1]]*k[[1, 2]], n] + Mod[j[[2, 2]]*k[[2, 2]], n]}}, n] _______________________________________________________________ CPparameters := (identity = {{1, 0}, {0, 1}}; alpha = randmatrix; Catch[Do[chi = randmatrix; If[mmul[chi, alpha] ! = mmul[alpha, chi], Throw[chi]], {10000000}]] chiinv = inv[chi]; alphainv = inv[alpha]; Catch[Do[s = Random[Integer, {2, 50}]; gamma = Mod[MatrixPower[chi, s], n]; If[gamma != identity, Throw[gamma]], {10000000}]]; Catch[Do[delta = Mod[Mod[Random[Integer, {1, n1}]gamma, n] + Mod[Random[Integer, {1, n1}]identity, n], n] If[delta !=identity && mmul[delta, alpha] !=mmul[alpha, delta], Throw [delta]], {10000000}]; beta = mmul[mmul[chiinv, aphainv], chi]; deltainv = inv[delta]; epsilon = mmul[mmul[deltainv, alpha], delta]; kappa = mmul[mmul[deltainv, beta], delta]; lambda = mmul[mmul[chiinv, epsilon], chi];) _______________________________________________________________ CPenc[plain_String] := CPencNum [ StringToMatrices[plain]] _______________________________________________________________ CPDecNum[l_list] := Table[mmul[mmul[lambda, l[[i]]], lambda], {i, Length[l]}] _______________________________________________________________ CPEncNum[l_List] := Table[mmul[mmul[kappa, l[[i]]], kappa], {i, Length[l]}] _______________________________________________________________ CPdec[cipher_List] := MatricesToString[CPDecNum[cipher]]
Higgins, J and Cambell, D: "Mathematical Certificates." Math. Mag 67 (1994). 2128.
Mackiw, George: "Finite Groups of 2 x 2 Integer Matrices." Math. Mag 69 (1996). 356361.
Meijer, A.R.: "Groups, Factoring and Cryptography." Math. Mag 69 (1996). 103109.
Menezes, van Oorschot, Vanstone: Handbook of Applied Cryptography, CRC Press 1996.
Salomaa, Arto: PublicKey Cryptography (2 ed.). Springer Verlag 1996.
Schneier, Bruce: Applied Cryptography. Wiley 1996.
Stangl, Walter D.: "Counting Squares in n." Math. Mag 69 (1996). 285289.
Sullivan, Donald: "Square Roots of 2 x 2 Matrices." Math. Mag 66 (1993). 314316.
From: "William Whyte" <wwhyte@baltimore.ie> To: "Jim Gillogly" <jim@acm.org>, "John Young" <jya@pipeline.com> Subject: RE: Flannery on CayleyPurser/RSA Date: Thu, 11 Nov 1999 18:10:21 0000 Hi Jim, > My take from her remark in that paper is that > the system is broken as it stands, and that there's no hint yet of a > repair. This is correct; the system as published by Sarah, and posted on the Cryptome website, is broken. The reason why the project still says that it's secure is to do with the rules of the science fair that Sarah entered the project in. As you remember, she won the Young Scientist award in January with the original CayleyPurser project, which stated that the algorithm was secure. Afterwards, myself, Michael Purser, and Sarah discovered an attack against the presented algorithm that appears pretty definitive. However, for the European Young Scientists fair, the project submitted had to be the same as the project for which you won your national prize, with the exception that you could add appendices. So that's what happened: the original project, submitted verbatim, claims the system is secure; the appendix, written afterwards, exposes the attack. It might be worth htmlising the attack and posting it, too.... Baltimore's official position is that we wish Sarah well, we continue to investigate new cryptosystems, and that the security or otherwise of the CayleyPurser algorithm doesn't affect our core business, which is building open, standardsbased Public Key Infrastructures. In a world where RSA will shortly be free, and where substantial investment has already been made in infrastructures based on existing algorithms, it seemed unlikely that CayleyPurser would ever be a commerical proposition anyway. I did make one misleading statement, right at the start of the press excitement, when I said in various forums that the security was based on the difficulty of factorisation and was assumed to be exactly as strong as RSA. Blame the excitement of the times; we hadn't looked at the system ourselves in almost a year and in the rush I posted before pausing to make sure I had my details right. I'll do better next time (if there is a next time). Cheers, William
