Cryptography on FPGAs


#1

In Cryptography, algorithms like RSA largely rely on the practical difficulty of prime factorisation. Fast algorithms such as Eratosthenes’ prime sieve allow to identify very large prime numbers required for encryption.

In 1978 Tony Hoare, in his CSP paper, described Eratosthenes’ sieve in form of a pipeline of processes (aka daisy chain of filters).

A concurrent prime sieve implementation is available in Go: https://golang.org/s/prime-sieve
(The sieve of Eratosthenes can find all the primes up to N in time O(N log log N) unlike its competitors which run in linear time)

We have shown that the algorithm runs faster on FPGAs at least by an order of magnitude!

It is usual to develop a modified form of sieving of your own by chaining these filters. Have you ever thought of developing your own Encryption/Decryption application?


#2

Here is a deterministic implementation of concurrent prime sieve with five filters using our compiler:

Couple of notes about the implementation above:
Since we can’t feed the entire input array into the mod filters at once it’d be necessary to have a stream of input numbers and implementing filters on demand (Actually if we could feed the entire array into the chain at once we would have filters implemented one at a time!)

As stated above a stream of data getting into the system via Ethernet/PCI would be ideal. When having a stream of inputs, filters got to be created on-the-fly, which makes it impossible to determine the number of the filters in advance.
In a spatial computer where computation resources are allocated statically a deterministic notion of the number of the filters is necessary (unless we assume we are not limited by space/area!).
In a timed computer (CPUs) processes are initiated on demand as long as there is enough memory (otherwise you’d face a SF!).
Also in hardware modules like div and mod are expensive to implement. By having a multiple FPGA system this scalable application would be a nice use case indeed (in other words we wont run out of DSP blocks quickly!).

Next Update: will be exploiting a multiple-FPGA system capability of streaming inputs and fitting millions of these filters in form of bump-in-the-wire. Stay tuned!


#3

I’ve completed a SHA256 hash generator which I’ve posted to https://github.com/foolmarks/reco_sha256.