Code

/* rsa.cpp
 *	- Will Bergen - 2019
 *	- Toy implementation of RSA pubkey algorithm
 *	- Uses hardcoded, small primes for test purposes
 *	- compile with: g++ rsa.cpp -std=c++11 -g
 * 
 */

#include <stdlib.h>
#include <stdio.h>
#include <cstdint>
#include <string.h>

using namespace std;

/*	RSA Algo:
 *		Key Generation
 *			- Find 2 primes, p and q
 *				- p and q should be similar, 
 *			- Compute n = p*q
 *			- Compute C(n) where C is Carmichael Function
 *				- C(n) = lcm(p-1,q-1) where lcm is Least Common Multiple
 *				- I don't understand the theory here...
 *			- Choose e s.t. 1 < e < C(n) AND gcd(e,C(n)) == 1
 *				- ie. Choose e s.t. e and C(n) are coprime
 *			- Compute d = e^-1 mod C(n)
 *				- ie. Compute d, the multiplicative inverse of e mod C(n)
 *			- e is pub key
 *			- d is priv key
 *
 * 		Encryption
 * 			- Plain text represented as integer p (ignoring padding)
 * 			- Cipher text c = p^e (mod n) where e is the other's public key
 *
 * 		Decryption
 * 			- Cipher text represented as integer c
 * 			- Plain text p = c^d (mod n) where d is your private key
 *
 */

uint64_t C(uint64_t n); 								// Carmichael
uint64_t gcd(uint64_t i, uint64_t j);					// Greatest Common Divisor
uint64_t my_pow(uint64_t x, uint64_t y, uint64_t m);	// Power Mod
uint64_t modInverse(uint64_t x, uint64_t m);			// Multiplicative Inverse
void encrypt(char *input, int msg_length, uint64_t e, uint64_t n, uint64_t *output);
void decrypt(uint64_t *input, int msg_length, uint64_t d, uint64_t n, char *output);




int main(int argc, char **argv)
{
	printf("RSA Running!\n");
	
	// Hardcoded test:
	uint64_t p = 371;
	uint64_t q = 377;
	uint64_t n = p * q;
	printf("Using: [p: %lu, q: %lu, n: %lu]\n", p, q, n);
	printf("Finding C(n)... ");

	uint64_t c = C(p * q); // Carmichael's Function
	printf("%lu!\n",c); 
	
	 
	//	- Choose e s.t. 1 < e < C(n) AND gcd(e,C(n)) == 1
 	//	- ie. Choose e s.t. e and C(n) are coprime

	uint64_t e;
	int i;
	for (int i = 16; i < c; ++i)
	{
		if (gcd(i,c) == 1){
			e = i;
			break;
		}
	}

	printf("Chose %lu for e!\n", e);


	//	- Compute d = e^-1 mod C(n)
 	//	- ie. Compute d, the multiplicative inverse of e mod C(n)
 	
 	uint64_t d = modInverse(e,c);
 	printf("Chose %lu as d!\n", d);

 	// Encrypt a message:
 	char msg[] = "This is my much longer Message!";
 	int msg_length = strlen(msg);
 	printf("Message String: %s, (Length: %i)\n", msg, msg_length);

 	
 	//  - Cipher text c = p^e (mod n) where e is the other's public key
 	
 	// Declares pointers to arrays of size msg_length
 	uint64_t ciph_pad[msg_length];
 	char decrypted_pad[msg_length];

 	// Encrypt:
 	encrypt(msg, msg_length, e, n, ciph_pad);

 	// Print Encrypted Message:
 	printf("Cipher Text: ");
 	for (int i = 0; i < msg_length; ++i)
 	{
 		printf("%c", (int)ciph_pad[i]);
 	}
 	printf("\n");

 	// Decrypt:
 	decrypt(ciph_pad, msg_length, d, n, decrypted_pad);

 	// Print Decrypted Message:
 	printf("Decrypted Text: ");
 	for (int i = 0; i < msg_length; ++i)
 	{
 		printf("%c", decrypted_pad[i]);
 	}
 	printf("\n");

}

/* Encrypt:
 *	- Takes pointer to input char array, ie the message to encrypt
 *	- Takes pointer to output uint64_t array, ie. the cipher buffer
 */
void encrypt(char *input, int msg_length, uint64_t e, uint64_t n, uint64_t *output)
{
 	for (int i = 0; i < msg_length; ++i)
 	{
 		output[i] = (uint64_t)my_pow(input[i], e, n);
 	}
}

/* Decrypt:
 *	- Takes pointer to input uint64_t array, ie the cipher buffer
 *	- Takes pointer to output char array, ie. decrypted message buffer
 */
void decrypt(uint64_t *input, int msg_length, uint64_t d, uint64_t n, char *output)
{
 	for (int i = 0; i < msg_length; ++i)
 	{
 		output[i] = (char)my_pow(input[i], d, n);
 	}
}

// Try them all naive:
uint64_t modInverse(uint64_t x, uint64_t m)
{
	int i;
	for (int i = 1; i < m; ++i)
	{
		if ((x*i) % m == 1)
		// if ((x * i)  == (1 % m))
		{
			return i;
		}
	}
}

// From https://www.geeksforgeeks.org/carmichael-numbers/
// Computes (x ^ y) mod m:
// Vast majority of time spent here
uint64_t my_pow(uint64_t x, uint64_t y, uint64_t m)
{
	if (y == 0)
	{
		return 1;
	}
	uint64_t temp = my_pow(x,y/2,m) % m;
	temp = (temp * temp) % m;
	if (y % 2 == 1)
	{
		temp = (temp * x) % m;
	}
	return temp;

}


/* Greatest Common Divisor
 * 	- Takes two ints i and j
 * 	- If either is 0, return the other
 * 	- r = i mod k
 * 	- Call gcd(j, r)
 */
uint64_t gcd(uint64_t i, uint64_t j)
{
	if (i == 0)
	{
		return j;
	}
	if (j == 0)
	{
		return i;
	}
	
	uint64_t r = i % j;
	uint64_t t = gcd(j,r);
}


/* Carmichael Function
 *  - Takes n
 * 	- Generate sequence Xm (ie. X = [m1, m2, .., mn])
 * 		- For each i < n, add to X if gcd(i,n) == 1
 * 		- X = list of all numbers less than n which are coprime to n
 * 	- k = 1
 * 	- For each m in X, increment k if (m^k) mod n == 1
 * 	- Return k
 */
uint64_t C(uint64_t n)
{
	uint64_t x[100];
	memset(&x, 0, sizeof(uint64_t)*100);
	
	int i;
	int cp_n = 0;
	// starts at 1?
	for (i = 1;i < n; i++)
	{
		if (cp_n >= 99) {break;printf("pad exhausted!\n");exit(0);}
		if (gcd(i,n) == 1)
		{
			x[cp_n] = i;
			cp_n ++;
		}
		
	}
	int k = 1;
	bool flag;
	while (true)
	{ 

		flag = true;
		uint64_t k2 = k;
		for (i = 0;i < cp_n; i++)
		{
			// printf("%lu ^ %i mod %lu ==  %lu\n", x[i], k, n, my_pow(x[i], k, n));
			if (my_pow(x[i], k, n) != 1)
			{
				flag = false;
			}
		}
		if (!flag) {
			k++;
			flag = true;
		} else {
			break;
		}

	}

	return (uint64_t)k;
}