# Does it take long to implement RSA in hardware?

I just finished my first Digital Hardware course. We covered combinational circuits, sequential circuits and FSMs.

We now need to create a final design project. We have 2 weeks to do so and we work in teams of 2.

I want to implement RSA encryption in hardware. Essentially, the FPGA would take a audio signal as input, run RSA on it and output the encrypted audio signal. We will be using Verilog and a DE2 board. I'm worried that this might take too to do though.

Could someone tell me if implementing RSA in hardware is a reasonable goal for a 2 week project for someone who has only taken a single digital electronics course? This is my first engineering project so I'm not very good at scoping yet.

Thank you.

RSA will not be easy to implement and may require a very large FPGA. RSA is far better suited to running on a general purpose CPU than an FPGA. I have seen some implementations of RSA on an FPGA that use a softcore to run the algorithm and the FPGA to accelerate some of the math, but the complete algorithm is not implemented in Verilog. And generally when a file is "RSA encrypted," it usually isn't - the file is generally AES encrypted and the AES key is then RSA encrypted since AES is much faster than RSA. If you want to implement an encryption algorithm on an FPGA, especially for a streaming signal, AES would be a much better idea than RSA. You can probably implement AES in a week, it's a pretty simple algorithm.

RSA is not suitable for directly encrypting large amounts of data. Not only is it way too slow, but it is also weaker than some other algorithms against an opponent who has a large number of known plaintext/ciphertext pairs. To guard against this, data which is encrypted using RSA is usually padded with random bits beforehand. As a consequence, RSA ciphertext will generally be considerably larger than the size of the data payload.

The normal usage pattern for RSA is to generate a random key for some other cryptosystem and generate an RSA "cleartext block" which contains that random key along with some optional additional information about the file to be encrypted, filling any extra space with random bits. That block will then be encrypted and sent to the intended recipient along with a copy of the real file, encrypted using the other cryptosystem with the key that's included in the RSA-encrypted block.

I think that designing a serial "RSA accelerator" circuit to efficiently perform an NxK multiplication where K is a fixed value and N can be arbitrarily large might be a good challenge. Make it so that once the circuit is loaded with the short multiplicand, each chunk of the long multiplicand clocked in (LSB first) will generate the same-sized chunk of result data. If you use a chunk size of one bit, the multiplier could be implemented as N-bit two registers; if X is loaded with the K-bit value, and R with zero, then each step should perform:

if input is 1
output = R[0] xor (input and K[0])
R = (R+K)>>1
else
output = R[0]
R = (R>>1)
endif


Implementing things that precise way would require a K-bit carry chain that could operate in one cycle. With a little thought, however, adding another K-bit register would allow the circuit to behave just like the above, but a rather short worst-case propagation delay. Further, the amount of additional circuitry required to tackle two bits at a time would not be much greater than that required to handle one bit at a time.

Designing a multiplier that could easily be interfaced to a microcontroller via one or two SPI ports (if two, make one master mode and make the other one slave mode with its clock tied to the master) might be a reasonable challenge. If one was willing to restrict the RSA modulus to the form 1000...000xxxxx with 256 zeroes near the leading bits (this would require using a modulus that was 256 bits longer than would otherwise be necessary for a given level of security) an Nx256 multiplier would probably require something around a 2048-gate FPGA but allow even a small micro to perform RSA encryptions in a fraction of a second.

This is pretty challenging and unless you use an open source or readily available rsa implementation, 2 weeks is a stretch.

If you use some ready library for implementation it is possible to wrap up the the library to suit your needs.

This assumes you have a proven devkit you can use.