MODULAR EXPONENTIATION WITH PARTITIONED AND SCATTERED STORAGE OF MONTGOMERY MULTIPLICATION RESULTS

摘要

Embodiments of techniques and systems for side-channel-protected modular exponentiation are described. In embodiments, during a modular exponentiation calculation, Montgomery Multiplication ("MM") results are produced. These MM results are scattered through a table for storage, such that storage of the values may not lead to discovery of a secret exponent value by a spy process through a side-channel attack. The scattering may be performed in order to reduce a number of per-result memory operations performed during each MM result storage or retrieval. In embodiments, a window size of 4 may be used in the modular exponentiation, along with partitioning of the MM result into 32-bit partition values which are scattered with offsets of 64-bytes. In embodiments, while use of a window size of 4 may result in additional MM calculations during modular exponentiation than other window sizes, the reduction in memory operations may provide a positive performance offset.