RSA Processing: The mathematical secret

Joe Wilkinson

RSA Encryption

Encryption depends on some properties of whole numbers and Modulus arithmetic. It uses the equation
C = M^e MOD n for encryption where

n	is a product of two prime numbers
e	is a number chosen in conjuction with n
M	is a single message unit, e.g. the ASCII code of a Character
C	is the encrypted message unit, ready to be transmitted

So a message consisting of the bytestream: M1, M2, M3, M4, M5 etc,
are transformed into the encrypted bytestream: C1, C2, C3, C4, C5 etc.

RSA Decryption

When the encrypted bytestream is received it is processed in a very similar way using the equation
M = C^d MOD n, where d is calculated from e and n
and C1, C2, C3, C4, C5 is changed back to the original M1, M2, M3, M4, M5

The relationship between n, e, and d

For this process to work, the values are related as follows:

n	*= p1p2**	the product of primes, as above
e	is chosen	to be relatively prime to *(p1-1)(p2-1)**
d	satisfies the equation:	*d e MOD {(p1-1)(p2-1)} = 1*

Breaking the code

It is obviously easiest for the person who gives out the public key (e,n), since they know p1 and p2. However it is clear that if n can be factorised, and e is known, d can be calculated.

Avoiding Over-large Numbers

When raising numbers to even reasonable sized powers, large numbers are produced. As is shown on the Example sheet, 6^13 exceeds the integer calculation power of a well known spreadsheet. Both in the spreadsheet that can be downloaded and experimented with, and in any sensible programming algorithm, the problem is avoided by carrying out the Modulus process after each multiplication. So instead of working out 5^13 = 1220703125, and then dividing by 77 and then finding the remainder =26, it is usually more efficient to find the value in stages.

Power	5	Modulus 77
2	5 * 5 = 25	25 MOD 77 = 25
3	25 * 5 = 125	125 MOD 77 = 48
4	48 * 5 = 240	240 MOD 77 = 9
5	9*5 = 45	45 MOD 77 = 45
etc