With all the talk on how to secure your desktop and send
encrypted messages, it would be unfair to leave out what goes on behind the
scenes. That’s why we have devoted this article to the most common techniques
and algorithms used in keeping your communication secure. Though they all use
complex mathematical calculations, we’ve left out most of the numbers and have
instead focused on how they actually work.
Simply speaking, secure communication happens in two parts–authentication
and encryption. In authentication, two parties try to identify each other using
digital certificates. The certificate is made of a digital signature generated
using DSA and MD5 algorithms. While, RSA and DES are commonly used algorithms
for encryption.
Authentication
DSA
This digital signature algorithm (DSA) is used for generating digital
signatures in digital certificates. Only someone who has a public-private key
pair can generate a digital signature.
A digital signature consists of two integers, called ‘s’
(signature) and ‘r’ (verification), which are sent to the client for
authentication. These integers are generated from several random integers.
First two prime integer numbers ‘p’ and ‘q’ are
taken. Then two random integers ‘h’ and ‘k’ are selected from these.
Here ‘h’ is in the range of 1 and p-1, while ‘k’ is a value greater than
0 and less than ‘q’. Subsequently, another value ‘g’ is calculated using
‘h’, ‘p’ and ‘q’. Finally, ‘r’ is calculated using ‘g’, ‘p’
and ‘q’.
For generating ‘s’, first a random message ‘m’ is
created. Then its hash is calculated using a hashing algorithm like MD5.
Finally, ‘s’ is generated using ‘k’, the hashed message, private key,
‘r’ and ‘q’.
The digital signature along with ‘p’, ‘q’ and ‘g’
is sent to the client for verifying its identity. The hashing algorithm used,
the message ‘m’ and the public key are also sent. On the client side the
message ‘m’ is first subjected to the hashing algorithm. Then a value ‘v’
(called verifier) is calculated from this hashed message, ‘s’, ‘p’, ‘q’,
and the public key. Now if ‘v’ is equal to ‘r’, then the digital
signature is verified.
MD5
MD5 (Message Digest) is a hashing algorithm used in
generating digital signatures. The output of MD5 is a message digest, which can
be used to authenticate the owner of a private key.
The MD5 algorithm takes a message and checks whether it’s
size is 448-bits. If it’s not, then it pads it with extra bits. Then it again
takes the original message and converts it to 64 bits. These are then added to
the 448 bits to give a block of 512 bits. This block is then broken into 32,
16-bit message blocks. A loop is started in which each of the 32 blocks are
processed. Outside this loop, four separate 32-bit variables–A, B, C, and D–of
standard values are taken. Then the values of these four variables–A, B, C, D–are
copied to four different variables say a, b, c, and d. Next, within the loop new
values are calculated for a, b, c, and d using the 16-bit blocks and the a, b,
c, and d values themselves. A different equation is used for each of these four
variables. Now A, B, C, and D are incremented with the new values of a, b, c,
and d.
Finally A, B, C, and D totaling to 128 bits (32x4) is the
hash calculated, which is also called a message digest.
Encryption
Broadly speaking there are two encryption techniques–symmetric
and asymmetric–used for secure communication. In symmetric encryption, the
same key is used for both encryption as well as decryption. This is known as the
private key. Consider two parties, A and B, wanting to engage in an encrypted
communication. Party A generates a private key and sends its copy to party B.
Hence both parties use this key to encrypt as well as decrypt messages.
In asymmetric encryption, party A generates a public-private
key pair, and sends just the public key to party B. When B wants to send a
secret message to A, it encrypts the message using A’s public key. When A
receives this encrypted message, it can only decrypt it with its corresponding
private key. Similarly, the reverse can also happen. This procedure is also
known as PKI or Public Key Infrastructure.
RSA
RSA, which is named after its developers (Rivest, Shamir,
Adleman), is an asymmetric or public key algorithm. In this, the public-private
key pair has a fixed length in bits, which can be decided at the time of their
generation like 512, 768, 1,024, 2,096, with higher numbers corresponding to
stronger encryption. When the public key is generated, it consists of the key
size and a positive integer called public exponent, which has some typical
standard values. The private key when generated includes these two along with a
private exponent and two prime numbers. The two prime numbers are derived such
that their product is equal to the key size. In RSA, key size is the same for
both keys. The private exponent in the private key is calculated from the public
exponent and the two prime numbers.
Once the keys have been generated, they are ready for
encrypting or decrypting data or message. The number of bits in the message
being encrypted must be less than or equal to the key size. If not, the message
is broken into separate blocks and then encrypted. If the message size is
smaller than the key size then some extra bits are padded to the message.
The encrypted message is created using the original message
itself, public exponent, and the key size information in the public key. When
the encrypted message is received on the other end, the private exponent and the
key size is used to decrypt it. Since the private exponent is calculated using
the public exponent, only the correct private key can decrypt the message. The
encryption and decryption of the message requires a lot of exponential
calculations. So RSA or as such public key encryption is slow.
DES
DES (Data Encryption Standard) is developed by IBM. It’s a
symmetric key encryption technique that encrypts messages in 64-bit chunks.
Though the actual key size is 64-bits, it only uses 56 bits for
encryption/decryption. The remaining 8 bits are used for checking whether the
key has changed during its transmission either accidentally or intentionally.
Both the 56-bit key and the 64-bit data go through a process
of permutation and transformation. The objective is to create sixteen, 48-bits
sub keys using the 56-bit key and the 64-bit data in 16 loops. The following is
the explanation of one loop.
The 56-bit key is first changed according to a key
permutation table. Permutation tables change the bit positions. Then the changed
key is divided into two 28-bit halves. The bits in each half are then shifted by
two places. The shifting is done in all the rounds except the first, second,
ninth, and the sixteenth round. Then from these two halves, a 48-bit key is
chosen using a compression permutation table.
The 64-bit data is divided into two 32-bit halves called a
left L and a right-half R. Now R is subjected to another permutation table
called the expansion permutation table where each 32-bit block is expanded to 48
bits (by padding and repeating some bits).
After this, R is XORed (pronounced Exclusive OR, which is a
digital gate function) with the 48-bit sub key generated from the 56-bit key.
The result of this is fed to 8 permutation tables known as S-boxes. Each S-box,
accepts 6 bits (8x6=48) and generates a 4-bit output. The total output from the
eight S-boxes is then combined, resulting in a 32-bit chunk. This 32-bit chunk
is then fed to another permutation table called a P-box. The P-box also produces
a 32-bit chunk, which is then XORed with L. Finally if this is not the sixteenth
round, L becomes R and vice versa. This swapping is called transformation. The
64-bit data undergoes 15 more such rounds for encryption. During decryption the
opposite process is repeated. Since the algorithm involves just XORing and
changes in bit positions, DES is relatively faster.
Triple DES or 3DES algorithm achieves greater strength by
encrypting the data or message three times using the same DES algorithm but each
time with a different key.
Shekhar Govindarajan