How PGP works and the maths behind RSA

How PGP works

Basic description of PGP

PGP is a hybrid cryptosystem that combines a public key (asymmetric) algorithm, with a conventional private key (symmetric) algorithm to give encryption combining the speed of conventional crytography with the considerable advantages of public key cryptography. As far as the user is concerned PGP behaves as a public key cryptosystem. In a public key system a key pair is mathematically generated, consisting of a public key and a private key. You can encrypt a message with one key and decrypt it with the other (either key can be used for encryption). The message cannot be decrypted using the same key that was used to encrypt it. Generally you publish your public key, making it available to anyone who wants to send you encrypted message. They encrypt their message with the public key - they cannot then decrypt the encypted message and nor can anybody else. The only person who can decrypt the message is you, i.e. the person who has the private key that goes with the public key. It is clear that the private key must be kept secret by its owner.

The great advantage of this kind of cryptography is that, unlike conventional cryptosystems, it is not necessary to find a secure means of transmitting the encryption key to the intended recipient of your message. Another useful feature of such cryptosystems is the ability to "sign" messages by encrypting them with your private key. Anyone can then decrypt the message with your public key, and they can be sure that only the owner of that public key could have encrypted the message (with the corresponding private key).

PGP uses the RSA public key algorithm for encryption in tandem with the conventional IDEA algorithm. A single IDEA key is generated for encrypting the message with IDEA, this is a conventional cryptosystem so the same key will decrypt the massage. RSA is them used to encrypt the IDEA key using the recipients public key. The recipient uses their copy of PGP which decrypts the RSA encrypted IDEA key with their private key. The IDEA key is then used to decrypt the rest of the message. 


Text encrypted      Key K encrypted  \
with IDEA using     using RSA with    |
key K               Alices Public     |
            |       key, E.           |
            |                         |
            |         |                \  Bob using his copy of PGP
            |         |                /  and Alice's public key E.
            V         V               |
          Message consists            |
          of RSA encrypted            |
          key K, and IDEA             |
          encrypted text.            /
                                      
                ||                    
                ||                    
                \/                    
            
         Message transmitted
         via email to Alice
         
                ||
                ||
                \/
                                     \
        IDEA key K decrypted          |
        using Alices private          |
        key, D and RSA.               |
                ||                     \  Alice using her copy of PGP
                ||                     /  and her own private key D.
                \/                    |
                                      |
        Text decrypted using          |
        IDEA and IDEA key K.         /

The maths behind RSA

RSA uses modular exponentiation (^ is used to denote exponentiation) to encrypt and decrypt messages based on text converted to numerical form (on a computer the text *is* in numerical form as far as the computer is concerned so this is trivial).

If you don't know much about modular arithmetic or have trouble following the maths below, read this document describing ideas in modular arithmetic used in RSA. The maths is not difficult but if it is unfamiliar this introduction should be helpful.

The RSA algorithm and key generation

The RSA encryption function is C = T^E mod N, where T is the plaintext, C is the ciphertext and E is the public key. In other words T is raised to the power of E in modulus N. To give a simple example, raising 2 to the power of 3 gives us 8, to raise 2 to the power of 3 in modulus 7 is 8 mod 7 which is 1. To decrypt The decryption function is T = C^D mod N where D is the private key. The keys E and D have to be generated such that E is the inverse of D with respect to exponentiation in mod N. i.e. (T^E mod N)^D mod N = T^ED mod N = T.

Finding a suitable key pair for which this is true requires us to know the Euler's totient function, J(N) for the modulus N. The Eulers totient function is the number of numbers in the set 1 to N-1 that are relatively prime to N. To find J(N) we need to know the prime factors of N.

Fundamental theorem of arithmetic: Every non-prime number can be represented as a product of a unique set of prime numbers.

Relative primes: Two numbers are realtively prime if they have no prime factors in common

We need to find this set of unique prime factors for Nin order to calculate the Euler's quotient J(N). Finding these primes is extremely difficult - impractically difficult for sufficiently large N which is in fact what makes PGP so secure. Given N and E you can't work out D (and thus decrypt a message) without finding the prime factors of N which is so difficult that PGP is virtually unbreakable for sufficiently large values of N.

The practical way to generate a key pair in the first place is to generate N by multiplying two large primes P and Q, so that you know the prime factors of NN to start with. For a number with just two primes factors (as this is) the Euler's totient function simplifies to:

J(N) = (P-1)(Q-1)

Now we choose a number E that is relatively prime to J(N). We need to find D which is the inverse of E with respect to exponentiation mod N. We can do this using J(N).

It is a rule of modular arithmetic that when manipulating exponents of numbers mod N that the exponentials are manipulated in mod J(N). For example consider the following,

(T^E mod N)^D mod N = T^ED mod N

It turns out that when multiplying the exponents E and D, we do it mod J(N) and not mod N. In order to find a suitable inverse D for our chosen encrypting exponent E we must find a D that satisfies the following:

T^ED mod N = T

This implies that ED mod J(N) = 1 since clearly T^1 mod N = T. Thus the problem of finding D is simply that of finding the multiplicative inverse of E in mod J(N) which is computationally straightforward. It should be noted here that it is a law of modular arithmetic that for a given modulus M, a number will only have a multiplicative inverse mod M if it is relatively prime to M. This is the reason that E must be initially chosen to be relatively prime to J(N) since it has to have a multiplicative inverse, D, in mod J(N). Values of E and D which are trivial (i.e. E = D) are rejected as insecure and another E value is tried.

Having chosen out value of N, and generated our E and D, we can disgard P, Q and J(N) as they have done their job. We now have suitable values of E and D for encryption and decryption with,

C = T^E mod N and T = C^D mod N

(in fact it doesn't matter which way round you use D and E). Without knowing P and Q it is a computationally impractical for anyone else to find J(N) and hence deduce D from E for large values of N, thus the encryption is secure.

Summary of the steps for key generation

Security of RSA

Factoring N would clearly enable RSA to be broken. It has not been proven that there is no polynomial time solution to finding prime factors of large numbers (i.e. it is possible that an algorithm that could factor N quickly enough to break RSA may be discovered in the future). However, despite constant improvements in factoring algorithms none have been found that satisfy the polynomial-time criteria which would make cracking RSA a tractable problem.

It is important to note that it has not been proven that security of RSA relies solely on the mathematical diffculty of finding the prime factors of large numbers. However, many of the other possibilities for finding D given E have been shown to be of equivalent difficulty to factoring N. One possibility is that an algorithm could be devised to find the Eth root mod N more easily than factoring N. Nevertheless, no such algorithm has been discovered so far, and RSA has withstood many attempts to crack it.

Sherry Mayo / ANU / scmayo@rschp2.anu.edu.au