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:
Expansion
Key mixing
Substitution
Permutation
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.
Re: Another option for acceleration with faster time to market!
Hi Rob,
Glad you liked it, your approach is good for someone who just has some code and has no wish to get into how he can transform it into RTL, and with softcore processors its always possible to extend the instruction set.
@Adam in the case of AES, FIPS have published a set of known result vectors which you can incoporate into your testbench if you can show that your implmentation produces the same results then you are good to go.
Another option for acceleration with faster time to market!
Hi Jerry, great article and we have another way of Accelerating Algorithms with FPGAs, but without going to HDL. Our newly released MXP Matrix Processor, adds a scalable soft core co-processor to the FPGA that increases performance by a couple orders of magnitude. At the same time we have a SW based methodology that allows you to create and maintain your algorithms in C/C++, while it leverages our processor.
So we have effectively decoupled the engine from the algorithms and provide great performance and flexibility, without the need for HDL.
We are not saying that in all cases you will get the same performance as a complete HDL version, but we can sure get your algorithms based FPGA solutions in the market quicker, and give you way more flexibility to modify/iterate on the fly.
Adam Taylor 11/16/2012 12:21:07 PM User Rank Blogger
Interesting Blog
Very interesting blog, the project I just worked on implemented AES in FPGAs for both the ground and flight systems they handle both the command and control of the satelllite and payload data encryption.
I know the FPGA team faced some interesting challenges in making the RTAX reach the speeds required.
One interesting point is that it is just not the algorithm that makes it secure but how the security architecture is segemented etc and what checking is involved if you are going for acreditation.
Re: RC4 is not the algorithm you are looking for...
Oh by the way, you know ian and clare harvey scream that they are never going to tell anyone why they lied to everyone at ncipher, its basically because ian harvey is obsessed about john hartley, as is Alex van sommerans wife, but after they placed the blanet ban on anyone asking them about it I met a guy and his wife who helped me and it turned out that he is an ex-professional cyclist so he got me into cycling, and iv been working on embedded systems and FPGA development ever since. I did the video processing hardware for all the ANPR cameras you see on police cops on the telly and also high speed serial stuff for mixing desks in Oxford.
I still do lots of bike racing and HUGE rides with this guy who after you get to the stage where you can just about hold his wheel when he sprints, turns round and says 'of course you know ive won stages in the giro d'italia don't you' and then proceeds to drag you up even bigger sodding hills.
Hills with their own names are bad news, if its called big bastard hill its bad news, and there is one we do round Winchester called 'steep hill' which goes on for about 500 miles and is near vertical. but its all good.
Re: RC4 is not the algorithm you are looking for...
Yeah well, that's why I don't do cambridge, there are people there going
Conceited? Moi?
Although secretshoppers secret identity has me intriguied, probably better to remain unknown.
anyway on with the show Ive got more bloggy stuff to send you, things about simulations which is then an opener for the continuation of the GOL, Hurrah!!
SecretShopper 11/14/2012 2:47:50 AM User Rank Beginner
Re: RC4 is not the algorithm you are looking for...
max,its a long story, I know Jez from way back when there was a slight explosion in cambridge, it is like a soap opera with added confusion caused by my ex-boss who is possibly the most conceited person in the entire history of the universe.
When you get out of cambridge and back into the real world you start to realise what a deeply strange place it is.
John Hartley knows who he is.
Most people I think you'll agree would say that if you apologise for something once, you really dont want to end up having to apologise a second time for doing exactly the same thing.
That's why I got out of cambridge, some people there are really not in very good places.
I don't wish to say more about it, Jez may respond, if he doesn't its understandable.
The Zynq-7000 All Programmable SoC uses the AXI protocol and buses to allow its Cortex-A9 processor system to communicate with, and control, custom logic implemented in the programmable fabric.
There is a flaw in my example code, which means that although it will compile with no errors, it won't actually work. Tracking down the problem requires us to use a testbench.
In which we define how each CA looks to the outside world -- it has a "clock" signal and a "reset" signal, and it also has signals that communicate its state to its neighbors along with signals that let it read its neighbors' states.
To save this item to your list of favorite All Programmable Planet content so you can find it later in your Profile page, click the "Save It" button next to the item.
If you found this interesting or useful, please use the links to the services below to share it with other readers. You will need a free account with each service to share an item via that service.
Tweet This
