11 November 1999
Source: TIF images provided by Jean-Jacques Quisquater of 18-page hardcopy provided by Jean-François Misarsky. Set of 18 images http://cryptome.org/flannery-cp.zip (1.2MB)

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 f is substituted for the phi-symbol; e for epsilon; x for chi; b for beta; l for lamda; g for gamma. Errata welcome; send to jy@jya.com

Should anyone convert the full paper to TXT, HTML or Postscript, or know of an online source of the original, we'd appreciate a pointer or a copy to offer here.

[Document undated; apparently September 1999. Excerpts.]

Cryptography:
An Investigation of a New Algorithm vs. the RSA

Sarah Flannery, Blarney, Co. cork, Ireland

Contents

• Introduction

• Aim

• The RSA Algorithm

• The Cayley-Purser Algorithm

• Wherein lies the security of the Cayley-Purser Algorithm?

• Some differences between the RSA and Cayley-Purser Algorithms

• RSA vs. Cayley-Purser -- Empirical Time Analysis

• Graph: CP vs. RSA -- Comparison of Enciphering Times

• Conclusions

• Post Script: An Attack on the CP Algorithm

• Appendix of Programmes

    -- Mathematica Code for RSA Algorithm
    -- Mathematica Code for Cayley-Puser Algorithm

• Bibliography

Cryptography:

An Investigation of a New Algorithm vs. the RSA

Introduction

As long as there are creatures endowed with language there will be the desire for confidential communication -- messages intended for a limited audience. Governments, companies and individuals have a need to send or store information in such a way that on the intended recipient is able to read it. Generals send orders, banks send fund transfers and inviduals make purchases using credit cards. Cryptography is the study of methods to 'disguise' information so that only the intended receipient can obtain knowledge of its content. Public-Key Cryptography was first suggested in 1976 by Diffie and hellman and a public-key cryptosystem is one which has the property that someone who knows only how [to] encipher ('diguise') a piece of information CANNOT use the enciphering key to find the deciphering key without a prohibitively elngthy computation. This means that the information necessary to send private or secret messages, the enciphering algorithm along with the enciphering key, can be made public-knowledge by submitting them to a public directory. The first public-key cryptosystem, the RSA Alogirith, was developed by Ronald Rivest, Adi Shamir and Leionard Adleman at MIT in 1977. This system, described below, has stood the test of time and is today recognised as a standard of encryption worldwide.

Aim

This project investigates a possible new public-key algorithm, entitled the Cayley-Purser (CP) Algorithm and compares it to the celebrated RSA public-key algorithm. It is hoped that the CP Algorithm is

• As secure as the RSA Algorithm and

• FASTER than the RSA Algorithm

Firstly both algorithms are presented and whey they both work is illustrated. A mathematical investigation into the security of the Cayley-Purser algorithm is discussed in the main body of the report. Some differences between RSA and CP algorithms are then set out. Both algorithms are programmed using the mathematical package Mathematica and the results of an empirical run-time analysis are presented to illustrate the relative speed of the CP Algorithm.

RSA Public Key Cryptosystem

The RSA scheme works as follows:

Start Up: [This need be done only once.]

• Generate at random two prime numbers p and q of 100 digits or more.

• Calculate n = pq f(n) = (p-1)(q-1) = n - (p + q) + 1.

• Generate at random a number c < f(n) such that (c f(n)) = 1.

• Calculate the multiplicative inverse, d, of c (mod f(n)) using the Euclidean algorithm.

Publish: Make public the enciphering key,

K_E = (n, c)

Keep Secret: Conceal the deciphering key,

K_D = (n, d)

Enciphering: The enciphering trasnformation is,

C = f(P) = P^c (mod n)

Deciphering: The deciphering trasnformation is,

P = f^-1(C) = C^d (mod n)

Why the deciphering works:- The correctness of the deciphering algorithm is based on the following result due to Euler, which is a generalization of what is known as Fermat's little theorem. This result states that,

n^f(n) = 1 (mod n)

whenever (a, n) = 1, where f(n), Euler's-f function, is the number of positive integers less than n which are relatively prime to n.

When n = p, a prime, f(n) = p - 1, and we have Fermat's theorem:

a^p-1 = 1 (mod p) ; (a, p) = 1

If p|a then a^p = a = 0 (mod p), so that for any a,

