RSA Algorithm Implementation in C

Aim

To write a C program to implement RSA (Rivest–Shamir–Adleman) asymmetric cryptographic algorithm.

Algorithm

1. Select two large prime numbers p and q.
2. Compute n = p * q.
3. Choose system modulus phi(n) = (p - 1) * (q - 1).
4. Decrypt by computing d = e^-1 mod phi(n).
5. Encryption: c = m^e mod n.
6. Decryption: m = c^d mod n.

Program Code

#include <stdio.h>

int gcd(int a, int b)

{

    int temp;

    while (b != 0)

    {

        temp = a;

        a = b;

        b = temp % b;

    }

    return a;

}

int power(int a, int n, int m)

{

    int res = 1;

    while (n != 0)

    {

        if (n % 2 == 1)

            res = (res * a) % m;

        a = (a * a) % m;

        n /= 2;

    }

    return res;

}

int main()

{

    int p, q, n, phi, e, d, msg, enc, dec;

    printf("Enter two non-equal prime numbers: ");

    scanf("%d %d", &p, &q);

    n = p * q;

    e = 2;

    phi = (p - 1) * (q - 1);

    while (e < phi)

    {

        if (gcd(e, phi) == 1)

            break;

        else

            e++;

    }

    int k = 2;

    d = (1 + k*phi) / e;

    printf("Enter numeric message data: ");

    scanf("%d", &msg);

    enc = power(msg, e, n);

    dec = power(enc, d, n);

    printf("\np = %d, q = %d", p, q);

    printf("\nn = %d", n);

    printf("\nPhi(n) = %d", phi);

    printf("\nPublic key, PU = {%d, %d}", e, n);

    printf("\nPrivate key, PR = {%d, %d}", d, n);

    printf("\nMessage data = %d", msg);

    printf("\nEncrypted data = %d", enc);

    printf("\nDecrypted data = %d", dec);

    return 0;

}

Output