   # A Coder's Notes

 Email : ren@techsolus.co.uk           # RSA Algorithm. As simple as I can get - 21/08/2013

p = 7
q = 5

n is simply p times q

n = p * q
n = 7 * 5
n = 35

z is p - 1 multiplied by q - 1

z = (p - 1) * (q - 1)
z = (7 - 1) * (5 - 1)
z = 6 * 4
z = 24

k is a prime number that is...
- less than z
- not a factor of z
- not the number 1
so z = 24. We can't use 1. Although 2 is a prime number 24 is divisible by 2 so we can't use 2. 3 is prime but 24 / 3 = 8 so 3 is a factor of 24. 5 is ok!!! so is 7, 11, 13, 17, 19 and 23
Lets say for clarity's sake that z came out at 352. We can't use 1 or 2. We can use 3 as 3 doesn't "go into" 352. Same with 5 and 7 but NOT 11! 352 / 11 = 32 with nothing left over. Choose a prime that doesn't "go into" z

We will choose k to be 7

k = 7

Our public key is now n = 35 and k = 7

To create our private key is complex(er). Our key is to be j and we use the formula
k * j = 1(mod z)

So...ahem...

7 * j = 1(mod 24)

mod 24???? when written 1(mod24) this means there will be a remainder of when when the number is divided by 24.

7 * j = (something divided by 24) remainder 1

or

(7 * j) / 24 = something remainder 1

we can guess
(7 * 1) / 24 = 7 / 24 = ermmmmm
(7 * 2) / 24 = 14 / 25 = ermmmmm
(7 * 3) / 24 = 21 / 24 = errrrrrmmmm
(7 * 4) / 24 = 28 / 24 = 1 r 4
(7 * 5) / 24 = 35 / 24 = 1 r 11
(7 * 6) / 24 = 42 / 24 = 1 r 18
(7 * 7) / 24 = 49 / 24 = 2 r 1 ............waoohoooo!!

so our private key is 7

Super duper...so how do we apply this.

The server sends is it's public key, actually 2 values of  n = 35 and k = 7. I receive the 2 numbers, 35 and 7. I want to send an encrypted message back, this time the number 14. So I apply the formula

m ^ k = c ( mod n )

m is the  message we want to encrypt
c is our encrypted message

So...

m = 8, the message we wish to send

8 ^ 7 = c(mod 35)
2,097,152 = c(mod 35)

2,097,152 / 35 = 59,918.62857.......... there's a remainder in there somewhere

59,918 * 35 = 2,097,130

2,097,152 - 2,097,130 = 22

I send the number 22...thats all

The server receives the number 22 and applies it's formula...

c ^ j = m ( mod n)
c is the encrypted message
j is the Server's secret key
m is the original message the server is looking for
n is the n part of the public key

So.....

22 ^ 7 = m(mod 35)

2,494,357,888 = m(mod 35)

2,494,357,888 / 35 = 71,267,368.2285714.....get the remainder

71,267,368 * 35 = 2,494,357,880

2,494,357,888 - 2,494,357,880 = 8...we've decrypted it!   