RSA Algorithm Explained: a step-by-step process

The art of information hiding, or Cryptography, is one of my favorite applications of Mathematics in computer science. Information Hiding dates from thousand of years ago in “non-standard hieroglyphs carved into monuments from Egypt‘s Old Kingdom (ca 4500+ years ago)” [History of Cryptography]. It has different real-world applications ranging from credit-card security to online transactions in protected websites (those with the security lock). There are different approaches of information hiding, and the one used in the applications cited is the one first described by Rivest, Shamir and Adleman, the RSA. A great post about public key cryptography is summarized by Dr. Duke O’Connor on his website post “RSA is 30, and counting” about the 30th anniversary of the paper gave the origin to RSA:

R. Rivest, A. Shamir, L. Adleman.  A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, Vol. 21 (2), pp.120–126. 1978.

The application used on the Internet can be summarized in the following video:

If you want to teach your children :), take a look at this other video.

Dr. O’Connor summarizes two versions of the Mathematical foundation of the algorithm: one with the first flaw and the corrected version. The “fixed” version of the algorithm is what I had studied in school while studying Abstract Algebra, where the students were distributed into groups of three to implement their own Crypto systems and exchange keys and information in order to be tested. Of course, different assumptions were considered for the exercise. This post is just the output of the application I had developed in Java, what I called Cryptonline. I decided to use my free time to develop a Groovy on Grails Online Forum application where users can only see the messages if they login and use your public/private keys. The intention of the application is just for educational purposes. Read Dr. O’Connor’s post for background background information before moving on (in case you don’t have the background on it :D). As the T-Shirt says, it is just an algorithm.

Suppose you are transferring an important message over an unreliable communication channel such as a letter to someone, or simply to give your bank account to someone for transfer purposes.

As you can see, a reliable communication channel is the one where your message is encrypted and no one in between the sender and receiver can read it because the message is an arrangement that only you and the bank are capable of reading. The only way to do so is the creation of a keys that can lock and unlock the message hidden in the message. The RSA algorithm is based on the idea of Private and Public keys, where both are used to encode and decode the encrypted message. Suppose the string “John Smith” is the text to be decoded. Encryption is the process to hide the information on an Encrypted version and Decryption is the process of decoding the Encrypted text to its original format.

Of course, the idea is to have a key where you can distribute, so that only people you want to read the message can read it.

This is the basic idea of the algorithm. There are different variations of this algorithm depending on the application. Whenever you visit a website with the lock enabled means that any information exchanged between your computer and the visited website’s computer is encrypted.

By now you should have the background on this subject (considering you have gone to Dr. O’Connor’s website and read the Mathematical background). The source-code below is the actual output from Cryptonline, the one I developed back in 2000 at school. It is divided into 3 steps: Keys creation, Text Encryption and Text Decryption.

Public Key Creation

Let’s start from the Public Key.

-> Configuring random prime numbers
        P = 1277
        Q = 2311
-> Calculating public keys
          N = P * Q; N = 2951147
-> FI = (P-1) * (Q-1); FI = 2947560

-> Calculating (E)
           While MCD(n >= 2 , 2947560) != 1
           MCD(2 , 2947560) = 2
           MCD(3 , 2947560) = 3
           MCD(4 , 2947560) = 4
           MCD(5 , 2947560) = 5
           MCD(6 , 2947560) = 6
           MCD(7 , 2947560) = 7
           MCD(8 , 2947560) = 8
           MCD(9 , 2947560) = 3
           MCD(10 , 2947560) = 10
           MCD(11 , 2947560) = 11
           MCD(12 , 2947560) = 12
           MCD(13 , 2947560) = 1 Correct!
          E = 13

       Public Key (N,E) = (2951147 , 13)

Private Key Creation

The calculation of the Private Key is based on the matrix calculation of the Phi number, considering E.

