Optimizing Montgomery Arithmetic for RSA on Cortex-M0+ and Cortex-M3

What it is

This paper gives concrete implementation techniques for Montgomery multiplication/squaring on two specific ARM cores — Cortex-M0+ (no native widening multiply) and Cortex-M3 (widening multiply with operand-dependent latency) — applied to RSA-2048/3072 CRT private-key operations, using 15-bit limbs.

How it works

• M0+ (no widening multiply): uses a "wrapped sum" plus accumulated block quotients to recover exact carries without widening multiplication. The squaring schedule interleaves square and reduction columns so the full square is never materialized in a buffer, saving memory and cycles.
• M3 (has widening multiply): keeps the existing half-diagonal representation but doubles each buffer limb at the point it first enters Montgomery reduction, which removes a separate pass over the buffer that prior implementations needed.
• Both schedules come with derived accumulator bounds proving exact digit/carry recovery (i.e., no overflow correctness issues at these limb sizes).

Preconditions / Affected

Applies specifically to RSA-2048 and RSA-3072 CRT private-key operations (1024-bit and 1536-bit modular arithmetic, matching the CRT factors) on Cortex-M0+ and Cortex-M3 microcontrollers. Framed for cryptographic tokens that must retain RSA for legacy authentication compatibility rather than migrating to ECC/post-quantum.

What to do

The actionable content is the technique, not a drop-in patch:

• On M0+: implementers can swap in the wrapped-sum/block-quotient Montgomery kernel and the interleaved squaring schedule for a reported 12.60–13.11% reduction in Montgomery mul/square cycles and 12.59–12.80% reduction in warm CRT-RSA cycles, measured at both 1024-bit and 1536-bit operand widths — the gain holds across both sizes, not just one.
• On M3: the doubled-buffer-limb trick on top of existing half-diagonal code gives a smaller but real 2.12–3.08% squaring cycle reduction and 1.69–2.39% warm CRT cycle reduction — worth doing only as a low-effort patch to an existing half-diagonal M3 implementation, not a rewrite.
• The M3 Montgomery multiplication kernel also beats a reproduced NTT-based multiplication by 31.47% fewer cycles for 2048-bit operands (matched integers, canonical outputs) — relevant if someone was considering switching to NTT-based multiplication on M3 for this operand size.

Caveats

All figures are the authors' own cycle-count measurements against their own "blocked two-word" controls and their own NTT reproduction — no third-party benchmarks or independent reproduction are cited. Gains are asymmetric: substantial on M0+, marginal (2–3%) on M3, so the paper is most relevant to M0+-class deployments.