# Memory Efficient Implementation of Modular Multiplication for 32-bit ARM Cortex-M4
## 2 Background
### Multi-Precision Multiplication
The inner loop of operand scanning is given in Algorithm 6. In line 1, one operand \(Q\) is loaded to the register (R8). In line 2, the intermediate result is loaded to the register (R9). In line 3, the 32-bit wise MAC is performed. In line 4, the result is stored in the memory. Figure 4: Proposed operand scanning multiplication for Montgomery reduction. **Left part**: outer loop, an example of SIKEp434. **Right part**: inner loop, \((q0\cdot M)\). ```
0: operand pointers R1, R4
0:results {R9, R10}
1:LDM R11, {R8}
2:LDR R4, {R4}
3:MNAL R9, R10, R7, R8
4:STM R41, {R9}
```
**Algorithm 7** 32-bit wise scalable operand-scanning for Montgomery reduction. In Algorithm 7, 32-bit wise scalable operand-scanning for Montgomery reduction is described. All operations are performed in 32-bit wise. In particular, the inner loop (i.e., line 4) is performed with the Algorithm 6. ```
0:modulus \(m\), constant \(m^{\prime}\), and \(len\) (operand length/word where the word is 32-bit)
0:results (\(r\))
1:for\(i=0\) to \(len-1\) by \(1\)do
2:\(prod=0\)
3:\(q=r[0]\times m^{\prime}\) mod \(2^{32}\)
4:\(prod=m[0]\times q\) {Algorithm 5}
5:\(prod+=r[0]\)
6:\(prod=prod\gg 32\)
7:for\(j=1\) to \(len-1\) by \(1\)do
8:\(prod+=m[j]\times q\)
9:\(prod+=r[0]\)
10:\(r[j-1]=prod\)
11:\(prod=prod\gg 32\)
12:endfor
13:\(prod+=r[j]\)
14:\(r[j-1]=prod\)
15:\(r[j]=r[j+1]+prod\gg 32\)
16:endfor
```

**Algorithm 8** 32-bit wise scalable operand-scanning for Montgomery reduction. ## 4 Performance Evaluation and Comparison

### Evaluation of Modular Arithmetic

The 32-bit ARM Cortex-M4 processor is evaluated with the STM32F4 Discovery board. The board supports 1 MB of Flash and 192 KB of RAM. Table 2 compares the proposed implementation with other works in terms of the execution timing. The work by [PERSON] et al. focused on high speed optimizations with the operand caching method and the sliding block doubling method. The proposed 256-bit multiplication and squaring operations are slower than those proposed by [PERSON] et al. by 67% and 72%, respectively, and the 768-bit multiplication and squaring operations are slower than [PERSON] et al. by 57% and 56%, respectively. The performance is reasonable as the 32-bit ARM Cortex-M4 microcontrollers support 168 MHz, which means that Curve25519 and SIKEp434 can be still performed within seconds. In terms of code size, our implementation only requires 584 bytes (260 bytes for multiplication and 324 bytes for squaring, respectively). This requires 75% and 10% of the code size used by [PERSON] et al., which directly saves 0.2-5 KB of code size for PKC implementations. In terms of long integer multiplication, previous works did not explore the implementations. This means that previous implementations cannot cover RSA implementations. For this reason,we evaluated the proposed implementations and compared the results to the estimated results by [PERSON] et al. For the RSA3072 encryption, the 3072-bit multiplication and squaring implementations based on [PERSON] et al. require about 54 KB and 38 KB, respectively. Furthermore, the fast RSA3072 decryption based on the Chinese-Remainder Theorem (CRT) needs 1536-bit multiplication and squaring implementations (13 KB for multiplication and 9 KB for squaring). For this reason, the unrolled RSA implementation cannot be used due to the code size. On the other hand, the proposed method still maintains a small code size (260 bytes for multiplication and 324 bytes for squaring). The results show that our method only provides all PKC options (i.e., ECC, RSA, and SIKE) on ARM Cortex-M4 microcontrollers. It is also interesting to compare parameterized implementations on other low-cost platforms (e.g., 8-bit AVR processors). Compared with previous parameterized implementations over the AVR processor [1], our implementation has several distinguishing features. In terms of the MAC algorithm, we introduced an optimized MAC method, which is specialized for the new UMAAL multiplier of target processor.