# Memory Efficient Implementation of Modular Multiplication for 32-bit ARM Cortex-M4
## 2 Background
### Multi-Precision Multiplication
Table 4 compares the practicality of implementations for public key cryptography. Previous works only focused on the speed optimization for one targeted PKC protocol. However, real world applications require multiple cryptography implementations to communicate with heterogeneous systems with multiple PKC schemes and security levels. Furthermore, for modular arithmetic of RSA implementations, speed optimized implementation requires a huge code size (See Table 1). On the other hand, the proposed modular arithmetic implementation supports all RSA, ECC, and SIKE with the smallest code size (e.g., 584 bytes) and reasonable execution timing. In terms of the energy consumption, the proposed method actually consumes more energy than speed optimized implementation due to the high latency (i.e., long execution timing or long working time), which \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Public Key Cryptography** & **ECC** & **All ECC** & **SIKE** & **All SIKE** & **RSA** & **All RSA** \\ \hline \hline [PERSON] \({}^{\ddagger}\)[9] & \(\surd\) & – & \(\surd\) & – & – & – \\ [PERSON] and [PERSON]\({}^{\ddagger}\)[10] & \(\surd\) & – & \(\surd\) & – & – & – \\ [PERSON] and [PERSON] \({}^{\dagger}\)[11] & \(\surd\) & – & \(\surd\) & – & – & – \\ [PERSON] and [PERSON] [12] & \(\surd\) & – & \(\surd\) & – & – & – \\ [PERSON] et al. [13] & \(\surd\) & – & \(\surd\) & – & – & – \\ [PERSON] et al. [14] & \(\surd\) & – & \(\surd\) & – & – & – \\ This work & \(\surd\) & \(\surd\) & \(\surd\) & \(\surd\) & \(\surd\) & \(\surd\) \\ \hline \end{tabular} \({}^{\ddagger}\) Including fast reduction.

\end{table} 
Table 4: Comparison of practical implementations. \begin{table}
\begin{tabular}{l l l l l l l l l l l} \hline \hline
**Implementation** & **Language** & \multicolumn{3}{c}{**Timings [cc]**} & \multicolumn{3}{c}{**Timings [cc \(\times\) 10\({}^{\ddagger}\)]**} & \multicolumn{3}{c}{**Throughput**} & \multicolumn{1}{c}{**ROM**} & \multirow{2}{*}{**Optimization**} \\ \cline{3-3} \cline{6-11} SIKEp434 & & & \(\mathbb{F}_{p}\)**, mul** & \(\mathbb{F}_{p}\)**sqr** & & & & & & \\ [PERSON] et al. [14] & ASM & 1110 & 981 & 74 & 122 & 130 & 252 & 1.50 & 33,528 & Speed \\ This work & ASM & 3147 & 2693 & 139 & 227 & 242 & 469 & 2.79 & 29,176 & Size \\ \hline SIKEp503 & & & & & & & & & & \\ [PERSON] et al. [14] & ASM & 1333 & 1139 & 104 & 172 & 183 & 355 & 2.11 & 37,912 & Speed \\ This work & ASM & 3888 & 3280 & 197 & 326 & 346 & 672 & 4.00 & 30,488 & Size \\ \hline SIKEp610 & & & & & & & & & & \\ This work & ASM & 5651 & 4639 & 340 & 631 & 634 & 1265 & 7.53 & 27,432 & Size \\ \hline SIKEp751 & & & & & & & & & & \\ [PERSON] et al. [14] & ASM & 2744 & 2242 & 282 & 455 & 491 & 946 & 5.63 & 44,688 & Speed \\ This work & ASM & 7693 & 6228 & 587 & 953 & 1022 & 1975 & 11.76 & 28,816 & Size \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Comparison of SIKE round 2 schemes on ARM Cortex-M4 microcontrollers. Timings are measured in clock cycles. Code size is reported in terms of bytes. Throughput is reported in terms of seconds per operation at 168 MHz. consumes high energy [31; 32; 33]. However, the proposed method is a suitable solution when considering the reasonable code size in real-world implementations. The importance of energy consumption for PKC is relatively lower than block cipher as PKC only needs one time before the secure communication as a secure key exchange (i.e., Diffie-Hellman). For this reason, the energy consumption metric of PKC implementation is of relatively lower priority than the code size in a real-world setting. ## 5 Conclusions

In this paper, we presented scalable implementations of multi-precision multiplication, squaring, and the Montgomery algorithm on the 32-bit ARM Cortex-M4. The implementation emphasizes reducing code size and providing scalability with practically fast speed. We proposed several novel techniques to further boost the implementations on low-cost 32-bit ARM processors, including MAC as well as doubling and MAC techniques.