-> Calculating private keys
         Initializing (p1,p2,p3) = (1, 0 , FI(n))
         Initializing (q1,q2,q3) = (0, 1 ,  E  ))
         While q3 != 0
             quoc = p3 / q3
             (t1,t2,t3) = (p1,p2,p3) - quoc * (q1,q2,q3)
             After, arrange the values:
             (p1,p2,p3) = (q1,q2,q3)
             (q1,q2,q3) = (t1,t2,t3)

           (13 <> 0) , then:
             quoc = 2947560 / 13 = 226735
             (t1,t2,t3) = (0,1,13) - 226735 * (1,-226735,5) = (1,-226735,5)
             (p1,p2,p3) = (1,-226735,5)
             (q1,q2,q3) = (1,-226735,5)

           (5 <> 0) , then:
             quoc = 13 / 5 = 2
             (t1,t2,t3) = (1,-226735,5) - 2 * (-2,453471,3) = (-2,453471,3)
             (p1,p2,p3) = (-2,453471,3)
             (q1,q2,q3) = (-2,453471,3)

           (3 <> 0) , then:
             quoc = 5 / 3 = 1
             (t1,t2,t3) = (-2,453471,3) - 1 * (3,-680206,2) = (3,-680206,2)
             (p1,p2,p3) = (3,-680206,2)
             (q1,q2,q3) = (3,-680206,2)

           (2 <> 0) , then:
             quoc = 3 / 2 = 1
             (t1,t2,t3) = (3,-680206,2) - 1 * (-5,1133677,1) = (-5,1133677,1)
             (p1,p2,p3) = (-5,1133677,1)
             (q1,q2,q3) = (-5,1133677,1)

           (1 <> 0) , then:
             quoc = 2 / 1 = 2
             (t1,t2,t3) = (-5,1133677,1) - 2 * (13,-2947560,0) = (13,-2947560,0)
             (p1,p2,p3) = (13,-2947560,0)
             (q1,q2,q3) = (13,-2947560,0)

         q3 is zero(0). Now, verify the value of p2. In case of negative, invert it by summing it with FI. (represent the negative number of z(n) by a positive.)

         u2 = 1133677;
         D = u2; D = 1133677

      Private Key (N,D) = (2951147, 1133677);

Using the Private and Public Keys

To summarize, the program outputs the keys used throughout the application.

#### All RSA Information ####

Public Key (N, E) = (2951147, 13)
Private Key (N, D) = (2951147, 1133677)

Of course you cannot give the original Prime Numbers to anybody since they are the factors that created the public and private key. So, the only key you can give away to other people is the Public one. Now, in order to illustrate Encryption and Decryption, my encryption machine uses ASCII-based character mapping for the Mathematical calculations. Consider my blog’s title as the input “Marcello de Sales: because solving problems is addicting”. Each character of the string is transformed into the ASCII added other numbers.

Encryption Process

-> Original Message
Marcello de Sales: because solving problems is addicting

-> Setting the receiver's public key
(N , E) = (2951147 , 13)

-> Transforming the message to ASCII code
177197214199201208208211132200201132183197208201215158132198201199197217215201132215211208218205210203132212214211198208201209215132205215132197200200205199216205210203

-> Configuring randomly selected blocks from the ASCII message
Bloco(x) = x ^ E mod N

Block(17) = 17 ^ 13 mod 2951147 = 2920887
Block(71) = 71 ^ 13 mod 2951147 = 1483408
Block(972) = 972 ^ 13 mod 2951147 = 363316
Block(1419) = 1419 ^ 13 mod 2951147 = 1419505
Block(920) = 920 ^ 13 mod 2951147 = 213548
Block(1) = 1 ^ 13 mod 2951147 = 1
Block(20) = 20 ^ 13 mod 2951147 = 93651
Block(8) = 8 ^ 13 mod 2951147 = 1394993
Block(2082) = 2082 ^ 13 mod 2951147 = 2878680
Block(1113) = 1113 ^ 13 mod 2951147 = 770001
Block(2200) = 2200 ^ 13 mod 2951147 = 2301917
Block(20113) = 20113 ^ 13 mod 2951147 = 787047
Block(2183) = 2183 ^ 13 mod 2951147 = 424239
Block(19) = 19 ^ 13 mod 2951147 = 1557862
Block(7) = 7 ^ 13 mod 2951147 = 2854397
Block(208) = 208 ^ 13 mod 2951147 = 375871
Block(2012) = 2012 ^ 13 mod 2951147 = 491468
Block(151) = 151 ^ 13 mod 2951147 = 2348470
Block(58) = 58 ^ 13 mod 2951147 = 966721
Block(13219) = 13219 ^ 13 mod 2951147 = 2596853
Block(820) = 820 ^ 13 mod 2951147 = 1336058
Block(11991) = 11991 ^ 13 mod 2951147 = 2624815
Block(97) = 97 ^ 13 mod 2951147 = 1340264
Block(21721) = 21721 ^ 13 mod 2951147 = 1760166
Block(52011) = 52011 ^ 13 mod 2951147 = 1685895
Block(32215) = 32215 ^ 13 mod 2951147 = 1202590
Block(21) = 21 ^ 13 mod 2951147 = 2752293
Block(1208) = 1208 ^ 13 mod 2951147 = 1414540
Block(21820) = 21820 ^ 13 mod 2951147 = 1733373
Block(5) = 5 ^ 13 mod 2951147 = 1879414
Block(21020) = 21020 ^ 13 mod 2951147 = 310870
Block(3132) = 3132 ^ 13 mod 2951147 = 519822
Block(212) = 212 ^ 13 mod 2951147 = 1315135
Block(2142) = 2142 ^ 13 mod 2951147 = 2430603
Block(1119) = 1119 ^ 13 mod 2951147 = 748920
Block(8208) = 8208 ^ 13 mod 2951147 = 2808982
Block(20) = 20 ^ 13 mod 2951147 = 93651
Block(1209) = 1209 ^ 13 mod 2951147 = 906866
Block(215) = 215 ^ 13 mod 2951147 = 396673
Block(13) = 13 ^ 13 mod 2951147 = 2564672
Block(2205) = 2205 ^ 13 mod 2951147 = 337248
Block(2) = 2 ^ 13 mod 2951147 = 8192
Block(151) = 151 ^ 13 mod 2951147 = 2348470
Block(32) = 32 ^ 13 mod 2951147 = 1191513
Block(197200) = 197200 ^ 13 mod 2951147 = 2266852
Block(200) = 200 ^ 13 mod 2951147 = 104075
Block(20) = 20 ^ 13 mod 2951147 = 93651
Block(519) = 519 ^ 13 mod 2951147 = 1459225
Block(9) = 9 ^ 13 mod 2951147 = 1601171
Block(21620) = 21620 ^ 13 mod 2951147 = 2477239
Block(5210) = 5210 ^ 13 mod 2951147 = 1598948
Block(203) = 203 ^ 13 mod 2951147 = 644537

-> Encrypted Message
2920887-1483408-363316-1419505-213548-1-93651-1394993-2878680-770001-2301917-787047-424239-1557862-2854397-375871-491468-2348470-966721-2596853-1336058-2624815-1340264-1760166-1685895-1202590-2752293-1414540-1733373-1879414-310870-519822-1315135-2430603-748920-2808982-93651-906866-396673-2564672-337248-8192-2348470-1191513-2266852-104075-93651-1459225-1601171-2477239-1598948-644537

Decryption Process

Upon receiving the encrypted message, the receiver needs to use the public key from the sender in order to decrypt the message. The receiver has the same encryption machine, but needs your public key in order to decipher it. The program developed decrypts the message as shown below.

-> Encrypted Message
2920887-1483408-363316-1419505-213548-1-93651-1394993-2878680-770001-2301917-787047-424239-1557862-2854397-375871-491468-2348470-966721-2596853-1336058-2624815-1340264-1760166-1685895-1202590-2752293-1414540-1733373-1879414-310870-519822-1315135-2430603-748920-2808982-93651-906866-396673-2564672-337248-8192-2348470-1191513-2266852-104075-93651-1459225-1601171-2477239-1598948-644537

-> Setting the private key
(N , D) = (2951147 , 1133677)

-> Decripting each block
Ascii(x) = x ^ D mod N

