Public-private key encryption algorithm
(How PGP, GPG, or GnuPG works)

Follow these simple steps to get the encryption and decryption keys:

  1. Find two large primes: P and Q.
    FYI: PGP uses 1024 bits or larger, which converted to decimal are numbers with 308 (or more) digits!

  2. Find a value E such that it is less than P times Q (ie PQ), and that it shares no factors with (P-1)(Q-1).
    Hint: E must be odd (as (P-1)(Q-1) will be even) but does not necessarily have to be a prime number.

  3. Now find a value D, so that DE-1 is divisible by (P-1)(Q-1).
    In modulo arithmetic, D is the multiplicative inverse of E, so can be written:
    DE mod ((P-1)(Q-1)) = 1

The public key is made of the two numbers PQ and D.
The private key is made of the two numbers PQ and E.
  1. To encrypt X into Y:
    Y=(X^E) mod (PQ)

  2. To decrypt Y back to X:
    X=(Y^D) mod (PQ)
Note: X and Y will have values 0..PQ-1

Hint: forget P and Q as they make it all too easy to work out the private key. It is very difficult to factor PQ to get the two primes, so much so, that it is often reported that such a computation would take billions of years using todays fastest machines. Of course, that is until someone finds out an algorithm to do it, in a reasonable amount of time. And there are a few methods that are getting close, such as MPQS (multiple polynomial quadratic sieve), ECM (elliptic curve method), and NFS (number field sieve). Close enough that 25% of the brute force time can be reportedly circumvented.

An example using smaller numbers:

P          =  17
Q          =  19
PQ         = 323
(P-1)(Q-1) = 288

Then choosing:
E          =  43
we get:
D          =  67
as 43*67 = 2881
and 2881 mod 288 = 1.

To encrypt the "message" 99, it is calculated as:
99^43 mod 323 =
64910262836840243299385600408064315507269747285819167695867408486826194559651331974299 mod 323 =
44

To decrypt this "44", the calculation is:
44^67 mod 323 =
129219877375000481226629921485716742694854635591566961372271643321956224151273763684202739354062946891269668864 mod 323 =
99
Although when encrypting and decrypting you do not need to calculate the huge number before doing the modulo, it can be done at the same time. For example, to calculate 99^43 mod 323, some code to do this could be: 
N=1;
repeat 43 times: N=(N*99) mod 323
Of course, having such small numbers so that the message can only be 0..322 per encryption packet is not very secure! Having two primes 1024 bits in size (over 300 digits) means the range of 0..PQ-1 becomes massive!

This encryption method also allows a message encrypted using the private key to be decrypted with the public key. Which means it can be used to allow secure communication between one place and another, by each place having its own key pairs, and each message is encrypted using its own private key, THEN encrypted with the others public key. At the receiving end, the message is decrypted with the private key, THEN decrypted with the public key of the sender.
It ensures the receiver knows the sender MUST have been the sender, and knows nobody else could decrypt the message without the private key of the receiver.
Although in practise you only need to show the checksum of use of your private key on the message (encrypted or not) to prove it was really you who sent the message. This is referred to as a "PGP signed" message.

Now all you have to do is trust the sender and/or the receiver to not give away their private key, and to trust the public key you are given IS definately the key to whom you think it belongs!
One way to ensure this is to use a simple one-way hashing algorithm (eg MD5), so that the massive key is reduced to (say) 32 or 128 bits. Then when the key is received, use another method of communication to the key owner (eg the phone, or meet in secret cafe) to confirm the hash value matches. As the hash is one-way, there is no way to reverse the hashed value to get the key, and you can trust the key was sent correctly, and nobody altered it in transit.

There are plenty of books on all of this and more, such as digital signatures, shared secrets, computer security, firewalls, etc. Visit your library, bookstore, or an online retailer.

Dongrays → Bryan → bookmarks → How crypt works