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.
- 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.
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!