|
|
 |
PGP - Pretty Good PrivacyPGP 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 OverviewPGP 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 cryptosystemRSA uses modular exponentiation to encrypt and decrypt messages. The RSA function is C=T^E mod N 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 keysFirst we'll introduce the Euler's totient function. 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 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). 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) ) This encryption is secure, because without knowing P1 and P2, finding D from E is
impractical... Again, How do I find the keys?
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. The IDEA algorithmIDEA 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 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 :
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.
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 Final transformation uses k1* k2# k3# k4* Explanation : k* is the multiplicative inverse of k modulus (2^16) + 1 |