An easy way for a programmer to understand public/private key encryption

Most every programmer uses public/private key encryption and is probably aware of the basics of very big numbers and those number being hard to factorialise.

I was interested in learning more about the process, but the guides I have come across tended to be complicated and sometimes actually plain wrong in explaining the maths.

So I decided it would be useful for me and perhaps others to see things in "simple" program form and use some nice little numbers that could be understood.

It did not go quite to plan, but is still pretty simple and I hope understandable. The problem is that the arithmetic of asymmetric encryption is based on raising numbers to large powers even if it is a small range of characters to be encrypted.

I chose just lower case letters and even that involves 25^23 which is approximately very big! It's not rocket science to get around that, but it does involve installing the gnu gmp library and hence my idea of a bit of code you could just compile and run assuming you have a c compiler was thwarted. 

But anyhow here we go, short and sweet.

// Demonstrate public/private key encrpytion

// gcc crypt.c -lm -l:libgmp.a

// requires libgimp

// https://gmplib.org/manual/Concept-Index

//

#include "stdio.h"

#include "math.h"

#include <stdlib.h>

#include <string.h>

#include "gmp.h"

//

// For public/private key encryption we need three normally very large random prime numbers

// These only need to be found once to generate the key, so it would not matter too much

// if the process was pretty time consuming. But since the way to crack a key is by

// factorisation of a multiple of those primes with the anticipation that a lot of CPUs

// are on the case it wouldn't be great if your one little computer was facing

// the challenge of checking with brute force factorisation.

// It so happens that the old fashioned method

// of checking for primes by looking for factors were superceded by superior methods

// in the 1970s. This seems pretty useful for covering the subject.

// https://en.wikipedia.org/wiki/Primality_test

// So our little CPU can create big keys without too much effort.

//

// For our purposes of showing an example we are just going to hard code our primes

#define PRIME1 11

#define PRIME2 5

#define PUBLIC_ENCRYPT_EXPONENT 7

// some bigger primes but we need to stay with m below 256 as we are storing in a char

//#define PRIME1 19

//#define PRIME2 13

//#define PUBLIC_ENCRYPT_EXPONENT 11

// Find highest common denominator

int get_common_denominator(int a, int b)

{

// Base Case

if (a == 0)

{

return b;

}

return get_common_denominator(b % a, a);

}

int main(int argc, char *argv[])

{

int fn = (PRIME1 - 1) * (PRIME2 - 1);

printf("f(n) = %d\n", fn);

int m = PRIME1 * PRIME2;

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

int c, x, y, gcd, isprime,private_decrypt_exponent;

c = 1;

//

// we are looking for a private key exponent where

// there are no common denoninators with f(n)

//

//

// This is where asymmetry makes its mark.

// Knowing the private f(n) number it is a quick function to get a private key exponent

// that complements the public key exponent.

// To reverse this from the modulus require you factorize the modulus and that is slow

// https://cs.stackexchange.com/questions/14456/factorial-algorithm-more-efficient-than-naive-multiplication

//

// What to were finding is known as a modular inverse

do

{

c += fn;

x = c % PUBLIC_ENCRYPT_EXPONENT;

if (x == 0)

{

printf("%d %d %d\n", c, fn, x);

gcd = get_common_denominator(c, fn);

private_decrypt_exponent = c / PUBLIC_ENCRYPT_EXPONENT;

if (gcd == 1 && private_decrypt_exponent != PUBLIC_ENCRYPT_EXPONENT)

{

break;

}

}

} while (1);

printf("private exponent %d m=%d\n", private_decrypt_exponent, m);

//

// Since this is modulus arithmetic. It stands to reason we cannot encode more different

// characters than the modulus.

// the whole principle of this thing is that each different character encrypts as a

// unique number within the range of the modulus So we can play with relatively small

// numbers we will choose lower case letters as a usable subset of ascii.

// No spaces sinces space is 32 and a is 65.

//

// Encryption is this using the public modulus and public key

// c = letter^ public_exponent mod m

// Decryption is the same but with the private key

// message = c^private_exponent mod m

//

//

// As a form of encryption this would be useless by itself as a bit of english encrpyted

// like this would retain the same symbol frequency as the original text.

// Since English has a skewed frequency of letter usage, any reasonably long bit of text

// could be easily cracked.

// As such what is actually encrypted in practice is a randomly generated key for an

// agreed far more secure cypher.

// Also in practice the messasge is also compressed to a zip like format to add a further

// obstacle to brute force attacks. If after every attempt, you have to unzip and see if

// anything sensible emerges it multiplies the CPU involved.

//

// A decent reference to the math is here

// https://www.nku.edu/~christensen/the%20mathematics%20of%20the%20RSA%20cryptosystem.pdf

//

char *in = "thequickbrownfoxjumpsoverthelazydog";

int l = strlen(in);

unsigned char *out = (unsigned char *)calloc(l + 1, 1);

int i;

//

// Even small numbers end up massive when raised to powers

// So we have to use a library than can manage to any arbitary size

//

mpz_t integ, result, modulus;

mpz_init(integ);

mpz_init(result);

mpz_init(modulus);

mpz_set_ui(modulus, (unsigned long int)m);

printf("Encrypt\n");

for (i = 0; i < l; i++)

{

mpz_set_ui(integ, (unsigned long int)in[i] - 'a');

mpz_powm_ui(result, integ, (unsigned long int)PUBLIC_ENCRYPT_EXPONENT, modulus);

unsigned long c = mpz_get_ui(result);

printf("(%c %ld)", in[i], c);

out[i] = (char)c;

}

printf("\nDecrypt");

for (i = 0; i < l; i++)

{

mpz_set_ui(integ, (unsigned long int)out[i]);

mpz_powm_ui(result, integ, (unsigned long int)private_decrypt_exponent, modulus);

unsigned long c = mpz_get_ui(result);

printf("(%d %c %c)", out[i], in[i], ((char)c) + 'a');

}

printf("\n");

}