Welcome to NRICH.

 
The Cayley Purser Algorithm and RSA
By Amars Birdi (P2769) on Thursday, August 3, 2000 - 04:57 pm:

All right, in case you don’t know about the Cayley Purser algorithm it is meant to be an encryption algorithm that is at least as secure as another algorithm called the RSA algorithm. However, the RSA algorithm is an old bench standard as it has withstood the test of time and has been used by banks all over the world as well as by governments for secure communications. This is all well and fine, however, the RSA algorithm is quite tediously slow! So, a 16 year old girl ( called Sarah Flannery ) had the bright idea of somehow using matrices to create a super fast, super efficient algorithm called the Cayley Purser algorithm. I just want to know how it works!

There is a web site that explains the mathematics behind the Cayley Purser algorithm and I would hope that someone could explain the various concepts that it involves ( as well as the concepts involved in the RSA algorithm!).
The web page is :

http://cryptome.org/flannery-cp.htm

By Dan Goodman (Dfmg2) on Sunday, August 6, 2000 - 03:04 am:

Something to note, at the bottom of that webpage, it has an additional note saying that they found an attack on the algorithm which demonstrates that it is not as secure as the RSA algorithm.

I can still write a bit about RSA, but can you give us an idea about what level to pitch it at? For instance, do you know about modular arithmetic (sometimes called clock arithmetic)? Do you know about algorithmic complexity (e.g. an algorithm might have complexity O(n2))?

By Amars Birdi (P2769) on Tuesday, August 8, 2000 - 03:33 pm:

Thanks for the response. I would really be interested in any literature about the RSA or other cyrptography algorithms you could offer. However, as far as my knowledge as maths goes in this area, I only know about modular arithmetic-not algorithmic complexity ( whatever that is!). I would appreciate fairly simple maths (I only do A-level maths).

By Dan Goodman (Dfmg2) on Tuesday, August 8, 2000 - 08:16 pm:

Right, if you know about modular arithmetic, you know enough to understand how it works, but not why it's hard to crack. Actually, algorithmic complexity is quite a simple idea, it's basically measuring how many steps it takes an algorithm to finish. For instance, to find the smallest integer k such that k2>n, one algorithm would be: let k=0, (1) compute k2, is k2>n? If so, finish, otherwise increase k by 1 and go to (1). This algorithm takes about sqrt(n) steps. If an algorithm takes less than some constant k times a function f(n) steps to complete, we say that the algorithm is O(f(n)). So, the above algorithm is O(sqrt(n)). For a coding system, you want the decryption algorithm to be something like O(2n), where n is the number of digits in the key, because then adding an extra digit doubles the amount of time it takes for them to crack your code, and you can easily just add enough digits to stop them being able to crack the code.

On to RSA, there's a couple of things in the area of modular arithmetic that you probably need to know before getting on to RSA. Two integers n and m are coprime if they have no common factor (that is there is no integer p such that p divides both n and m). We write (n,m)=1 if this is true, (n,m) is the usual notation for the highest common factor of n and m. The function phi(n) is called the Euler totient function, it is the number of integers a with 1<=a<n such that a is coprime to n. If p is a prime number, you can see that phi(p)=(p-1), because there can be no common factors between p and a number less than p. You can also show that if two integers n and m are coprime, then phi(nm)=phi(n).phi(m). So if p and q are both prime, then phi(pq)=phi(p)phi(q)=(p-1)(q-1).

Now comes the modular stuff. Euler's Theorem (also called the Euler-Fermat theorem) says that aphi(n)=1 (mod n) if a¹0 (mod n). Moreover, Bezout's theorem says that if two integers n and m are coprime, then we can find integers a and b such that an+bm=1.

Now we can do the RSA bit. Suppose we've encoded our message into a string of numbers x1, x2, etc. What we want is an encoding function E(x) and a decoding function D(x) (so that D(E(x))=x). Moreover, we want to tell people what E(x) is, but not what D(x) is, and we don't want them to be able to work out D from knowing E. This is the basic idea behind any public key cryptography system. In RSA, you choose two very large prime numbers p and q (you want them to be about 100 digits or so), and let n=pq. Now you choose an encoding digit e which is coprime to phi(n)=(p-1)(q-1), this will be easy enough to do (details if you want them). The encoding function is E(x)=xe (mod n). Using Bezout's theorem (above), we can find an integer d such that ed+k.phi(n)=1. The decoding function is D(x)=xd (mod n). We can see that this does decode it, because D(E(x))=(xe)d=xed=x1+k.phi(n)=x.(x phi(n))k=x.(1)k=x (mod n), using the fact that ed=1+k.phi(n) and also Euler's theorem xphi(n)=1 (mod n). Now, all we have to do is publish e and n (but not d, p or q!), and people can send us messages which only we can read, they can't even decode it themselves.

The security and practicality of this algorithm lies in the fact that (a) to find d, you need to know phi(n), (b) to find phi(n) you need to know p and q, (c) to find p and q you have to prime factorise n, this is suspected to be a very hard task for large numbers, certainly, no-one has yet found a quick way of doing it (or have they? is the NSA watching even now?). The practicality of the RSA scheme lies in the fact that computing e and d is quick for you to do, and that encoding and decoding messages is also quick (using a neat trick for computing large powers) once you know the keys (OK, it's not that quick, but it's quick enough).

Alright, that tells you the absolute minimum you need to know for RSA, I haven't proved any of the theorems or actually given any algorithmic specifics (like how to find e and d), but I can fill in these details if you're interested? If you do a search on the internet, you should be able to find lots more information about stuff like this. A good place to start is http://mathworld.wolfram.com. Alternatively, you can go the RSA web page http://www.rsa.com, although you'll probably find your name is put on an NSA computer if you go to this webpage, but if you search for RSA you'll be on their database anyway! Paranoia strikes :)