International audience

In [1] the authors introduced the leak resistant arithmetic in RNS to randomize RSA modular exponentiation. This randomization is meant to protect implementations on embedded device from side channel analysis. We propose in this paper a lazy version of the approach of [1] in the case of right-to-left square-and-multiply exponentiation. We show that this saves roughly 30% of the computation when the randomization is done at each loop iteration. We also show that the level of randomization of the proposed approach is better than the one of [1] after a few number of loop iterations.

Copyright 2016 by SCITEPRESS - Science and Technology Publications, Lda. All rights reserved.Cryptographic operations performed on an embedded device are vulnerable to side channel analysis and particularly to differential and correlation power analysis. The basic protection against such attacks is to randomize the data all along the cryptographic computations. In this paper we present a modular multiplication algorithm which can be used for randomization. We show that we can use it to randomize the modular exponentiation of the RSA cryptosystem. The proposed randomization is free of computation and induces a level of randomization from 210 to 215 for practical RSA modulus size.

The main operation in RSA encryption/decryption is the modular exponentiation, which involves a long sequence of modular squarings and multiplications. In this paper, we propose to improve modular multiplications AB, AC which have a common operand. To reach this goal we modify the Montgomery modular multiplication in order to share common computations in AB and AC. We extend this idea to reduce the cost of multiple modular multiplications AB1,...,ABℓby the same operand A. We then take advantage of these improvements in the Montgomery-ladder and SPA resistant m-ary exponentiation algorithms. The complexity analysis shows that for an RSA modulus of size 2048 bits, the proposed improvements reduce the number of word operations (ADD and MUL) by 14% for the Montgomery-ladder and by 5%-8% for the m-ary exponentiations. Our implementations show a speed-up by 8%-14% for the Montgomery-ladder and by 1%-8% for the m-ary exponentiations for modulus of size 1024, 2048 and 4048 bits.

International audience

We present two new strategies for parallel implementation of scalar multiplication over elliptic curves. We first introduce a Montgomery-halving algorithm which is a variation of the original Montgomery-ladder for point multiplication. This Montgomery-halving can be run in parallel with the original Montgomery-ladder in order to concurrently compute part of the scalar multiplication. We also present two point thirding formulas in some subfamilies of curves E(F3m). We use these thirding formulas to implement scalar multiplication through (Third, Double)-and-add and (Third, Triple)-and-add parallel approaches. We also provide some implementation results of the presented parallel strategies which show a speed-up of 5-14 percent on an Intel Core i7 processor and a speed-up of 8-19 percent on a Qualcomm Snapdragon processor compared to non-parallelized approaches.

Some applications like cryptography involve a large number of multiplications of binary polynomial. In this paper, we consider two-, three-, and four-way methods for parallel implementation of binary polynomial multiplication. We propose optimized three- and four-way split formulas which reduce the space and time complexity of the best known methods. Moreover, we present a block recombination method which provides some further reduction in the space complexity of the considered two-, three-, and four-way split multipliers.

In this paper, we propose new schemes for subquadratic arithmetic complexity multiplication in binary fields using optimal normal bases. The schemes are based on a recently proposed method known as block recombination, which efficiently computes the sum of two products of Toeplitz matrices and vectors. Specifically, here we take advantage of some structural properties of the matrices and vectors involved in the formulation of field multiplication using optimal normal bases. This yields new space and time complexity results for corresponding bit parallel multipliers.

In this paper, we consider three-way split formulas for binary polynomial multiplication and Toeplitz matrix vector product (TMVP). We first recall the best known three-way split formulas for polynomial multiplication: the formulas with six recursive multiplications given by Sunar in a 2006 IEEE Transactions on Computers paper and the formula with five recursive multiplications proposed by Bernstein at CRYPTO 2009. Second, we propose a new set of three-way split formulas for polynomial multiplication that are an optimization of Sunar's formulas. Then, we present formulas with five recursive multiplications based on field extension. In addition, we extend the latter formulas to TMVP. We evaluate the space and delay complexities when computations are performed in parallel and provide a comparison with best known methods.

Computing the product of a Toeplitz matrix and a vector arises in various applications including cryptography. In this paper, we consider Toeplitz matrices and vectors with entries in $({\hbox{\rlap{I}\kern 2.0pt{\hbox{F}}}}_2)$. For improved efficiency in such computations, large Toeplitz matrices and vectors are recursively split and special formulas with subquadratic arithmetic complexity are applied. To this end, we first present a formula for the five-way splitting and then provide a generalization for the $(k)$-way splitting, where $(k)$ is an arbitrary integer. These formulas can be used to compute a Toeplitz matrix-vector product (TMVP) of size $(n)$ with an arithmetic complexity of $(O(n^{\log_k(k(k+1)/2)}))$.

