RSA Signature Verification Implementation on Cortex M0 I have to implement RSA Signature Verification procedure (RSA-2048) on a Cortex M0 based MCU. My budget is 15kB Flash and 2-4kB Flash RAM.

Is it even possible to do RSA on a low end MCU based on Cortex M0?
As pointed by CodesInChaos, you'll need to know the padding used; depending on application that could be RSASSA-PKCS1-V1_5, or RSASSA-PSS, or some of the three schemes of ISO/IEC&nbsp;9796-2, etc.. Hashing, and padding check, are a significant part of the code.

In any case, yes, it is possible to implement RSA-2048 signature verification on a Cortex-M0 based MCU, with much less than 15&thinsp;kB code and 2&thinsp;kB RAM. That's extremely ample even including hashing, and padding check.

With tight coding we are talking 2 to 5&thinsp;kB code (depending on hash and padding, including code for RSA and SHA-1, SHA-256 or even SHA-512) and at most 1.4&thinsp;kB RAM (temporarily used in stack or heap, not dedicated) including public key and signature (assumed already properly aligned bytes).

To give an order of magnitude of the speed achievable: for $e=65537$, a simple but good implementation of the RSA public function is dominated by a core loop executed about $17\cdot(2048/32)^2$ times, comprising 8 MULS, 3 memory reads, 1 memory write, and like 16 other single-cycle operations; thus, on a 40&thinsp;MHz CPU running without code wait states, like 70&thinsp;ms with single-cycle MULS (or 500&thinsp;ms with the 32-cycle MULS of some Cortex-M0 variants).

Speed (and code density) will also depend on


using assembly in the critical loops, rather than C which typically generates sub-optimal code for RSA arithmetic (notably, because C only has a tortuous idiom for carry propagation);
not using Montgomery arithmetic, which introduces complexities hardly justifiable for RSA signature verification and common (low) public exponents $e$;
value of public exponent; $e=3$ can be like 8 times faster than $e=65537$ (for short messages);
size of what's signed (influencing hash time);
care of programming; this is not easy!




An archetypal implementation of modular exponentiation $Y\gets X^e\bmod N$, geared for RSA signature verification with typical parameters including moderate public exponent $e&gt;0$, optimized for low RAM footprint, code simplicity, and speed, can uses left-to-right binary exponentiation at the top level:


$Y\gets X$
set $j$ to the number of bits in $e$, that is $\lceil\log_2(e+1)\rceil$
while $j&gt;0$


$Y\gets Y\cdot Y\bmod N$
$j\gets j-1$
if bit $j$ in the binary representation of $e$ is set, that is if $\lfloor e/2^j\rfloor\bmod 2\ne0$ 


$Y\gets X\cdot Y\bmod N$




This requires 2 modular multiplications for $e=3$, and 17 for $e=65537$.

In an implementation optimized for size (and simplicity) we'll have a single piece of code to perform $Y\gets X\cdot Y\bmod N$, and we'll replace argument $x$ by $Y$ when performing $Y\gets Y\cdot Y\bmod N$. Our modular multiplication will use more or less clever variants of the ‘classical’ algorithms commonly used by hand in decimal, only using base $2^w$ instead of base 10, where $w$ is some convenient word width. We note $n$ the number of $w$-bit words in $N$. Execution time will be $\mathcal O(n^2)$. On Cortex-M0 we'll probably use $w=32$ (or $w=16$ which would give simpler and shorter code, with only moderate speed penalty for the Cortex-M0 variant with 32-cyle MULS, but much more in proportion for the variant with single-cycle MULS).

The simplest option for modular multiplication is algorithm 14.28 in the Handbook of Applied Cryptography, which performs multiplication (using multiplication per algorithm 14.12) followed by modular reduction (using Euclidean division per algorithm 14.20 ignoring the quotient, or Barrett reduction per algorithm 14.42). This is has some drawbacks, though:


