CNS Practical-9

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

// Function to compute gcd
long gcd(long a, long b) {
    while (b != 0) {
        long t = b;
        b = a % b;
        a = t;
    }
    return a;
}

// Function to compute modular inverse of a with respect to m
long modInverse(long a, long m) {
    a = a % m;
    for (long x = 1; x < m; x++) {
        if ((a * x) % m == 1) {
            return x;
        }
    }
    return -1;
}

// Function to compute power (x^y) % p
long power(long x, long y, long p) {
    long res = 1;  // Initialize result
    x = x % p;  // Update x if it is more than or equal to p
    while (y > 0) {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;
        // y must be even now
        y = y >> 1;  // y = y/2
        x = (x * x) % p;  // Change x to x^2
    }
    return res;
}

// Function to generate keys (public and private)
void generateKeys(long *n, long *e, long *d) {
    long p = 61, q = 53;  // Two prime numbers
    *n = p * q;  // n is the product of p and q
    long phi = (p - 1) * (q - 1);  // Euler's Totient function

    // Choose e such that 1 < e < phi(n) and gcd(e, phi(n)) = 1
    *e = 17;
    while (gcd(*e, phi) != 1) {
        (*e)++;
    }

    // Compute d such that (d * e) % phi(n) = 1
    *d = modInverse(*e, phi);
}

// Function to encrypt the message using the public key
long encrypt(long msg, long e, long n) {
    return power(msg, e, n);
}

// Function to decrypt the message using the private key
long decrypt(long cipher, long d, long n) {
    return power(cipher, d, n);
}

int main() {
    long n, e, d;
    generateKeys(&n, &e, &d);

    printf("Public Key (e, n): (%ld, %ld)\n", e, n);
    printf("Private Key (d, n): (%ld, %ld)\n", d, n);

    long msg = 65;  // Example message (must be less than n)
    printf("Original Message: %ld\n", msg);

    long cipher = encrypt(msg, e, n);
    printf("Encrypted Message: %ld\n", cipher);

    long decrypted = decrypt(cipher, d, n);
    printf("Decrypted Message: %ld\n", decrypted);

    return 0;
}