# Memory Efficient Implementation of Modular Multiplication for 32-bit ARM Cortex-M4
## 1 Introduction
### Research Contributions  
In contrast to most of the previous implementations, which have focused primarily on the execution time, this study focused on optimizing the memory consumption of multi-precision multiplication implementation and multi-precision squaring implementation, without reducing the high performance. In particular, we present a MAC operation. The operation is used for the inner loop of target multiplication and squaring operations.  
The proposed MAC routine fully employs general purpose registers and a \(32\times 32+32+32\to 64\)-bit multiplier, also known as Unsigned Long Multiply with Accumulate Accumulate (UMAAL). Second, the squaring algorithm is further optimized through a dedicated doubling routine. Finally, the proposed implementations achieved a very small memory footprint and good scalability; thus, they can be used for RSA, ECC, and SIKE. We implemented all of the second round of SIKE protocols on 32-bit ARM Cortex-M4 microcontrollers. A reasonable execution timing can be achieved with the smallest code size.  
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**Methods** & **Code Size** & **Scalability** & **SIKE** & **ECC** & **RSA** & **Speed Record** & **Hybrid Protocol** \\ \hline \multicolumn{8}{c}{**Multi-Precision Multiplication**} \\ \hline \hline \multicolumn{1}{c}{[PERSON] \({}^{\dagger}\)[9] & 1284 & & ✓ & & & & \\ Santis and Sigl \({}^{\ddagger}\)[10] & 1264 & & & ✓ & & & \\ Fujii and Aranha \({}^{\ddagger}\)[11] & 622 & & & ✓ & & & \\ Haase and Labrique [12] & 452 & & & ✓ & & & \\ [PERSON] et al. [13] & – & & ✓ & & & & \\ [PERSON] et al. [14] & 452 & & & ✓ & & ✓ (U) & \\ [PERSON] et al. (SIKE) [14] & 3,396 & & ✓ & & & ✓ (U) & \\ This work & 260 & ✓ & ✓ & ✓ & ✓ & ✓ (L,P) & ✓ \\ \hline \multicolumn{8}{c}{**Multi-precision squaring**} \\ \hline \hline \multicolumn{1}{c}{[PERSON] \({}^{\dagger}\)[9]} & 1168 & & ✓ & & & & \\ [PERSON] and [PERSON] \({}^{\ddagger}\)[10] & 882 & & & & ✓ & & \\ [PERSON] and [PERSON] \({}^{\ddagger}\)[11] & 562 & & & ✓ & & & \\ [PERSON] and [PERSON] [12] & 324 & & & ✓ & & & \\ [PERSON] et al. [14] & 320 & & & ✓ & & ✓ (U) & \\ [PERSON] et al. (SIKE) [14] & 2372 & & ✓ & & & ✓ (U) & \\ This work & 324 & ✓ & ✓ & ✓ & ✓ (L,P) & ✓ \\ \hline \hline \end{tabular} \({}\dagger\) symbol indicates implementations with fast reduction.  
\end{table}
Table 1: The comparison results of multi-precision multiplication implementation and multi-precision squaring implementation on 32-bit ARM Cortex-M4 microcontrollers in terms of the code size (in bytes), scalability, and highest speed. The Elliptic Curve Cryptography (ECC), Rivest-Shamir–Adleman (RSA), and Supersingular Isogeny Key Encapsulation (SIKE) symbols represent the targeted implementation with the modular arithmetic implementation (Letters U, L, and P indicate whether the works are implemented in unrolled, looped, or parameterized).  
The paper is written as follows. In Section 2, previous implementations of multiplication/squaring, target ARM Cortex-M4 microcontrollers, and SIKE Round 2 candidates are introduced. In Sections 2.4 and 2.5, implementations of the multi-precision multiplication method and multi-precision squaring method are presented. In Section 3, a case study of SIKE round 2 protocols is given. The proposed implementations are evaluated in Section 4. Conclusion is given in Section 5.