Search

Applications such as public-key cryptography are critically reliant on the speed of modular multiplication for their performance. This paper introduces a new block-based variant of Montgomery multiplication, the Block Product Scanning (BPS) method, which is particularly efficient using new 512-bit advanced vector instructions (AVX-512) on modern Intel processor families. Our parallel-multiplication approach also allows for squaring and sub-quadratic Karatsuba enhancements. We demonstrate $$1.9\,\times $$ 1.9 × improvement in decryption throughput in comparison with OpenSSL and $$1.5\,\times $$ 1.5 × improvement in modular exponentiation throughput compared to GMP-6.1.2 on an Intel Xeon CPU. In addition, we show $$1.4\,\times $$ 1.4 × improvement in decryption throughput in comparison with state-of-the-art vector implementations on many-core Knights Landing Xeon Phi hardware. Finally, we show how interleaving Chinese remainder theorem-based RSA calculations within our parallel BPS technique halves decryption latency while providing protection against fault-injection attacks.

Montgomery’s and Barrett’s modular multiplication algorithms are widely used in modular exponentiation algorithms, e.g. to compute RSA or ECC operations. While Montgomery’s multiplication algorithm has been studied extensively in the literature and many side-channel attacks have been detected, to our best knowledge no thorough analysis exists for Barrett’s multiplication algorithm. This article closes this gap. For both Montgomery’s and Barrett’s multiplication algorithm, differences of the execution times are caused by conditional integer subtractions, so-called extra reductions. Barrett’s multiplication algorithm allows even two extra reductions, and this feature increases the mathematical difficulties significantly. We formulate and analyse a two-dimensional Markov process, from which we deduce relevant stochastic properties of Barrett’s multiplication algorithm within modular exponentiation algorithms. This allows to transfer the timing attacks and local timing attacks (where a second side-channel attack exhibits the execution times of the particular modular squarings and multiplications) on Montgomery’s multiplication algorithm to attacks on Barrett’s algorithm. However, there are also differences. Barrett’s multiplication algorithm requires additional attack substeps, and the attack efficiency is much more sensitive to variations of the parameters. We treat timing attacks on RSA with CRT, on RSA without CRT, and on Diffie–Hellman, as well as local timing attacks against these algorithms in the presence of basis blinding. Experiments confirm our theoretical results.

The scatter-gather technique is a commonly implemented approach to prevent cache-based timing attacks. In this paper we show that scatter-gather is not constant time. We implement a cache timing attack against the scatter-gather implementation used in the modular exponentiation routine in OpenSSL version 1.0.2f. Our attack exploits cache-bank conflicts on the Sandy Bridge microarchitecture. We have tested the attack on an Intel Xeon E5-2430 processor. For 4096-bit RSA our attack can fully recover the private key after observing 16,000 decryptions.

A series of algorithms for evaluation of multi-exponentiation are proposed based on the binary greatest common divisor algorithm. The proposed algorithms are inversion free and have the capability to evaluate double or multi-exponentiation with non-fixed base numbers and exponents. They can also be employed in developing side-channel countermeasures. For n-bit double and triple exponentiation, they achieve the average complexity of 1.53n and 1.75n multiplications (including squarings), respectively. The proposed algorithms can be very useful for the implementation of many public-key cryptosystems on small devices with limited memory space, e.g., smart cards.

The significant cost of RSA computations affects the efficiency and responsiveness of SSL/TLS servers, and therefore software implementations of RSA are an important target for optimization. To this end, we study here efficient software implementations of modular exponentiation, which are also protected against software side channel analyses. We target superior performance for the ubiquitous ×86_64 architectures, used in most server platforms. The paper proposes optimizations in several directions: the Montgomery multiplications primitives, the w-ary modular exponentiation flow, and reduced cost of side channel mitigation. For a comparison baseline, we use the current OpenSSL version, 1.0.0e. Our implementation—called “RSAZ”—is more than 1.6 times faster than OpenSSL for both 1,024 and 2,048-bit keys, on the previous generation 2010 Intel® Core™ processors and on the 2nd generation Intel® Core™ processors. The RSAZ code was contributed to OpenSSL as a patch, and improvements proposed in an earlier version of this paper have already been incorporated into the future OpenSSL version.

Straightforward implementations of binary exponentiation algorithms make the cryptographic system vulnerable to side-channel attacks; specifically, to simple power analysis (SPA) attacks. Solutions proposed so far introduce a considerable performance penalty. In this paper, we present a new method that implements an SPA-resistant binary exponentiation exhibiting optimal execution time at the cost of a small amount of storage—\({O(\sqrt{\ell})}\), where l is the bit length of the exponent. The technique is optimal in the sense that it adds SPA-resistance to an underlying binary exponentiation algorithm while introducing zero computational overhead. Furthermore, we show that for practical applications, the same optimal execution time can be achieved with much less storage space, without noticeably sacrificing security or any other aspect of the cryptosystem’s performance. We also discuss the possibility of our method being implemented in a way that a certain level of resistance against differential power analysis may be obtained.