In this paper, we present a new method for parallel binary finite field multiplication which results in subquadratic space complexity. The method is based on decomposing the building blocks of the Fan-Hasan subquadratic Toeplitz matrix-vector multiplier. We reduce the space complexity of their architecture by recombining the building blocks. In comparison to other similar schemes available in the literature, our proposal presents a better space complexity while having the same time complexity. We also show that block recombination can be used for efficient implementation of the GHASH function of Galois Counter Mode (GCM).

In the recent past, subquadratic space complexity multipliers have been proposed for binary fields defined by irreducible trinomials and some specific pentanomials. For such multipliers, alternative irreducible polynomials can also be used, in particular, nearly all one polynomials (NAOPs) seem to be better than pentanomials. For improved efficiency, multiplication modulo an NAOP is performed via modulo a quadrinomial whose degree is one more than that of the original NAOP. In this paper, we present a Toeplitz matrix-vector product based approach for multiplication modulo a quadrinomial. We obtain a fully parallel multiplier with a subquadratic space complexity. The Toeplitz matrix-vector product-based approach is also interesting in the design of sequential multipliers. We present two such multipliers that process a two-bit digit every clock cycle. Field-programmable gate-array implementations of the proposed sequential as well as fully parallel multipliers for the field size of 163 are also presented.

We study Dickson bases for binary field representation. Such a representation seems interesting when no optimal normal basis exists for the field. We express the product of two field elements as Toeplitz or Hankel matrix-vector products. This provides a parallel multiplier which is subquadratic in space and logarithmic in time. Using the matrix-vector formulation of the field multiplication, we also present sequential multiplier structures with linear space complexity.

This paper deals with binary field multiplication. We use the bivariate representation of binary field called Double Polynomial System (DPS) presented in . This concept generalizes the composite field representation to every finite field. As shown in , the main interest of DPS representation is that it enables to use Lagrange approach for multiplication, and in the best case, Fast Fourier Transform approach, which optimizes Lagrange approach. We use here a different strategy from to perform reduction, and we also propose in this paper, some new approaches for constructing DPS. We focus on DPS, which provides a simpler and more efficient method for coefficient reduction. This enables us to avoid a multiplication required in the Montgomery reduction approach of , and thus to improve the complexity of the DPS multiplier. The resulting algorithm proposed in the present paper is subquadratic in space O(n1.31) and logarithmic in time. The space complexity is 33 percent better than in and 18 percent faster. It is asymptotically more efficient than the best known method (specifiably more efficient than when n ≥ 3,000). Furthermore, our proposal is available for every n and not only for n a power of two or three.

In the recent past, subquadratic space complexity multipliers have been proposed for binary fields defined by irreducible trinomials and some specific pentanomials. For such multipliers, alternative irreducible polynomials can also be used, in particular, nearly all one polynomials (NAOPs) seem to be better than pentanomials (see [7]). For improved efficiency, multiplication modulo an NAOP is performed via modulo a quadrinomial whose degree is one more than that of the original NAOP. In this paper, we present a Toeplitz matrix-vector product based approach for multiplication modulo a quadrinomial. We obtain a fully parallel (nonsequential) multiplier with a subquadratic space complexity, which has the same order of space complexity as that of Fan and Hasan. The Toeplitz matrix-vector product based approach is also interesting in the design of sequential multipliers. In this paper, we present two such multipliers: one with bit serial output and the other bit parallel output.

In this paper, we propose a complete set of algorithms for the arithmetic operations in finite fields of prime medium characteristic. The elements of the fields IFpkare represented using the newly defined Lagrange representation, where polynomials are expressed using their values at sufficiently many points. Our multiplication algorithm, which uses a Montgomery approach, can be implemented in O(k) multiplications and O(k2log k) additions in the base field IFp. For the inversion, we propose a variant of the extended Euclidean GCD algorithm, where the inputs are given in the Lagrange representation. The Lagrange representation scheme and the arithmetic algorithms presented in the present work represent an interesting alternative for elliptic curve cryptography

We present a new multiplication algorithm for the implementation of elliptic curve cryptography (ECC) over the finite extension fields GF(p/sup k/) where p is a prime number greater than 2k. In the context of ECC we can assume that p is a 7-to-10-bit number, and easily find values for k which satisfy: p>2k, and for security reasons log/sub 2/(p)/spl times/k/spl sime/160. All the computations are performed within an alternate polynomial representation of the field elements which is directly obtained from the inputs. No conversion step is needed. We describe our algorithm in terms of matrix operations and point out some properties of the matrices that can be used to improve the design. The proposed algorithm is highly parallelizable and seems well adapted to hardware implementation of elliptic curve cryptosystems.