# Is there a fast implementation of RSA for Microcontrollers?

Zhe Liu, Johann Großschädl, and Ilya Kizhvatov. "Efficient and Side-Channel Resistant RSA Implementation for 8-bit AVR Microcontrollers" describes a fast implementation, but only contains a sketch of the algorithm with partial pseudo-code.

Is there a worked implementation publicly available?
If not, what is a good fast implementation for small-memory footprint microcontrollers?

• The paper's claim is $76⋅10^6$ CPU cycles for 1024-bit private key operation (+12% for side-channel protection), with like $\mathcal O(n^3)$ scaling. This is impressive, but still credible: about 8 cycles for one 8×8→16 bit MUL and two 8-bit ADD, which leave about 4 cycles for operand fetches and overhead, using a method that plausibly minimizes fetches and overhead by leveraging the numerous CPU registers. However, in practical terms in the Smart Card industry that still is too slow, not security certified. We do private-key RSA with special hardware; software is good only for public-key. – fgrieu Dec 9 '15 at 12:15