Up to $8k$8k-bit Modular Montgomery Multiplication in Residue Number Systems With Fast 16-bit Residue Channels

Hardware realization of public-key cryptosystems often entails Montgomery modular multiplication (MMM), which is more efficient in residue number systems (RNS). A large pool of co-prime moduli allows for higher number of dynamically changeable moduli-set pairs for the required base extension, leading to ultra-wide key-lengths to accommodate the indispensable resistance to differential power-analysis (DPA) attacks. The moduli are often of the form
${2^r} - {{\delta }}$
, where
$r$
denotes the width of residue channels. In a previous relevant RNS MMM design, with
$r\ = \ 64$
, probability of a successful DPA attack is less than
${2^{ - 66}}$
, where efficient arithmetic is obtained only for a limited set of moduli that are insufficient for key-lengths over 1024 bits. Here we propose a free-
${{\delta }}$
RNS MMM scheme, for up-to 8192-bit key-lengths and fast 16-bit residue channels, based on the proposed
${{\delta }}$
-independent modulo-(
${2^r} - {{\delta }}$
) adders and multipliers. Moreover, we propose an especial method for moduli selection that is required for base extension, leading to the same aforementioned DPA-resistance measure and much lower measures for key-lengths over 1024. The implementation results show
$82,69,44\ percent$
less RSA delay, for key-lengths
$512,1024,2048$
, respectively of the home designs versus the 512-bit main reference design, and more than
$5,100\ percent$
for
$4096,8192$
key-lengths, respectively, all per 512-bit encrypted messages.