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

- Select at random two LARGE prime number $p$ and $q$.
- Multiply $p$ and $q$ i.e. $n = p*q$.
- Select a small odd integer $e$ which is relatively prime to $\phi(n)$, where $\phi(n) = (p-1) * (q - 1)$.
- Calculate the value of $d$ (explained below). $d$ is calculated as a modular multiplicative inverse of $e$ modulo $n$.
- Publish the pair $P = (e, n)$ as a public key.
- 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\]

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.

- 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$.
- 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$
- 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; }

Excellent Explanation, awesome work!!!

ReplyDelete