Monday, November 6, 2017

RSA Algorithm Explained with C code

An RSA algorithm is an important and powerful algorithm in cryptography. It is widely used in Digital Signature and in an SSL.  The algorithm works in the following way
  1. Select at random two LARGE prime number $p$ and $q$.
  2. Multiply $p$ and $q$ i.e. $n = p*q$.
  3. Select a small odd integer $e$ which is relatively prime to $\phi(n)$, where $\phi(n) = (p-1) * (q - 1)$.
  4. Calculate the value of $d$ (explained below). $d$ is calculated as a modular multiplicative inverse of $e$ modulo $n$.
  5. Publish the pair $P = (e, n)$ as a public key. 
  6. Keep secret the pair $S = (d, n)$ as a private key. 
The message is encrypted using $P = (e, n)$ using following formula. 
\[P(M) = M^e \text{ mod } n\]
The message can be decrypted using $P = (d, n)$ using following formula.
\[S(C) = C^d \text{ mod } n\]
Secret key pair $(d, n)$ should be kept secret.

To calculate the value of $d$, we use the various number theories from mathematics.  In step 3 of the algorithm, we select $e$ which is relatively prime to $\phi(n)$. This means the GCD of $e$ and $\phi(n)$ is always 1. i.e.
\[ GCD(e, \phi(n)) = 1 \]
Let $x$ and $y$ be two parameters such that they satisfy following mathematical expression,
\[GCD(a, b) = d = ax + by\]
If we replace value of $a$ and $b$ with $e$ and $\phi(n)$ respectively, we get
\[GCD(e, \phi(n)) = 1 = ex + \phi(n)y\]
We already know the values of $e$ and $\phi$ and now we can use the Extended Euclid's Algorithm to get the value of $x$ and $y$. We can re-arrange the above expression as below
\[ ex + \phi(n)y = 1\]
Taking $( \text{ mod } \phi(n))$ on both side
\[ ex + \phi(n)y \equiv 1 (\text{ mod } \phi(n))\]
Since $\phi(n)y (\text{ mod }\phi(n))$ is 0, the final expression becomes
\[ ex \equiv 1 (\text{ mod }\phi(n)) \]
$x$ is now called a Modular Multiplicative Inverse of e.
We can finally solve for $d$ using a Modular Linear Equation Solver  which uses Extended Euclid's Algorithm

Let's take an example.  Suppose we want to solve the following expression.
\[13x \equiv 1 (\text{ mod } 220)\]
This equation is equivalent to 
\[ 13x + 220y = 1\]
To calculate value of $x$ and $y$, follow the following steps. 
  1. Let $a$ = 220  and $b$ = 13. Divide 220 by 13 which gives quotient 16 and remainder 12.  We can write this as $12 = 220 - 16 * 13$ or $12 = a - 16b$.
  2. Divide 13 (smaller number in step 1) by 12 (remainder in step 1) to get 1 as quotient and 1 as remainder. We can write this as $1 = 13 - 1 * 12$ Using the relation from step 1, we can rewrite this as $1 = b - 1 * (a - 16b) = 17b - a$
  3. Again, divide 12 (smaller number in step 2) by 1 (remainder in step 2) to get 12 as quotient and 0 as remainder. Since remainder is 0, we stop here and use step 2 as final equation. 
From step 2, we have equation $17b - a = 1$. If we compare it with our original equation $13x + 220y = 1$, we get $x = 17$ and $y = -1$. We don't care the value of $y$, we only care the value of $x$. 

The next step is finding the value of $d$, which is part of our secret key. From the definition, $d$ is the modular multiplicative inverse of $e$, modulo $\phi(n)$.  That means $d$ is $x$ modulo $\phi(n)$. In above example, $d$ = $x$ mod 220 = 17. To summarize this, after we came to an expression of the form $ex \equiv 1 (\text{ mod }\phi(n))$, we calculate $x$ and calculate $d$ using $x$ modulo $\phi(n)$. 

After we calculate the value of $d$, next step is to use public key pair ($e, n$) to encrypt the message using 
\[P(M) = M^e \text{ mod } n\]
Where $M$ is an important message (ex. a credit card number) to encrypt. Even for a large value of $e$, $M^e \text{ mod } n$ can be calculated using a Modular Exponentiation in very less amount of time.  Similarly using the private key pair ($d, n$), we can decrypt the message using 
\[S(C) = C^d \text{ mod } n\]
Where C is the encrypted message and S(C) is the original message M. 

The following C program gives a complete solution to all the mathematical concepts we just discussed. The Code is also available on GitHub.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

typedef struct {
 int d;
 int x;
 int y;
} EE;

EE extended_euclid(int a, int b) {
 EE ee1, ee2, ee3;
 if (b == 0) {
  ee1.d = a;
  ee1.x = 1;
  ee1.y = 0;
  return ee1;
 } else {
  ee2 = extended_euclid(b, a % b);
  ee3.d = ee2.d;
  ee3.x = ee2.y;
  ee3.y = ee2.x - floor(a / b) * ee2.y;
  return ee3;
 }
}

// Copied from 
// https://stackoverflow.com/questions/11720656/modulo-operation-with-negative-numbers
int modulo(int x, int N){
    return (x % N + N) % N;
}

void decimal_to_binary(int op1, int aOp[]){
    int result, i = 0;
    do{
        result = op1 % 2;
        op1 /= 2;
        aOp[i] = result;
        i++;
    }while(op1 > 0);
}

int modular_exponentiation(int a, int b, int n){
 int *bb;
 int count = 0, c = 0, d = 1, i;

 // find out the size of binary b
 count = (int) (log(b)/log(2)) + 1;

 bb = (int *) malloc(sizeof(int*) * count);
 decimal_to_binary(b, bb);

 for (i = count - 1; i >= 0; i--) {
  c = 2 * c;
  d = (d*d) % n;
  if (bb[i] == 1) {
   c = c + 1;
   d = (d*a) % n;
  }
 }
 return d;
}

int get_d(int e, int phi){
 EE ee;
 ee = extended_euclid(e, phi);
 return modulo(ee.x, phi); 
}

int main(int argc, char* argv[]) {
 int p, q, phi, n, e, d, m, c;
 printf("Enter the value of p: ");
 scanf("%d", &p);
 printf("Enter the valeu of q: ");
 scanf("%d", &q);
 n = p*q;
 phi = (p - 1) * (q - 1);
 printf("Enter the value of e: ");
 scanf("%d", &e);
 d = get_d(e, phi);
 printf("Public Key: (n = %d, e = %d)\n", n, e);
 printf("Private Key: (n = %d, d = %d)\n", n, d);
 printf("Enter message to encrypt: ");
 scanf("%d", &m);
 c = modular_exponentiation(m, e, n);
 printf("Encrypted message is: %d\n", c);
 m = modular_exponentiation(c, d, n);
 printf("Message is decrypted to %d\n", m);
 return 0;
}

1 comment: