asp.net consultancy chorley ASP.NET Server Side Scripting Wigan
Website Development Radcliffe

IT Services And Support

Email : ren@techsolus.co.uk
Mobile Phone : 0788 68 41 411
Answerphone : 01204 469683
bespoke invoice systems Standish Information Technology Advice Worsley
    development systems Ramsbottom
data manipulation Farnworth access databases Whitefield SQL connections Atherton
online accessible software Leyland software compatible Coppull


Get connected and Online Tottington
remote management Makerfield code and design Aspull

RSA Algorithm. As simple as I can get - 21/08/2013

Start with 2 prime numbers...

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!

Post A Comment

Name Comment
programming services asp.net specialist
Valid XHTML 1.0 Transitional
Admin
GD