Here on All Programmable Planet there has been some talk about looking at how FPGAs can be used to implement algorithms that have been traditionally implemented in software -- also how the inherent parallelism of an FPGA can be used to improve the performance of certain algorithms. So, I thought it might be instructive for us to take a look at the DES (Data Encryption Standard) algorithm as an example of what FPGAs can "bring to the table."
DES was developed by IBM in 1972 as an encryption standard. It was originally designed to be easy to implement using the hardware that was available at the time. DES has now been superseded by other techniques and -- for a variety of reasons -- is not used in serious cryptographic applications any longer.
One of the criticisms of DES is that it is not particularly easy to implement in software and it tends to be slow. The following illustration shows the overall structure of the DES algorithm:
In this image, the blocks marked "IP" and "FP" perform the initial and final permutation stages. These blocks don't actually have much effect and are largely there for historical reasons related to how the original implementations were performed. As we can see, there are 16 "F" functions; the F function is quite complex and performs the following tasks:
- Key mixing
These tasks are shown diagrammatically in the following image, but the nitty-gritty details of these functions are beyond the scope of this article:
The main point here is that, traditionally, the software solution to implementing this algorithm has been to perform all the various stages as a series of loops. Due to the serial nature of software, there isn't a great deal that can be done to improve performance.
Next page >