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
- 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;
}
About Author
Excellent Explanation, awesome work!!!
Thanks a lot!