a^p = a (mod p)

Now since d is the multiplicative inverse of c, we have

cd = 1 (mod f(n)) => cd = 1 + kf(n), k e Z

Now

f^-1(f(P)) = (P^c)^d = P^cd (mod n)

and

P^cd = P^{1| kf(n)} (mod n)      (for some integer k)

Now for P with (P, p) = 1, we have

P^p-1 = 1 (mod p) => P^kf(n)|1 = P (mod p) as p - 1|f(n)

This is trivially true when P = 0 (mod p), so that for all P, we have

P^cd = P^1+kf(n) = P (mod p)

Arguing similarly for q, we have for all P,

P^cd = P^1+kf(n) = P (mod q)

Since p and q are relatively prime, together these equations imply that for all P,

P^cd = P^1+kf(n) = P (mod n).

The Cayley-Purser Algorithm

Introduction

Since this algorithm uses 2 x 2 matrices and ideas due to Purser it is called the Cayley-Purser Algorithm. The matrices used are chosen from the multiplicative group G = GL(2, Z_n). the modulus n = pq, where p and q are both primes of 100 digits or more, is made public along with certain other parameters which be be described presently. Since

|GL(2, Z_n)| = nf(n)²(p + 1)(q +1)

we note that the order of G cannot be determined from a knowledge of n alone.

Plaintext message blocks are assigned numerical equivalents as in the RSA and placed four at a time in the four positions (ordered on the first index) of a 2 x 2 matrix. This message matrix is then trasnformed into a cipher matrix by the algorithm and the corresponding ciphertext is then extracted by reversing the assignment procedures used in the encipherment.

Because this algorithm uses nothing more than matrix multiplication (modulo n) and not modular exponentiation as required by the RSA it might be expected to encipher and decipher considerably faster than the RSA. This question was investigated, using the mathematical package Mathematica, by applying both algorithms to large bodies of text (see Tables I-IX) and it was found that the Cayley-Purser algorithm was approximately twenty-two times faster than the RSA with respect to a 200-digit modulus.

Needless to say if it could be shown that this algorithm is as secure as the RSA then it would recommend itself on speed grounds alone. The question of security of htis algorithm is disucssed after we have described it and wxplained why it works.

The CP Algorithm

Start Up:   procedure to be followed by B (the receiver):

• Generate two large primes p and q.

• Calculate the modulus n = pq.

• Determine x and a e GL(2, Z_n) such that x^a-1 /= ax.

• Calculate b = l^-1a^-1x.

• Calculate g = l^r ; r e N.

Publish: The modulus n and the parameters a, b, and g

[Snip four pages of equations.]

Some differences between the RSA and Cayley-Purser Algorithms

1. The most significant difference between the RSA and Cayley-Puser algorithm is the fact that the Cayley-Purser algorithm uses only modular matrix multiplication to encipher plaintext messages whereas the RSA uses modular exponentiation which requires considerably longer computation time. Even with the powerful Mathematica function PowerMod the RSA ppears (see Tables I - IX) to be over 20 times slower than the Cayley-Purser Algorithm.

2. In the RSA the parameters need to encihper -- (n, e) -- are published for the whole world to see and anyone qho wishes to send a message to Bob rasiers their messages' numerical equivalents to the power of e modulo n. However in the Cayley-Puser algorithm the enciphering key is not made public! Only the parameters for calculating one's owen 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 Cayley-Purser 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 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 Cayley-Purser 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 adn therefore can get the deciphering key, g^-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 possilbe advantage in this for Alice in that she could store encrypted messages on her computer ready for sending to Bob.

[Snip three pages if RSA-CP comparison tables]

Conclusions

This project

• (a) Shows mathematically that the CP algorithm is as secure as the RSA Algorithm.

• (b) Illustrates through an empirical run-time analysis that the CP Algorithm is FASTER to implement than the RSA Algorithm: the speed factor increasing with modulus size as shonw on the following table: -

Post Script: An Attack on the CP Algorithm

We describe an attack on the Cayley-Puser Algirthm which shows that with a knowledge of the public parameters a, b and g can form a multiple of l' and x. This matric x' can then be used in conjunction with e to form l = g^-1 which is the deciphering key. Thus the system as originally set out is 'broken'.

[Snip six pages of the attack, Mathmatica code and bibliography.]