RSA

In an earlier article I discussed the protocols of Public Key Algorithms. This discussion rested on their being 'one way functions', things which were easy to calculate in one direction, but hard to undo, unless a secret was known.

One such algorithm is RSA. RSA is not used to encode the message itself. Rather a random key is used in a 'symmetrical' algorithm to encode the message. This key is then encoded with RSA. The encoded key is sent with the encoded message.

One reason for this is speed, RSA is a slow algorithm compared to a symmetric algorithm, so encoding the whole message would be slow. There are other reasons it is done this way which have to do with the security of the system.

The RSA algorithm was invented in 1978 by three people: Ron Rivest, Adi Shamir, and Leonard Adleman. The algorithm bears their names. It relies upon one fact, it is much harder to factorise than multiply.

Consider the number 15, its factors are 3 and 5 because 3x5=15. It should not take you long to realise that 21 has factors 3 and 7. This seems easy.

What about the number 241568849? How long does it take you to find out its factors? (They are in the HTML source if you want to know)

Even with this fairly small number you should see that it's a 'hard' problem, much tougher than taking the two numbers to produce the multiple. The trick of RSA is to make this hard problem tough enough.

This is how RSA works, I'll leave the proof for others.

To generate a key, choose two large prime numbers. A number is prime if it can only be divided by 1 and itself without leaving a remainder.

We'll call these two numbers p and q.

As an example, let's choose p=17 and q=19. Note that in any real implementation the two numbers would be large.

One note, both p and q much be higher than the smallest number we wish to encrypt (note that computers deal in numbers, not text!) If we are encoding 8 bits at a time, then this should not be a problem, as numbers as small as 256 are insecure! p and q should be much higher.

Now find their product, n. Where n=pq.

In our case n=323

Find the number, m, where m=(p-1)(q-1). So, with our numbers that 16x18. m=288.

The next is tricky. We need to find a number, e, which is coprime to m. Two numbers are coprime if they share no common factors, e.g. 6 is not coprime to 8, because both are divisible by 2. However 8 is coprime to 9.

e needs to be a small number. We can find a number which is coprime using Euclid's algorithm.

In our case, let's choose e=5.

Now we need to find a value of d, such that de/m has the remainder of 1.

This is the same thing as finding a value of d for de =1 + xm, where x is any old whole number.

To do this, let's write down what we have.

e=5 m=288

x=1 de = 1 + 1x288  so de=289, so d=57.8  (no)
x=2 de = 1 + 2x288  so de=577, so d=115.4  (no)
x=3 de = 1 + 3x288  so de=865, so d=173    (yes!)

Thus we have d=173.

We can then publish our keys.

The public key consists of e and n.

The private key (which is not published) consists of d and n. All other figures such as m, p and q are discarded.

To encode the message, P (for plaintext) to the Ciphertext (C), we would use the following calculation.

C=Remainder of (Pe / n)

So if the P=23 (note this is different from the lower case p used above) we get

C = Remainder of (235 / 323)

235 means 23x23x23x23x23 - this is 6436343.

Dividing by 323 gives 19926 remainder 245, therefore C=245.

To decrypt we use a similar looking equation:

P=Remainder of (Cd / n)

'd' is known only to the recipient. Someone wishing to break the algorithm needs to establish 'd'.

This is hard to do as to find 'd' from 'e' and 'n' is tricky. To do this we would need to factorise 'n' in order to find 'm'.

In our case: P=Remainder of (245173 / 323)

This is a harder sum to do as d is larger than e, however there are methods which involve breaking the exponent into bits (based on multiples of 2). This is too tedious to go into here.

Remember, this is all done in the computer program, not manually. However it is slow. This is why a symmetric algorithm is used for the message, and RSA is used to encode the (smaller) key which is then transmitted alongside.