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.

- Add: This was implemented using the simple addition bit by bit as in electronics.

carry_{i}= a_{i}& b_{i}; & is logical AND

sum_{i}=a_{i}^ b_{i}; ^ is Exclusive Or - 2’s complement:
- 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 1
_{10}from 7_{10}using 2’s complement.

- First, we need to convert 0001
_{2}to its negative equivalent in 2’s complement.

**0111 (7) - 0001 - (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**- Next, we add the negative value we computed to 0111
_{2}. This gives us a result of 10110_{2}.

**0111 (7) + 1111 +(-1) 10110 (?)**- 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 0110
_{2}(or 6_{10}).

**0111 (7) - 0001 - (1) 0110 (6)** - First, we need to convert 0001
- Multiply: We are using normal shift left multiplication and addition. Eg:
- 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.
- 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:

functionrsa: // 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 };functionmodular_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 +veif(x1 < 0): x1 += m0;returnx1;

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

## Be First to Comment