Ascii(2920887) = 2920887 ^ 1133677 mod 2951147 = 17
Ascii(1483408) = 1483408 ^ 1133677 mod 2951147 = 71
Ascii(363316) = 363316 ^ 1133677 mod 2951147 = 972
Ascii(1419505) = 1419505 ^ 1133677 mod 2951147 = 1419
Ascii(213548) = 213548 ^ 1133677 mod 2951147 = 920
Ascii(1) = 1 ^ 1133677 mod 2951147 = 1
Ascii(93651) = 93651 ^ 1133677 mod 2951147 = 20
Ascii(1394993) = 1394993 ^ 1133677 mod 2951147 = 8
Ascii(2878680) = 2878680 ^ 1133677 mod 2951147 = 2082
Ascii(770001) = 770001 ^ 1133677 mod 2951147 = 1113
Ascii(2301917) = 2301917 ^ 1133677 mod 2951147 = 2200
Ascii(787047) = 787047 ^ 1133677 mod 2951147 = 20113
Ascii(424239) = 424239 ^ 1133677 mod 2951147 = 2183
Ascii(1557862) = 1557862 ^ 1133677 mod 2951147 = 19
Ascii(2854397) = 2854397 ^ 1133677 mod 2951147 = 7
Ascii(375871) = 375871 ^ 1133677 mod 2951147 = 208
Ascii(491468) = 491468 ^ 1133677 mod 2951147 = 2012
Ascii(2348470) = 2348470 ^ 1133677 mod 2951147 = 151
Ascii(966721) = 966721 ^ 1133677 mod 2951147 = 58
Ascii(2596853) = 2596853 ^ 1133677 mod 2951147 = 13219
Ascii(1336058) = 1336058 ^ 1133677 mod 2951147 = 820
Ascii(2624815) = 2624815 ^ 1133677 mod 2951147 = 11991
Ascii(1340264) = 1340264 ^ 1133677 mod 2951147 = 97
Ascii(1760166) = 1760166 ^ 1133677 mod 2951147 = 21721
Ascii(1685895) = 1685895 ^ 1133677 mod 2951147 = 52011
Ascii(1202590) = 1202590 ^ 1133677 mod 2951147 = 32215
Ascii(2752293) = 2752293 ^ 1133677 mod 2951147 = 21
Ascii(1414540) = 1414540 ^ 1133677 mod 2951147 = 1208
Ascii(1733373) = 1733373 ^ 1133677 mod 2951147 = 21820
Ascii(1879414) = 1879414 ^ 1133677 mod 2951147 = 5
Ascii(310870) = 310870 ^ 1133677 mod 2951147 = 21020
Ascii(519822) = 519822 ^ 1133677 mod 2951147 = 3132
Ascii(1315135) = 1315135 ^ 1133677 mod 2951147 = 212
Ascii(2430603) = 2430603 ^ 1133677 mod 2951147 = 2142
Ascii(748920) = 748920 ^ 1133677 mod 2951147 = 1119
Ascii(2808982) = 2808982 ^ 1133677 mod 2951147 = 8208
Ascii(93651) = 93651 ^ 1133677 mod 2951147 = 20
Ascii(906866) = 906866 ^ 1133677 mod 2951147 = 1209
Ascii(396673) = 396673 ^ 1133677 mod 2951147 = 215
Ascii(2564672) = 2564672 ^ 1133677 mod 2951147 = 13
Ascii(337248) = 337248 ^ 1133677 mod 2951147 = 2205
Ascii(8192) = 8192 ^ 1133677 mod 2951147 = 2
Ascii(2348470) = 2348470 ^ 1133677 mod 2951147 = 151
Ascii(1191513) = 1191513 ^ 1133677 mod 2951147 = 32
Ascii(2266852) = 2266852 ^ 1133677 mod 2951147 = 197200
Ascii(104075) = 104075 ^ 1133677 mod 2951147 = 200
Ascii(93651) = 93651 ^ 1133677 mod 2951147 = 20
Ascii(1459225) = 1459225 ^ 1133677 mod 2951147 = 519
Ascii(1601171) = 1601171 ^ 1133677 mod 2951147 = 9
Ascii(2477239) = 2477239 ^ 1133677 mod 2951147 = 21620
Ascii(1598948) = 1598948 ^ 1133677 mod 2951147 = 5210
Ascii(644537) = 644537 ^ 1133677 mod 2951147 = 203

-> Complete message in ASCII
177197214199201208208211132200201132183197208201215158132198201199197217215201132215211208218205210203132212214211198208201209215132205215132197200200205199216205210203

-> Original Message
Marcello de Sales: because solving problems is addicting

This is fun! Now you can talk anything with your peers :D. Different practical applications are in Internet chat rooms. I’ve used Adium for Mac in order to chat through a secure communication channel over the Internet :). I keep thinking which the keys are when I’m communicating (when I’m bored…).