Monday June 19, 2000

In order to show that there is a useful application of the program you are working on, let us look at the problem of encrypted data. One of the best known and most widely used techniques today to encrypt data is known as the RSA algorithm.

The procedure followed in this algorithm is to first choose two large prime number and form their product, say p and q. Then compute what is known as the Euler-phi function of the number, which in this case is (p-1)*(q-1).

Take the data we want to encrypt and encode it. One way of doing it is with ASCII code. Once we have the characters converted to numbers, we then pick a power, k, and raise the encoded character to that power and find the remainder when we divide by pq. That remainder is our encrypted data.

When we want to decrypt the data, we find a linear combination of k and the Euler-phi function of the number to give us 1, the greatest common divisor of the numbers. We take the coefficient of k and raise the encryted data to that power and find the remainder when we divide that power by pq. The result is the original data.

So we first consider the task of dealing with large powers of numbers.

Suppose we have a number a and we wish to raise that number to the kth power and find what the remainder would be if we divided that result by a number m.

For example, we want to raise 6 to the 10th power and find out what the remainder would be if we divided that result by 11.

For small numbers we could simply use the modulus operator. But for large numbers this may not work.

So let us examine a technique which will allow us to compute the remainder or modulus.

First let's look at the binary representation of 10 = 10102.

So 610 = 61*20 + 1*21 + 0*22 + 1*23 = 60*20 * 61*21 * 60*22 * 61*23.

So we can find the modulus of the whole product by finding the modulus of each term and multiplying them together.

An algorithm to accomplish this task is 
1. Get a, the number which will raise the power to, k, the power to which we raise the number, and m, the number which we will use to find the remainder of the power.

2. Initialize a variable x to 1.

3. Repeat the following steps as long as k is greater than 0.

4. Let e = k - (int)(k/2)*2, that is let e be 0 if k is even, 1 if k is odd.

5. If e is 1, then replace x by a*x % m.

6. Replace a by a2 % m.

7. Replace k by (k-e)/2.

8. The remainder is x.
A Java method to accomplish steps 2 - 8 is as follows. We will assume that somewhere else in our program we have input the numbers and will send them to this method. 
public int find_modulus(int a,int k,int m) {
   int x = 1;

   while (k>0) {
      e = k - (int)(k/2)*2;
      if (e==1)
         x = a*x % m;
      a = a*a % m;
      k = (k-e)/2;
   }

   return(x);
}


Notice that this is an instance method since I didn't include the keyword static.

Open up JBuider and create a new Class.

Remove each line and paste the following into the window. 
import java.io.*;
import RSA.*;
import USA.*;
    
public class Converter {
   int base; 
   int power;
   int mod;
 
   public Converter(int a,int m,int k) {
      base = a;
      power = k;
      mod = m;
   } 
 
   public int find_modulus() {
      int e = 0;
      int x = 1;
   
      while (power>0) {
         e = power - (int)(power/2)*2;
         if (e==1)
            x = base*x % mod;
         base = base*base % mod;
         power = (power-e)/2;
      } 
 
      return(x); 
   } 

   public static void main(String[] args) throws IOException {
      InputStreamReader stream = new InputStreamReader(System.in);
      BufferedReader keyboard = new BufferedReader(stream);

      System.out.println("Please enter your character");

      char c = keyboard.readLine().charAt(0);

      int asciicode = RSA.encode(c);

      int prime1 = RSA.find_prime(11);
      int prime2 = RSA.find_prime(13);

      int m = prime1*prime2;

      int phiOfm = (prime1-1)*(prime2-1);

      System.out.println("Please enter the power");

      int power = new Integer(keyboard.readLine()).intValue();

      Converter myConverter = new Converter(asciicode,m,power);

      int encryptednumber = myConverter.find_modulus();

      System.out.println(encryptednumber);

      System.out.println("Hello");

      int coefficient = RSA.find_coefficient(power,phiOfm);

      Converter myConverter2 = new Converter(encryptednumber,m,coefficient);

      int decryptednumber = myConverter2.find_modulus();

      char decryptedcharacter = RSA.decode(decryptednumber);

      System.out.println(decryptedcharacter);
   }
}