Data encryption has become a sad necessity for responsible data managers. However cryptography is jargon-heavy even by the discouraging standards of the IT world – symmetric and asymmetric cryptosystems, public versus private keys, digital signatures, hash algorithms, RSA, DES, Rijndael, PGP, MD5, SHA-1, https, secure sockets, Camellia, IDEA; what does it all mean? What are the differences? Relative advantages and disadvantages? Hopefully this article will clear some of the fog.

Although we tend to use the words ‘code’ and ‘cipher’ interchangeably, technically they're two entirely different things. When you substitute each letter in a message for a different symbol that's a cipher. A code on the other hand means assigning a secret meaning to a word or phrase.

For example, if "The birds are flying south" means "Flee! The police are on to us!" that's a code. But the simple schoolboy “code”, 1 = 'A', 2 = 'B' etc. (invented, legend has it, by Julius Caesar), is a cipher, a substitution cipher in fact. So the ASCII “code” is actually a kind of cipher for example.

Substitution ciphers were good enough for nearly two thousand years but they eventually failed in the face of improving technology. The Enigma cipher used by the German military during World War II is a substitution cipher and it was broken long before the days of computers, both by the Poles and more famously the British. Don’t, however, dismiss substitution ciphers. If you just want to deter prying eyes a substitution cipher using multiple substitutions and several different substitutions schemes offers a reasonable level of encryption for virtually no computational effort. (This is the way Enigma works and after all, it did take Alan Turing to break it).

There is a form of substitution cipher that does offer excellent security. By making random substitutions, the patterns that make other substitution ciphers vulnerable are eliminated. The simplest form of random substitution is to break a message into blocks of 4 bytes (4 ASCII characters) and add a pseudo-random number to each block. To recover the plaintext (the input message) subtract the same series of pseudo-random numbers from the ciphertext (the encrypted message). The key is simply the seed value for the pseudo-random number generator.

This form of encryption is widely used (the file encryption options offered by word processors often use this method) as it’s simple, highly reliable and will defeat all but the most determined and skillful attackers.

If, however, you need higher levels of security there are plenty of alternatives. Block ciphers break the message into fixed-length blocks, then each block of plaintext is converted into a block of ciphertext using a sequence of arithmetic operations and/or substitutions. The best known of these is DES (the Data Encryption Standard), developed by the National Institute of Standards and Technology in the US.

DES uses 64-bit blocks with a 64-bit key (although only 56 bits are significant; the other 8 are parity bits). The bits within a block are shuffled and XOR’ed with the key in a sequence of 16 substitutions called “rounds”, to create the ciphertext. Applying the same process (with the same key) to the ciphertext restores the original plaintext, so the process is symmetric. It has been very widely used, by the US government and commercial organisations around the world, including many financial institutions. It is easy to code (and there are good public domain implementations) and as it only involves bit-shifting operations combined with a few small look-up tables it doesn’t impose too much of a computational load.

Unfortunately, while it was secure enough in 1976 when it was introduced, advances in computer hardware mean the relatively short key is now vulnerable to a brute-force attack. A decent supercomputer or Beowulf cluster could check all possible DES keys in just a few days and the time can’t be far off when even a desktop PC will be enough to crack any DES-encrypted message.

Consequently the National Institute of Standards and Technology (NIST) no longer recommends DES and has instead proposed a successor, AES (Advanced Encryption Standard, also known as Rijndael – pronounced "rein-dahl" – from the names of its two inventors). AES is similar to DES in principle but uses much longer keys (128, 192 or 256 bits) and is specifically designed to resist the most sophisticated cryptographic attacks, methods such as timing analysis (looking for correlations between a plaintext and the time taken to encrypt it) and power analysis (looking for variations in the processor power requirements for encrypting different plaintexts). It has very low memory requirements so is particularly suited for embedded applications such as smart cards.

DES and AES are by no means the end of the story as far as symmetric encryption systems go. Microsoft uses a proprietary symmetric encryption system for Windows XP key validation and other systems you may encounter include RC4, RC6 and IDEA, while the European Union’s cryptography committee, NESSIE (New European Schemes for Signatures, Integrity and Encryption), recommends the Japanese Camellia cipher as an alternative to AES.