each modular multiplication requires $\mathcal o(2n^2)$ memory reads, $\mathcal o(n^2)$ memory writes, and $\mathcal o(n^2)$ loops for the multiplication, and modular reduction requires as many; when other algorithms reduce that to a total of $\mathcal o(3n^2)$ memory reads, $\mathcal o(n^2)$ memory writes, and $\mathcal o(n^2)$ loops (the same asymptotic cost as a good implementation of the equivalent of modular multiplication in Montgomery arithmetic);
the intermediary result is twice as wide as $N$, which consumes some RAM;
the index in this intermediary result is not the same as the index in other operands, thus we have two indexes to maintain.


These three drawbacks can be avoided without using Montgomery arithmetic (which requires pre and post computations that increase code size, and have significant speed penalty for low $e$), as follows.

For any integer $Z$, we note $Z_j$ the $j$th digit of $Z$ in base $2^w$, that is
$$Z_j=\left\lfloor{Z\bmod 2^{(j+1)\cdot w}\over2^{j\cdot w}}\right\rfloor$$
so that
$$0\le Z&lt;2^{k\cdot w}\implies Z=\sum_{0\le j&lt;k}Z_j\cdot2^{j\cdot w}$$
$N_0$ is odd since $N$ is odd, and $N_{n-1}&gt;0$ since $n$ words are required to write $N$. We define (and precompute early, e.g. as a preliminary of exponentiation) $M_j=2^w-N_j-1$ for $0&lt;j&lt;n$ and $M_0=2^w-N_0$, corresponding to $M=2^{n\cdot w}-N$; and
$$H=\min\left(\left\lfloor{2^{5\cdot w}\over N_{n-1}\cdot2^{2\cdot w}+N_{n-2}\cdot2^w+N_{n-3}}\right\rfloor,2^{3\cdot w}-1\right)$$
as the corresponding $H_2$, $H_1$, $H_0$, which will help in quotient estimation.

The general sketch of modular multiplication goes:


$T\gets Y_{n-1}\cdot X$ over $n+1$ digits, using a loop scanning the $X_j$ and $T_j$ by increasing index;
for $i=n-2$ downto $0$ (a loop invariant being that $T&lt;N\cdot2^w$)


find an approximation $q$ of the next quotient chunk $\left\lfloor{T\cdot2^w+Y_i\cdot X\over N\cdot2^w}\right\rfloor$, erring up by at most $1$ by excess, and with $0\le q\le2^w$ (which it turns out is possible using a constant number of multiplications and additions involving $T_n$, $T_{n-1}$, $T_{n-2}$, $X_{n-1}$, $X_{n-2}$, $Y_i$, $H_2$, $H_1$, $H_0$);
$T\gets T\cdot2^w+Y_i\cdot X+q\cdot M\cdot2^w$, over $n+1$ digits and an extra one $t$ for what would have been $T_{n+1}$, using a loop scanning the $X_j$, $M_j$ and $T_j$ by increasing index; most of the time is spent in this single loop with $q\ne2^w$ (the special case $q=2^w$ must be detected and handled separately, but is faster than the general case);
if $t&lt;q$ (which is rare and will thus consume negligible time), then $q$ was one higher than it should have been:


$T\gets T-M$, using a loop scanning the $M_j$ and $T_j$ by increasing index;


$Y\gets T\bmod N$ (one way to do this is as an extra iteration of the above, with a virtual $y_{-1}=0$, and mapping the $T_{j+1}$ of the result to $Y_j$).


The essential thing is that we manage to perform multiplication and modular reduction in the same loop doing $T\gets T\cdot2^w+Y_i\cdot X+q\cdot M\cdot2^w$, with the quotient digit $q$ on a single word, using operations with fair native support (word multiplications and additions with carry; that's even though each full $32\times32\to64$ multiplication will require four MULS). As often in crypto, and especially crypto implementation, the devil is in the details.



Doing signature generation with appropriate speed and security is much more difficult. That's going to be like 50 times slower than signature verification with $e=65537$, using the CRT and regular two-factors RSA (and otherwise comparable code for the two modular exponentiations). The code will be significantly larger (though still feasible within the code and RAM budget). For some padding schemes including RSASSA-PSS and ISO/IEC&nbsp;9796-2 scheme 2, a TRNG with some strength will be required, making the code's interfaces much more complex. Most importantly, it will be practically impossible to hide the required secret key from a JTAG debugger or the like, and even quite hard to safeguard it from timing and other side-channel attacks.