PGP is a high security cryptographic application. PGP allows you to exchange information (whether it's files or messages) with privacy, authentication and convenience. It means that only the intended receiver will be able to access the information and that The sender identity is known. PGP is very easy to use, as there is no need for a dedicated secure channel.
Quick Overview
PGP uses two algorithms. One is the Rivest-Shamir-Adleman (RSA) public key cryptosystem and the second is the IDEA algorithm. An IDEA key is generated for the message. The IDEA system is a conventional cryptosystem, so that the same key will be used to decrypt the message. Then RSA is used to encrypt the IDEA key, using the recipient public key. The recipient (When he receives the message) uses his private RSA key to decrypt the IDEA key, which is then used to decrypt the entire message.
RSA public key cryptosystem
RSA uses modular exponentiation to encrypt and decrypt messages.
The RSA function is C=T^E mod N
T is the original text, E is the Public key, and C is the resulting encrypted text.
The Decryption function is T = C^D mod N.
D is the Private key.
The two keys (E and D) have to be generated such that (T^E mod N) ^ D mod N = T^(ED) mod N = T
How to find a pair of keys
First we'll introduce the Euler's totient function.
The function is J(N) for the modulus N. The function is the number of numbers in the set {1..N-1} that are relatively prime to N.
Two numbers are relatively prime if they have no prime factors in common.
Finding the set of unique prime factors for N (which is needed to computer J(N)) is very difficult (computational speaking). That what makes PGP so secure. Given N and E it's hard to find the D, needed to decrypt the message.
So, How DO we find a pair of keys?
The practical way of doing so, is to generate N by multiplying two primes (Let's say P1 and P2). That way we'll know the prime factors when we begin! The Euler's totient function for a number with just two prime factors simplifies to
J(N) = (P1-1)(P2-1)
Now we choose a number (E) that is a relatively prime to J(N). The last thing to do is find a D which is the inverse of E with respect to exponentiation mod N. (We need this, because E and D need to satisfy the formula we stated before).
It turns out, that we must find a D that satisfies this formula:
T^(ED) mod N = T
that means that ED mod J(N) = 1. (That's because T^1 mod N = T; The problem of finding D is the problem of finding the multiplicative inverse of E in mod J(N). NOTE : for a given modulus M, a number will only have a multiplicative inverse mod M if it is relatively prime to M. That's why we chose E to be relatively prime to J(N) )
We must note, that this formula might get us a trivial answer : E = D which is insecure. If we get this answer, we must try another Value of E.
This encryption is secure, because without knowing P1 and P2, finding D from E is impractical...
Again, How do I find the keys?
- Choose two large Primes, P1 and P2. N= P1 * P2
- J(N) = (P1-1) * ( P2-1)
- E is chosen such that E is a relatively prime to J(N)
- D is calculated (the multiplicative inverse of E mod J(N). Trivial values are rejected.
- C = T^E mod N : The text is encrypted and safe!
- D (which is kept secret) is used to decrypt : T = C^D mod N
Is RSA really Safe?
Actually, it has not been proven that there is no polynomial time solution to finding prime factors of N. (It is what is called a NP - Complete problem). Also, it has not been proven that D cannot be found by other means, (i.e. other than finding the prime factors of N). Actually, there ARE several other ways of finding D! But all the ways found so far have been shown to be of equivalent difficulty to factoring of N.
So while it has not been Proven, RSA is very secure, and until now it has not been broken. (Unless by brute force, which would take a very long time, with a very strong computer). After all, nothing can be completely safe!
The IDEA algorithm
IDEA is a clock cipher, which uses a 128-bit length key to encrypt 64-bit blocks of data. The scheme uses 52 16-bit subkeys. They are generated from the 128-bit key (The 'main' key), like that :
- The main key is split into eight keys (each 16-bit long) these are the first subkeys
- The main key is shifted left 25 times. This makes a new key, which is split into 8 more subkeys
The second step is repeated, until we have 52 subkeys.
The 64-bit block of data (original data) is split into 4 16-bit segments. We'll call them s1,s2,s3 and s4. The subkeys are k1, k2 .. k52.
The encryption is made in 8 rounds. Each round is made of the following steps :
- s1 * k1 -> d1
- s2 + k2 -> d2
- s3 + k3 -> d3
- s4 * k4 -> d4
- d1 XOR d3 -> d5
- d2 XOR d4 -> d6
- d5 * k5 -> d7
- d6 + d7 -> d8
- d8 * k6 -> d9
- d7 + d9 -> d10
- d1 XOR d9 -> d11
- d3 XOR d9 -> d12
- d2 XOR d10 -> d13
- d4 XOR d10 -> d14
Note : This process involves modular multiplication, with a modulus of (2^16) + 1 and addition with a modulus of 2^16. A key of all zeros is defined as being equal to 2^ 16, for multiplication steps.
After these steps, the blocks d11, d13, d12, d14 (in that order!) are used as input to the next round, with the next 6 keys. After the 8 rounds are over, we get 4 blocks : b1,b2,b3,b4.
Then we perform :
- b1 * k49 -> c1
- b2 + k50 -> c2
- b3 + k51 -> c3
- b4 * k52 -> c4
The final blocks (c1 - c4) form the encrypted 64-bit block.
To decrypt the data, we use the same steps, but with different set of subkeys. it goes like that.
1st round k49* k50# k51# k52* k47 k48
2nd round k43* k45# k44# k46* k41 k42
3rd round k37* k39# k38# k39* k35 k36
4th round k31* k33# k32# k34* k29 k30
5th round k25* k27# k26# k28* k23 k24
6th round k19* k21# k20# k22* k17 k18
7th round k13* k15# k14# k16* k11 k12
8th round k7* k9# k8# k10* k5 k6
Final transformation uses k1* k2# k3# k4*
Explanation : k* is the multiplicative inverse of k modulus (2^16) + 1
k# is the additive inverse of k modulus 2^16