View difference between Paste ID: d9sSvxVJ and Kh5fhn1t
SHOW: | | - or go back to the newest paste.
1-
Section1. Generating Public and Private Keys
1+
Section1. Generating Public and Private Keys
2-
First, as we mentioned above, before any transmission happens, the Server had calculated its public and secret keys.  Here is how. 
2+
First, as we mentioned above, before any transmission happens, the Server had calculated its public and secret keys.  Here is how. 
3-
3+
4-
1.1) pick two prime numbers, we'll pick p = 3 and q = 11
4+
1.1) pick two prime numbers, we'll pick p = 3 and q = 11
5-
1.2) calculate n = p * q = 3 * 11 = 33
5+
1.2) calculate n = p * q = 3 * 11 = 33
6-
1.3) calculate z = ( p - 1 ) * ( q - 1 ) = ( 3 - 1 ) * ( 11 - 1 ) = 20
6+
1.3) calculate z = ( p - 1 ) * ( q - 1 ) = ( 3 - 1 ) * ( 11 - 1 ) = 20
7-
1.4) choose a prime number k, such that k is co-prime to z, i.e, z is not divisible by k. We have several choices for k: 7, 11, 13, 17, 19 (we cannot use 5, because 20 is divisible by 5). Let's pick k=7 (smaller k, "less math").
7+
1.4) choose a prime number k, such that k is co-prime to z, i.e, z is not divisible by k. We have several choices for k: 7, 11, 13, 17, 19 (we cannot use 5, because 20 is divisible by 5). Let's pick k=7 (smaller k, "less math").
8-
1.5) So, the numbers n = 33 and k = 7 become the Server's public key.
8+
1.5) So, the numbers n = 33 and k = 7 become the Server's public key.
9-
1.6) Now, still done in advance of any transmission, the Server has to calculate it's secret key. Here is how.
9+
1.6) Now, still done in advance of any transmission, the Server has to calculate it's secret key. Here is how.
10-
1.7) k * j = 1 ( mod z )
10+
1.7) k * j = 1 ( mod z )
11-
1.8) 7 * j = 1 ( mod 20 )
11+
1.8) 7 * j = 1 ( mod 20 )
12-
1.9) ( 7 * j ) / 20 = ? with the remainder of 1 (the "?" here means: "something, but don't wory about it"; we are only interested in the remainder). Since we selected (on purpose) to work with small numbers, we can easily conclude that 21 / 20 gives "something" with the remainder of 1. So, 7 * j = 21, and j = 3. This is our secret key. We MUST NOT give this key away.
12+
1.9) ( 7 * j ) / 20 = ? with the remainder of 1 (the "?" here means: "something, but don't wory about it"; we are only interested in the remainder). Since we selected (on purpose) to work with small numbers, we can easily conclude that 21 / 20 gives "something" with the remainder of 1. So, 7 * j = 21, and j = 3. This is our secret key. We MUST NOT give this key away.
13-
13+
14-
Now, after the Server has done the above preparatory calculations in advance, we can begin our message transmission from our Browser to the Server. First, the Browser requests from the Server, the Server's public key, which the Server obliges, i.e., it sends n=33 and k=7 back to the Browser.  Now, we said that the Browser has a Plain message P=14, and it wants to encrypt it, before sending it to the Server. Here is how the encryption happens on the Browser.
14+
Now, after the Server has done the above preparatory calculations in advance, we can begin our message transmission from our Browser to the Server. First, the Browser requests from the Server, the Server's public key, which the Server obliges, i.e., it sends n=33 and k=7 back to the Browser.  Now, we said that the Browser has a Plain message P=14, and it wants to encrypt it, before sending it to the Server. Here is how the encryption happens on the Browser.
15-
15+
16-
Section 2. Encrypting the message
16+
Section 2. Encrypting the message
17-
Here is the encryption math that Browser executes.
17+
Here is the encryption math that Browser executes.
18-
18+
19-
2.1) P ^ k = E ( mod n ) 
19+
2.1) P ^ k = E ( mod n ) 
20-
"^" means "to the power of"
20+
"^" means "to the power of"
21-
P is the Plain message we want to encrypt
21+
P is the Plain message we want to encrypt
22-
n and k are Server's public key (see Section 1)
22+
n and k are Server's public key (see Section 1)
23-
E is our Encrypted message we want to generate
23+
E is our Encrypted message we want to generate
24-
24+
25-
After plugging in the values, this equation is solved as follows:
25+
After plugging in the values, this equation is solved as follows:
26-
2.2) 14 ^ 7 = E ( mod 33 )
26+
2.2) 14 ^ 7 = E ( mod 33 )
27-
This equation in English says: raise 14 to the power of 7, divide this by 33, giving the remainder of E.
27+
This equation in English says: raise 14 to the power of 7, divide this by 33, giving the remainder of E.
28-
2.3) 105413504 / 33 = 3194348.606 (well, I lied when I said that this is "Pencil and Paper" method only. You might want to use a calculator here).
28+
2.3) 105413504 / 33 = 3194348.606 (well, I lied when I said that this is "Pencil and Paper" method only. You might want to use a calculator here).
29-
2.4) 3194348 * 33 = 10541348
29+
2.4) 3194348 * 33 = 10541348
30-
2.5) E = 105413504 - 10541348 = 20
30+
2.5) E = 105413504 - 10541348 = 20
31-
31+
32-
So, our Encrypted message is E=20.  This is now the value that the Browser is going to send to the Server. When the Server receives this message, it then proceeds to Decrypt it, as follows.
32+
So, our Encrypted message is E=20.  This is now the value that the Browser is going to send to the Server. When the Server receives this message, it then proceeds to Decrypt it, as follows.
33-
33+
34-
Section 3. Decrypting the Message
34+
Section 3. Decrypting the Message
35-
Here is the decryption math the Server executes to recover the original Plain text message which the Browser started with.
35+
Here is the decryption math the Server executes to recover the original Plain text message which the Browser started with.
36-
36+
37-
3.1) E ^ j = P ( mod n)
37+
3.1) E ^ j = P ( mod n)
38-
E is the Encrypted message just received
38+
E is the Encrypted message just received
39-
j is the Server's secret key
39+
j is the Server's secret key
40-
P is the Plain message we are trying to recover
40+
P is the Plain message we are trying to recover
41-
n is Server's public key (well part of; remember that Server's public key was calculated in Section 1 as consisting of two numbers: n=33 and k=7).
41+
n is Server's public key (well part of; remember that Server's public key was calculated in Section 1 as consisting of two numbers: n=33 and k=7).
42-
42+
43-
After plugging in the values:
43+
After plugging in the values:
44-
3.2) 20 ^ 3 = P ( mod 33 )
44+
3.2) 20 ^ 3 = P ( mod 33 )
45-
3.3) 8000 / 33 = ? with the remainder of P.  So to calculate this remainder, we do:
45+
3.3) 8000 / 33 = ? with the remainder of P.  So to calculate this remainder, we do:
46-
3.4) 8000 / 33 = 242.424242...
46+
3.4) 8000 / 33 = 242.424242...
47-
3.5) 242 * 33 = 7986
47+
3.5) 242 * 33 = 7986
48-
3.6) P = 8000 - 7986 = 14, which is exactly the Plain text message that the Browser started with!
48+
3.6) P = 8000 - 7986 = 14, which is exactly the Plain text message that the Browser started with!
49-
49+
50
Well that's about it. While we did not discuss the theory behind the formulae involved I hope that you got at least a basic idea of how the public key cryptography using the RSA algorithm works.