An RSA Example (C)

If we want to understand this public key encryption scheme, we need to follow the steps outlined below to generate our public and private keys.
  1. We pick two primes, naming them P and Q. For our example we'll use P=23, and Q=29. We also pick another working number, naming it K, preferably also a prime. We'll use K=31. Remember that, except where noted, all numbers need to be kept secret.
  2. We now create N = P * Q. In our case this equals 23*29 or 667. This is the "big" number that needs to be factored to crack the encryption. That is easy for this example, but hard for really big numbers.
  3. We now distribute N and the working number K. Together they represent our public key and anyone desiring to send us a secure message must use these two numbers. We'll show how in a minute.
  4. We also need to generate the so-called private key or decryption key that we will use to decrypt any message. We'll call it G.
    One important arithmetic tool you will need to follow this is modular arithmetic. This just means that we define a largest number and if we reach this, we wrap around to zero and continue. Most car odometers work modulo 100,000. That is, if we exceed 100 thousand, we just start over again. Notice that this is the same as our Java remainder operator % . Thus, a car's odometer gives us the mileage%100000 -- that is It only gives us the remainder after dividing by 100,000. In review: 8%100 yields 8, 88%100 yields 88, 888%100 also yields 88 since if we divide 888 by 100, we get 8; but more important, the remainder is 88. Another set of examples: 12 % 13 yields 12; but 100%13 yields 9 since 100/13 is 7 with a remainder of 9.
    First we define a value R = (P-1)*(Q-1). For our example, R = 22*28 = 616. We need to find a value for G such that the following equation is true using modulo R (or mod R) arithmetic: 
    K * G == 1
    At first it would seem that this could only be true if K and G were both equal to 1. But, that's the reason we are using mod R arithmetic. What we are really saying is that after dividing K*G by R, the remainder must be one, or: 
    (K * G) % R == 1
    Using our example values: 
    (31 * G) % 616 == 1
    Finding G is a bit tricky, but using a computer program and just trying different values works for these small examples. The correct answer for G is 159. To confirm this, 31*159 yields 4929. If we divide 4929 by 616 we get a quotient of 8 and a remainder of 1. So G = 159 is our private decryption key.
  5. The end result is that N= 667 and K=31 make up our public key. G = 159 is our private key.
We are now ready to try it out. We want to encrypt a message, call it M, using the public key and then show that with the private key we can recover the original number. With our small example, we can only encrypt a fairly small chunk of data. We'll have our correspondent send us a small integer, say M=65. If we just want to send numbers, that is fine. In practice, we want to send text, but since the computer represents each letter in a message as number anyway, then showing we can deal with numbers ensures that we could also be using letters. So, on to showing how she would encrypt the secret message, the number 65, and how we would decrypt the resulting number.
  1. The encrypted message, named C, is arrived at when she calculates 
    C =  (M^K)%N = (65^31)%667
    That is, all calculations are made mod N. Now it turns out that in calculating M to the Kth power, we get the correct answer even if at each step along the way, we apply the mod N operation. This keeps our number from getting too large. (FN: What we are using is the identity (x % y) * (x % y) == (x * x) % y.)
  2. The result is C = 103. This bears no resemblance to the original 65 and would seem to be a fairly secure way of keeping that value a secret.
  3. At the other end, we receive the message 103 and now need to apply our private key to see what she was trying to send us. We use the formula 
    M = (C^G)%N = (103^159)%667 = 65.
    Again, all of the calculations are done mod N and this results in our seeing her original message, 65. Success!

Breaking the Code

To break this code, the attacker needs to get the decryption key. The only way known to obtain this from the public key is to factor N. If N can be factored, then the attacker can generate the private key G just as we did. For our example, where N is 667, it does not take much to arrive at the factors 23 and 29. To make this system secure, we are counting on the fact that factoring a number N that has several hundreds of digits is beyond any current and expected compute capability.