Symmetric block ciphers such as DES and AES can provide very high levels of security. However they have one obvious weakness, in that both sender and receiver must share the key, yet keep it secret from anyone else. This poses a particular problem for Internet commerce since a secret key would no longer be secret if it were sent over the Internet, and if it was embedded in a browser it could be discovered by reverse-engineering the program. On the other hand without some way to encrypt web traffic, sensitive details such as credit card numbers would be available to anyone with the slightest knowledge of TCP/IP.

The solution lies in an ingenious group of ciphers known as asymmetric or public key/private key systems. In asymmetric systems the key used to encrypt a message is not the same as that used to decrypt it. If a message has been encrypted using one key of a pair it cannot be decrypted even by someone else who has that key (crucially, knowing one key doesn’t provide knowledge of the other). Only the matching key of the pair can be used for decryption.

This seems rather extraordinary – almost magical on the face of it. If you know both the encryption algorithm and the key, how is it possible that the encryption process can’t simply be reversed to recover the original message? Nonetheless, that’s exactly how it is. Given a pair of keys, a message encrypted with one can only be decrypted with the other and vice-versa.

There are a number of asymmetric key systems but the best known and most widely used is RSA, named for its (three) co-inventors. Originally patented, the patent expired in September 2000 and the algorithm is now in the public domain. The Secure Sockets Layer used for secure communications on the Internet uses RSA (the https protocol is simply http over SSL).

Unfortunately, nothing in life is free, and so it is with asymmetric cryptosystems. Since d can be computed from e given p and q, and p and q are the factors of N, they must be chosen so large that N cannot be factorised in any reasonable time. As computer power has grown so too has the ability to compute the factors of very large numbers. Current hardware means key lengths should be 1024 bits for complete security.

Raising such very large numbers to very large exponents is computationally much more demanding than the bit shifting and XOR'ing of symmetric cryptosystems such as DES, so asymmetric encryption is really only practical for short messages. A common workaround when encrypting long messages is to use RSA to encrypt a short preamble containing a DES or AES key selected at random, then send the main body of the message encrypted with that key. A recipient with the corresponding private key can decrypt the preamble and use the key it contains to decipher the rest of the message. Modern web browsers use exactly this method to conduct secure communications.

An increasingly important use for asymmetric encryption is digital signing. A digital signature is the reverse of public key encryption. Just like an ordinary signature it is used to prove the identity of the sender of a message. This can happen in several ways. The simplest is to send a random message as both plaintext and ciphertext. The recipient deciphers the ciphertext version using the published public key and if the two versions match it proves the sender was in possession of the private key.

One drawback of this form of signature is that it only verifies itself, not any message to which it is attached. An alternative form uses a redundancy or hash function to create a message digest from a message in order to verify the source and reliability of the message. Suppose A and B (the Alice and Bob so beloved of cryptographers) want to exchange messages. A encrypts a message using B’s public key and appends the hashed value of the message encrypted with her own private key. On receiving the message B deciphers it using his private key, and also deciphers the accompanying message digest using A’s public key. If it matches the hash value he computes from the message he received, he can conclude that:

(a) The message originated from A (the only person who could have encrypted the digest correctly) and

(b) The message has not been altered in transit.

The RSA algorithm has become the standard for digital signature applications and the company founded by the co-inventors of RSA, RSA Data Security Inc, has developed (and published) a number of improvements on this basic scheme. Digital signatures on the Web are based on RSA, as is the popular PGP – Pretty Good Privacy – package.

Cryptography Techniques

Encryption - What is it and how does it work?

Encryption is esentially the transformation of meaningful data into non-meaningful data for the purposes of transportation so that anyone without a secret decryption key can not read the original meaningful data unless they are the intended recipient of the data.

Privacy is ensured by keeping the information hidden from anyone for whom it is not intended, even those who can see the encrypted (meaningless) data. As a simple example it is possible to encrypt files on a hard disk to prevent intruders from reading them.

However, when the environment, where data is exchanged, has many people transferring data within it, the risks of intruders, be they passive (attempting to read the data) or active (attempting to corrupt the data), increases to the point of justifying that all data packets leaving a particular node need to be encrypted.

Encryption allows secure communication over an insecure data comunications channel. It works as follows:

• 1. The sender intends to send a message to the recipient. The data is not to be seen by any other person that may also be using the same environment.
• 2. The sender completes writing the message which when read is meaningful. This is the plaintext.
• 3. He/She then encrypts the message with an encryption key. There are different types of encryption discussed below.
• 4. The encrypted message is sent off down the insecure communications channel to the intended recipient. The message in this meaningless form is called the ciphertext.
• 5. On arrival of the encrypted message, the receiver decrypts the ciphertext with the decryption key and reads the message.
• 6. While the ciphertext is in transit, an intruder, in order to read the message, may try the following: - obtain the secret key (eg by theft) or - recover the plaintext without using the secret key.

A secure Cryptosystem is one where the plaintext cannot be recovered from the ciphertext without using the decryption key.

Symmetric Cryptosystem

Here, the same single key is used as both the encryption key and the decryption key.

Secret-key cryptography

Secret-key cryptography is a very straightforward agreement between sender and receiver a message. Each party knows and uses the same secret key.

It works very simply:

• 1. The sender uses the secret key to encrypt the message.
• 2. The receiver uses the same secret key to decrypt the message.

This form of cryptography has one hugely insecure factor. How to keep the 'secret' key as a secret! The sender and receiver must agree on the secret key (usually text of some form, similiar to a login password) without any other party finding out.

If they are in separate physical locations, communication is required to agree on the key. They must trust a courier, the phone system, or some other transmission system to ensure that the secret key being communicated is not disclosed to anyone else but the two parties.Anyone who overhears or intercepts the key while in transit is capable of decrypting and thus reading all messages encrypted using that key.

Key management

This is the generation, transmission and storage of keys. All cryptosystems have to deal with key management issues. Secret-key cryptography often has difficulty providing secure key management due to the insecurity of agreeing on a secret key in the first place.

Public-key cryptography

Diffie and Hellman solved the key management problem in 1976 by inventing Public-key cryptography. This cryptosystem is based on the idea that each person gets a pair of keys, called a public key and a private key. Every user gets their public key published but the private key is kept secret. So the sender and receiver need not have to agree on, and communicate secret information (ie a key).

All communication involves public keys only. No private key is ever transmitted or shared. So trusting some communications channel to be secure against eavesdropping or betrayal is no longer an issue. The most important requirement is that no party can figure out the private key from the corresponding public key.

Any sender can send a confidential message just using the intended recipient's public key, but it can only be decrypted with the private key solely in the possession of the receiver.

Furthermore, public-key cryptography aswell as being used for privacy (encryption), can also be used for authentication (digital signatures - discussed below).

How Public-key cryptography functions:

• 1. The sender wishes to send a message to the receiver
• 2. He/She looks up the receiver's public key in a directory
• 3. The public key is used to encrypt the message and it is sent off
• 4. The receiver uses his/her private key to decrypt the message and read it.
• 5. No other party listening in can decrypt the message.
• 6. Anyone can send an encrypted message to the receiver but only the receiver can read it.

RSA - An example of a public-key cryptosystem

RSA was invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman. It is a public-key cryptosystem used for the purposes of both encryption and authentication.

The RSA Algorithm

• 1. Take two large primes, p and q.
• 2. Find their product n = pq; n is called the "modulus".
• 3. Choose a number, e, less than n.
• 4. e must also be relatively prime to (p-1)(q-1).
• 5. Find its inverse, d, mod (p-1)(q-1).
• 6. This means that ed = 1 mod (p-1)(q-1).
• 7. e and d are called the public and private exponents, respectively.
• 8. The public key is the pair (n,e) and the private key is d.
• 9. The factors p and q must be kept secret, or destroyed.

It is presumed to be too difficult to obtain the private key d from the public key (n,e). This is the fundamental irony of RSA. We could call this both a flaw and an adequately good enough security measure. If an intruder could factor n into p and q, then he could obtain the private key d.

So the entire security of RSA is predicated on the assumption that factoring (of two very large primes) is difficult. In theory an easy factoring method would ``break'' RSA.

RSA privacy (encryption)

• 1. The sender wants to send a private message, m, to the receiver.
• 2. The sender creates the ciphertext c by exponentiating: c = m^e mod n, where e and n are the receiver's public key.
• 3. To decrypt, the receiver performs the exponentiation: m = c^d mod n, and recovers the original message m.
• 4. The relationship between e and d ensures that the receiver correctly recovers m.
• 5. Since only the receiver knows d, only he/she can decrypt the message.

Authentication and Digital signatures

While encryption dates back to the times of Caesar, digital signatures are more recent. This is due to the proliferation of digital communications and in this context the exponential growth of the Web.

Authentication is the use of digital signatures and holds the same function and meaning for digital documents as handwritten signatures do for printed documents. In paper and ink terms, a signature is an unforgeable piece of information unique to a particular person who has written or has agreed with the contents of the document where their signature is attached.

The recipient (as well as a third party) can verify that the document did originate from the person whose signature is attached and also that the document has not been tampered with since it was signed and dispatched.

The same concepts hold for electronic messages. Authentication in the context of Web Security is where the receiver of a digital data message can be confident of the identity of the sender and of the validity of the message.

Popular examples of authentication protocols in use today are: secret-key cryptosystem: DES, public-key system: RSA (detailed below) Authentication in public-key systems uses digital signatures.

All secure cryptosystems consist of two parts: The method of signing the document at the senders end, making forgery an impossibility, and the method of verifying that the signature was actually generated by the real sender, at the receivers end.

Public-key cryptography for the purposes of authentication works as follows

• 1. The sender, to sign a message, does a computation involving both their private key and the message itself.
• 2. The resulting output of this computation is called the digital signature and it is attached to the message.
• 3. The package is then sent.
• 4. The receiver needs to verify the signature. This is achieved by performing some computation involving:
  • the message
  • the supposed senders signature and
  • the sender's public key

• 5. If the results hold in this simple mathematical relation then the signature is verified as genuine. If not, they are discarded because the signature may be fraudulent or the message may have been altered.

So it would seem that there is no way secure digital signatures can be the cause of conflict. The signer of a document would never be able to disown it by later claiming it was forged.

RSA authentication (digital signature writing)

• 1. The sender wants to send a signed document m to the receiver.
• 2. The sender creates a digital signature s by exponentiating: s = m^d mod n, where d and n belong to the sender's key pair.
• 3. He/She sends s and m to the receiver.
• 4. In order to verify the signature, the receiver performs the exponentiation: m = s^e mod n, where e and n belong to the sender's public key, and hence has checked that the message m has been recovered intact.

So in keeping with public-key principles, encryption and authentication take place without any sharing of private keys. Each person uses only other people's public keys and his or her own well guarded private key.

Again anyone can send an encrypted message or verify a signed message, using only public keys, but only someone in possession of the correct private key can decrypt or sign a message.

Public-key cryptography versus Secret-key cryptography
The advantages and disadvantages:

• The obvious advantage of public-key cryptography is increased security in that the private keys need not ever be communicated, transmitted or revealed to anyone.
• This, in contrast, is the insecurity of a secret-key system. There is always the possiblility that another rogue party could discover the secret key while it is being transmitted for agreement purposes.
• From the authentication point of view public-key systems are a major advantage in that they can provide a method for digital signatures.
  
  Authentication via a secret-key system would require the sharing of some secret key and sometimes requires trust of a third party as well. A sender could then deny any association with a previously signed message by claiming that the shared secret was somehow compromised by one of the parties sharing the secret. However this conflict would never arrive using public-key authentication because each user is responsible for protecting his/her private key. This property of public-key authentication is called "non-repudiation".
• From the judicial point of view, digitally signed messages can be proved authentic to a third party, such as a judge, thus allowing such messages to be legally binding.
• The major disadvantage of using public-key cryptography for encryption is speed of encrypting a message before dispatching it. Most popular Secret-key encryption methods are significantly faster than any public- key encryption methods currently available. So obviously the trade-off involves secure key management against speed.
• A compromise is achieved where public-key cryptography can share the burden with secret-key cryptography to get the best of both worlds.

Encryption combining public keys and secret keys

In order to utilise both the security advantages of public-key systems, and the speed advantages of secret-key systems, the solution is to combine public- and secret-key systems.

Initially the public-key system can be used to encrypt a secret key. The secret is probably small in size, so speed of encryption is not important. Once such a key has been securely communicated between patries, it is then used to encrypt a complete file or message. This may be large in size, but the sender and receiver have the assurance that it is being encrypted as quickly as possibly and that the secret-key has been shared using a sound secure method. This is indeed the case in RSA.

Conclusion

Public-key cryptography is not meant to replace secret-key cryptography, but rather to supplement it, to make it more secure. The first use of public- key techniques is for secure key exchange in an (otherwise) speedy secret-key system. Hence secret-key cryptography is still extremely important.

Parimal Sudas

Assitt. Professor