Links to hints about how to accomplish the operations are provided. But please read through the entire description before getting into the details of how to do things.
First, you must select two sets of keys, a public set and a private set. Do this as follows.
Select at random two large prime numbers p and q. (For high security, p and q should have about 100 decimal digits each. You will want to test your program with much smaller numbers than that, but it should be capable of using very large numbers.) Prime numbers p and q must be selected independently of one another, or you will lose all security. Do not, for example, choose q to be the next prime number after p. You do not want anybody to be able to guess p and q. [Hint on getting p and q]
Let n = pq, and let phi = (p-1)(q-1). [Hint on getting phi and e]
Select a small number e > 2 such that gcd(e,phi) = 1. (Gcd(x,y) is the greatest common divisor of x and y, also called the greatest common factor of x and y.) [Hint on getting phi and e]
Find an integer d where 0 < d < phi such that (ed) mod phi = 1. (It is guaranteed that such a number d exists.) [Hint on getting d]
The public key set is the pair (n,e), and the private key set is the pair (n,d). You can tell everybody your public key set if desired, but you keep the number d hidden. (Keep p and q hidden too, since from them and e anybody could compute d.)
A "message" to be enciphered is an integer k where 0 < k < n. The encipher function is
encipher(k) = (ke) mod nThat is, take k to the power e, and take the remainder when you divide that result by n. [Hint on enciphering and deciphering]
Notice that anybody who knows the public key (n,e) can encipher a number k.
The decipher function has the property decipher(encipher(k)) = k as long as 0 < k < n. That is, if you decipher an enciphered message, you get back the original message. It also has the property that encipher(decipher(k)) = k. That is, if you decipher a message and then encipher what you got from the decipher function, you get the original message back.
The decipher function is defined by
decipher(k) = (kd) mod nNotice that deciphering is the same kind of operation as enciphering. It just uses a different exponent. [Hint on enciphering and deciphering]
Only somebody who knows the private key set (n,d) can decipher messages. It is believed to be difficult to obtain d, knowing only n and e. The only known way to do that is to find the prime factors p and q of n, and there is no efficient method known to do that. [Notes on factoring and security]
For this example, we choose small prime numbers p = 7 and q = 13. (Obviously, this offers no security, but it illustrates how the system works.) Then n = 91 (since n is 7 times 13) and phi = 72 (since phi is 6 times 12). You can choose e = 5, since 5 > 2 and gcd(5, 72) = 1. Then d = 29, since 5*29 mod 72 = 1. The encipher and decipher functions are
encipher(k) = k5 mod 91decipher(k) = k29 mod 91
For example, encipher(18) = 185 mod 91 = 1889568 mod 91 = 44.
Then decipher(44) = 4429 mod 91 = 103398262268135618662965386326260402241163444053559142001800343869789787916826452309190192417264131218078348833560221412981442053155592422955707936598553748950499511586893512801517568 mod 91 = 18.
(This example should be enough to convince you that some care must be taken in how the encipher and decipher functions are computed. Even for these rediculously small values of p and q, quite large intermediate results show up. For realistic values of p and q, the intermediate results will be so large that they cannot be stored in the entire memory of the computer. Fortunately, those large intermediate results can be avoided. See the hint on enciphering and deciphering].)