The ultimate in modern cryptography is public/private key cryptosystems. One of the first and most successful is the RSA algorithm. It is fairly simple yet very powerful, and it is at the heart of some of the best encryption software available. I learned the mathematics behind it in a first year math course and decided to implement it in C. This document describes the major systems required to implement the RSA algorithm and how I chose to do so.
The RSA algorithm is based on the properties of prime numbers, so finding them is critical. To be secure, the primes should be very large and randomly chosen. Commercial implementations take great care when generating random numbers to decrease the probability of an attack correctly guessing the keys. My implementation does not pretend to be secure so I used the C library's rand function and the standard unsigned long int data type. To test if my randomly generated integer is prime, I used wheel factorization, which is O( sqrt(n) ), where n is the size of the integer to test. It is slow but simple to understand and implement, and since my generated keys are small, this is not a problem. Serious implementations need to use much faster probabalistic algorithms due to the enormous size of the keys.
Once we have generated a pair of primes (p, q) and have found e such that gcd( e, (p - 1)(q - 1) ) = 1, we need to find the inverse of e modulo (p - 1)(q - 1). Essentially, we need to find a such that ae + b(p - 1)(q - 1) = 1. This is a diophantine equation, and can be solved using the euclidean algorithm.
The actual encryption and decryption is performed by evaluating Me mod n, where M is the data and (e, n) is the public or private key, depending on if you are encrypting or decrypting. Since evaluating Me results in an enormous number, we must take advantage of the properties of modular arithmetic to efficiently evaluate the exponentiation. The square and multiply algorithm is the simplest method to do this. More complex algorithms, expecially ones which can apply the Chinese Remainder Theorem during decryption, are faster.
My implementation is not actually useful. It was created only as an exercise in order to better understand the mathematics behind the RSA algorithm. If you are still curious, you can download the source code of my rsa-test program. It generates a pair of keys then encrypts and decrypts standard input to standard output. It was compiled and tested using GCC for Linux, but it should work with little modification with any ANSI C compiler.