Encryption and Decryption - Note of Fundamental Number Theory III

In previous notes we’ve seen how messages are encrypted/decrypted from the top and middle level. Eventually we come to the very detail about how the helper functions in setRSAKeys(), and processMessage() are implemented.

getPrime() in getRSAKeys() returns a prime. It randomly picks an integer and calls isPrime() to test if it is a prime. isPrime() makes use of ModularExponentiation() to perform the pseudo prime test.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65


        int ModularExponentiation(int a, int b, int n)
        {
            int c = 0;
            int d = 1;
            int mask = 0x8000;

            /*locate the most significant bit of b*/
            while (0 == mask & b) mask = mask >> 1;

            while (0 != mask)
            {
                c = c * 2;
                d = (d * d) % n;
                if (0 != (mask & b))
                {
                    c = c + 1;
                    d = (d * a) % n;
                }
                mask = mask >>  1;
            }

            return d;
        }

        bool isPrime(int n)
        {
            /*this function requires function ModularExponentiation(),
             *which assumes the input n is an odd integer greater than 2
             */

            if (0 == n % 2)
            {
                return false;
            }

            if ( 1 == ModularExponentiation(2, n-1, n))
            {
                //This is, possibly, a prime, or to be accurate, a pseudoprime
                if ( 561 == n)
                   return false; // the only Carmichael number in [1, 1000]
                else
                   return true;
            }
            else
            {
                //This is definitely a composite
                return false;
            }
        }

        void getPrime(int* prime)
        {
            int suspect = 0;

            do
            {
                //pick a random number
                suspect = rand() % 1000;
                //test if it is a prime
                //if yes, return
                //go to the top
            } while (! isPrime(suspect));

            *prime = suspect;
        }

The modular exponentiation is to compute $$a^b$$ mod $$n$$, where $$a$$ and $$b$$ are nonnegative integers and $$n$$ is a positive integer. Here it is used to test if an input number is a prime. The test is also called primality-testing. In this note the so-called repeated squaring method, described as below, is utilized to compute the modular exponentiation:

Let $$(b_k, b_{k-1}, …, b_0)$$ representing the binary form of $$b$$. $$b_0$$ is the least significant bit. ModularExponentiation(int a, int b, int n) computes $$a^c$$ mod $$n$$ as $$c$$ is increased by doublings, from 0 to $$b$$.

The function returns false when the input n is a composite, and true, if n is a pseudo-prime, which is very likely to be a prime, with a few exceptions.

The exceptions are called Carmichael numbers. They are composites and are also pseudo-primes, but they are very rare. So rare they are that for integers less than 100,000,000 there are only 255 Carmichael numbers.

In this note we make lives simple and limit the participants less than 1000, in which there is only one Carmichael number, 561.

There are of course other ways to perform perfect prime test. Miller-Rabin randomized primality test, for example, overcomes the “fake prime” problem that we have in the method above. Again to keep this note short we simply use the Modular Exponentiation method.

With a method for primality test, in the code above a random number is picked and tested.
But how many numbers should we pick until a prime is found? Is there a way to estimate the density of primes given the integer range?
Yes, by the Prime number theorem: $$lim_{x \to \infty} \frac{ \pi(n)}{n \ln n} = 1$$

the number of primes equal or less than $$n$$ is approximately $$\frac{n}{\ln n}$$

So before we can find a 1024-bit long prime, we will need to test about $$\ln 2^{1024} \approx 709$$ numbers, and if we skip checking the evens, there are only 354 candidates to test.

Back to our little simple case, we will get a prime, oh, a pseudo-prime, after trying about $$\frac{\ln 2^{9}}{2} \approx 3$$ times, not bad ha?

After getting the required primes, two functions, gcd() and Extended_Euclid(), are used in setRSAKeys() to get $$e$$ and $$d$$.

The functions gcd() produces greatest common divisor of two integers. $$e$$, relatively prime to $$\phi(n)$$, is generated by this function:

1
2
3
4
5
6
7


   int gcd(int a, int b)
   {
      if (b == 0)
         return a;
      else
         return gcd(b, a % b);
   }

I was thinking a simple while loop would be more efficient than the recursion version, but comparisons in C doesn’t show any benefit…

After playing with some numbers and I realized that: 1. when a = b, the recursion terminates. 2. if a>b or b>a, the number of recursions is still reasonably small.

(and as it proves later in the book:(Lamé’s theorem)

for any integer $$k \geq 1$$, if $$a > b \geq 1$$ and $$b > F_{k+1}$$,

then the call Euclid(a, b) makes fewer than k recursive calls.),

where $$F_{k}$$ is the Fibonacci numbers.

Exended_Euclid() are based on the Euclid’s algorithm and it’s extended version:

Given the input of $$a$$ and $$b$$, returns $$d$$, $$x$$ and $$y$$, where integers $$a$$, $$b$$, $$d$$, $$x$$, and $$y$$ satisfy:d = gcd(a, b) = ax+by

This function is used here to calculate modular multiplicative inverses, $$d$$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


    typedef struct euclid_coefficients
    {
       int d;
       int x;
       int y;
    } euclid_coefficients;
    euclid_coefficients ec;

    euclid_coefficients Extended_Euclid(int a, int b)
    {
       if (b == 0)
       {
          ec.d = a;
          ec.x   = 1;
          ec.y   = 0;
          return ec;
       }
       euclid_coefficients tmp;
       tmp = Extended_Euclid(b, a % b);
       int old_x = tmp.x;
       tmp.x = tmp.y;
       tmp.y = old_x - a/b*tmp.y;
       return tmp;
    }

The last step is to use the key to encrypt/decrypt the message:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


        long powerMod(long x, int n, int y)
        {
          if (1 > n)
          {
              return 1;
          }
          if (x > y)
          {
              x = x % y;
          }

          long tmp = 1;
          while ( n > 2 )
          {
              n -= 2;
              tmp = ((x * x) % y) * tmp;
              tmp %= y;
          };
          if (2 == n)
          {
              tmp = (x % y) * tmp;
          }
          tmp = (x % y) * tmp;
          tmp %= y;

          return tmp;
        }

        void processMessage(long* msg, key key, int len)
        {
            int i;

            for (i = 0; i < len; i++)
            {
                msg[i] = powerMod(msg[i], key._key, key.n);
            }
        }

After all, we’ve built a simple encryption/decryption tool.
Time to have some fun…

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


    ~/EncryptionAndDecryption/> test
    p = 61, q = 881
    n = 53741, phi(n) = 52800
    e = 7
    d = 7543
    the encrypted message:
    [~] [▒] [▒] [▒] []
    the decrypted message:
    [h] [e] [l] [l] [o]

    ~/EncryptionAndDecryption/>