RSA : Rivest, Shamir Adleman Algorithm C++

The RSA is a standard algorithm in public key cryptography. I will not bore you with the theoretical details of algorithm that can be found here.What we are gonna talk about today is a visual studio 2010 vc++ project discussing the algorithms used. The code defines the key size which defaults to 512 right now. As we know standard processors don’t have word sizes as big as that so first problem that we face is how to represent this number.

To represent this number we use a byte array of 512/8 = 64. Then we implement all the math functions for it.

    1.  Add: This was implemented using the simple addition bit by bit as in electronics.
      carryi= ai & bi; & is logical AND
      sumi=ai ^ bi; ^ is Exclusive Or
    2. 2’s complement:
    3. Subtract: This is implemented by calculating the twos complement and subsequently calling add. Lets follow the logic with a smaller bit count example. Let’s consider how we would solve our problem of subtracting 110 from 710 using 2’s complement.
      1. First, we need to convert 00012 to its negative equivalent in 2’s complement.
          0111    (7)
        - 0001  - (1)
      1. To do this we change all the 1’s to 0’s and 0’s to 1’s and add one to the number. Notice that the most-significant digit is now 1 since the number is negative.
        0001 -> 1110
                   1
                1111
      1. Next, we add the negative value we computed to 01112. This gives us a result of 101102.
          0111    (7)
        + 1111  +(-1)
         10110    (?)
      1. Notice that our addition caused an overflow bit. Whenever we have an overflow bit in 2’s complement, we discard the extra bit. This gives us a final answer of 01102 (or 610).
          0111    (7)
        - 0001  - (1)
          0110    (6)
    4. Multiply: We are using normal shift left multiplication and addition. Eg:BinaryMultiplicationExample
    5. Div: This is implemented is using binary search. We start with the divisor and multiply it with the mid where mid = (divisor+dividend)/2. We then call multiply (mid, mid). Then we collapse onto the size that is closer to the dividend.
    6. Greatest Common Divisor: We are using Euclidean algorithm for calculating gcd.
      function gcd(a, b)
          while b ≠ 0
             t := b; 
             b := a mod b; 
             a := t; 
          return a;

RSA Implementation

Now that we have the math functions defined above, we are using the following algorithm:

    function rsa:
        // generate values
        p = random_prime(), // 512 bit
        q = random_prime(), // 512 bit
        n = p * q,
        t = (p - 1) * (q - 1), // totient as φ(n) = (p − 1)(q − 1)
        e = random_prime(1, t),
        d = modular_multiplicative_inverse(e, t);
    return {
    	n: n, // public key (part I)
        e: e, // public key (part II)
        d: d  // private key
    };

   function modular_multiplicative_inverse(a, m)
       g = gcd(a, m);
       assert (g != 1) // inverse does not exist as a and m are not coprime
       x0 = 0, x1 = 1, m0 = m;
       while (a > 1):
           q = a / m; // quotient
           t = m;    
           m = a % m;
           a = t;
           t = x0;
           x0 = x1 - q *x0;
           x1 = t;
       // make x1 +ve
       if (x1 < 0):
           x1 += m0;
       return x1;

The visual studio solution along with the entire code can be found here.

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *