How Block Ciphers Work

Back in May I gave a brief introduction to encryption and decryption. The next few posts are a short series on symmetric encryption algorithms, which use a shared secret key for both encryption and decryption. I've got a little bit of coverage about the general algorithms and issues with this type of cryptography before giving some examples of the actual algorithms that are used. The encryption algorithms I'll talk about come in two varieties, called block ciphers and stream ciphers.

Block ciphers split the input text into fixed-size chunks called blocks. Each block of the input is exactly the same length as all of the other blocks, for example 16 bytes. Since most input texts are not going to be an exact multiple of the block size, the encryption algorithm needs to pad the input text with some additional bytes to fill out the last block. The decryption algorithm needs to remove those pad bytes before returning the resulting text. Typically, the number of pad bytes is added to the message for this purpose, meaning that every message encrypted by a block cipher is between 1 and the size of the block bytes larger than before encryption. Small messages can be inefficient to transmit using block ciphers.

The operation of a block cipher is to take a block of input text and a block of key to produce a block of output text. You can think of this action as a table that contains all of the possible input text blocks as rows and all of the possible key blocks as columns, giving a value for every row-column combination. This table defines the function for encryption. There's then another table that defines the function for decryption. If you've got an input block M and a key block K, then the encryption function gives you an output block O. If you then look at row O, column K of the decryption function table, then the value of that entry will be M. As long as the two sides know the key blocks, they can exchange messages.

The weakness of this simple method is that if we use a fixed key block and parts of the message repeat, then the corresponding parts of the encrypted text will also repeat. When we look at symmetric encryption algorithm issues, this is one of the ones we'll try to address.

Next time: How Stream Ciphers Work