Modular exponentiation with partitioned and scattered storage of Montgomery Multiplication results

#This application relates to the technical field of data processing, more specifically to modular exponentiation with partitioned and scattered storage of Montgomery Multiplication results.

#The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure. Unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in the present disclosure and are not admitted to be prior art by inclusion in this section.

#Many cryptographic operations, such as the Rivest, Shamir and Adleman (“RSA”) cryptographic process, may rely on one or more modular exponentiations. A modular exponentiation may include operations to determine a value for ax mod m for input values a, x, and m. In various techniques, a “windowed” exponentiation process may be performed based on a “window size” value w. In such a w-ary modular exponentiation, a loop may iterate through exponent bits in groups of w bits during calculation of an exponentiation result.

#Embodiments of the present invention will be described by way of exemplary embodiments, but not limitations, illustrated in the accompanying drawings in which like references denote similar elements, and in which:

#FIG. 1 is block diagram illustrating an example modular exponentiation arrangement with Montgomery Multiplication storing and gathering modules, in accordance with embodiments of the present disclosure;

#FIG. 2 is a block diagram illustrating an example of scattered Montgomery Multiplication results, in accordance with various embodiments;

#Methods, apparatuses, and storage media associated with side-channel-protected windowed exponentiation are disclosed herein. In various embodiments, a computer-implemented method may include initializing a table, by a computing device, in a memory of the computing device, the table having a size. The method may also include performing, by the computing device, a first plurality of Montgomery Multiplications. The method may also include storing, by the computing device, results of the first plurality of Montgomery Multiplications into the table, the storing of each result into the table. The storing may include partitioning the particular result into multiple partition values and storing the partition values of the particular result scattered across the table. The method may also include performing, by the computing device, a second plurality of Montgomery Multiplications using the stored partition values of the results of the first plurality of Montgomery Multiplications scattered in the table. Initializing the table may include selecting the size of the table to at least reduce a number of memory accesses performed during retrieval of the stored partition values of the results of the first plurality of Montgomery Multiplications scattered in the table during performance of the second plurality of Montgomery Multiplications.

#In various embodiments, an apparatus may be equipped to practice one or more of the methods described herein. In various embodiments, the apparatus may include a computer-readable memory and one or more computer processors coupled to the memory. the apparatus may also include a Montgomery Multiplication result storing module configured to be operated by the one or more computer processors to store partition values of Montgomery Multiplication results scattered across a table in the memory. The apparatus may also include a Montgomery Multiplication result gathering module configured to be operated by the one or more computer processors to reconstruct Montgomery Multiplication results from corresponding stored partition values scattered across the table. The apparatus may also include an initialization routine to be operated by the one or more computer processors, and configured to initialize the table. The initialization module may be configured to initialize the table in a manner such that memory operations performed by the Montgomery Multiplication result gathering module during reconstruction of Montgomery Multiplication results based on corresponding partition values stored and scattered across the table by the Montgomery Multiplication result storing module are reduced.

#In various embodiments one or more non-transitory computer-readable media may include instructions that, in response to execution by a computing device, cause the computing device to perform one or more operations of various methods described herein.