Search

This paper presents a secured computation of modular exponentiation to resist higher-order differential power analysis (HODPA) attacks in asymmetric cryptosystems like RSA. HODPA attacks can be resisted by segmenting secret sensitive data and its intermediate values into multiple shares. In modular exponentiation-based cryptosystems, the exponent plays a significant part in the secret key. We have used inner product with differential evolution algorithm to segment the exponent into multiple shares. Using entropy-based nearest neighbor algorithm, we have randomly computed independent modular exponentiation to resist SPA and DPA attacks. Analysis was done on 1024, 1536 and 2048 bit RSA. With a pre-computation complexity, the proposed approach can provide significant resistance to SPA, DPA and HODPA attacks against modular exponentiation-based cryptosystems.

This paper presents a randomized Montgomery Powering Ladder Modular Exponentiation (RMPLME) scheme for side channel attacks (SCA) resistant Rivest-Shamir-Adleman (RSA) and its leakage resilience analysis. This method randomizes the computation time of square-and-multiply operations for each exponent bit of the Montgomery Powering Ladder (MPL) based RSA exponentiation using various radices (Radix – 2, 22, and 24) based Montgomery Modular multipliers (MMM) randomly. The randomized computations of RMPLME generates non-uniform timing channels information and power traces thus protecting against SCA. In this work, we have developed and implemented a) an unmasked right-to-left Montgomery Modular Exponentiation (R-L MME), b) MPL exponentiation and c) the proposed RMPLME schemes for RSA decryption. All the three realizations have been assessed for side channel leakage using Welch’s t-test and analyzed for secured realizations based on degree of side channel information leakage. RMPLME scheme shows the least side-channel leakage and resilient against SPA, DPA, C-Safe Error, CPA and Timing Attacks.

RSA (Rivest-Shamir-Adleman) is a widely known and popular public-key cryptosystem used in many security applications. The main mathematical function in RSA is Modular Exponentiation, which is demanding in terms of speed and area. Due to repetitive Modular Multiplications involved in Exponentiation function, it becomes time-consuming, especially for large operands. To accelerate the RSA Encryption/Decryption operation, a reduction in number of Modular Multiplications as well as reduction in clock-cycles to perform one Modular Multiplication operation is required. The main objective of this paper is to develop high-speed, area-efficient hardware Montgomery Modular Exponentiation architecture for RSA Encryption/Decryption operations by using Lookup-Table (LUT) based high-radix Montgomery Modular Multiplier. In this paper, we present a hardware architecture designed to implement Right-to-Left (R-L) Montgomery Modular Exponentiation using a lookup-table based Radix-16 Modular Multiplication with Montgomery reduction. The proposed architecture provides tremendous improvement by reducing the number of clock cycles for one Modular Multiplication from n (operand bit-length) to n/4 cycles. With our implementation results, for Montgomery Modular Exponentiation with Radix-16 lookup-table based Montgomery Multiplier architecture, we are able to achieve computational delay of 6.35ms, 43.16ms, 320.4ms for computing 1024/ 2048/ 4096 bits of Modular Exponentiation, respectively. We were able to achieve significant improvement in terms of time and Time-Area (TA).

This paper presents an approach to resist modular exponentiation-based cryptosystems like RSA from higher-order DPA attacks. The best way to prevent higher-order DPA attacks is by splitting the sensitive data into independent shares and execute them individually. We have incorporated the concept of inner product to split the large exponent or secret key in modular exponentiation into multiple shares. With these independent shares, individual modular exponentiation has been computed using multiply-always binary method. These shares have also been arithmetically blinded with a 32-bit blinding factor prior to computation. The entire analysis has been executed in RSA of sizes: 1024 bits, 1536 bits and 2048 bits. The results show that the proposed work can provide significant resistance to SPA, DPA and higher-order DPA attacks on modular exponentiation-based cryptosystems.

In this article we formalize in Mizar the maximum number of steps taken by some number theoretical algorithms, “right–to–left binary algorithm” for modular exponentiation and “Euclidean algorithm” For any natural numbers a, b, n, “right–to–left binary algorithm” can calculate the natural number, see (Def. 2), AlgoBPow(a, n,m) := ab mod n and for any integers a, b, “Euclidean algorithm” can calculate the non negative integer gcd(a, b). W have not formalized computational complexity of algorithms yet, though we had already formalize the “Euclidean algorithm” in. For “right-to-left binary algorithm”, we formalize the theorem, which says that the required number of the modular squares and modular products in this algorithms are 1+blog2 nc and for “Euclidean algorithm”, we formalize the Lam´e's theorem, which says the required number of the divisions in this algorithm is at most 5 log10 min(|a|, |b|). Our aim is to support the implementation of number theoretic tools and evaluating computational complexities of algorithms to prove the security of cryptographic systems., Article, FORMALIZED MATHEMATICS 27(1) : 87-91(2019)

Modular multiplication is a key operation in RSA cryptosystems. Modular multipliers can be realized using Montgomery algorithm. Montgomery algorithm employing carry save adders makes modular multiplication suitable and efficient. Montgomery modular multiplication can be carried out in two ways. All the operands are kept in carry save form in one of the ways. The input and output are kept in binary form, and intermediate operands are kept in carry save form in the other way which requires an efficient format converter. This paper proposes a fast and high-throughput Montgomery modular multiplier which employs an efficient format conversion method. Format conversion is carried out through a format conversion unit which consists of a carry look-ahead unit and multiplexer unit. In addition, this multiplier merges two iterations, which reduces the number of clock cycles significantly. Merger of iteration requires integer multiples of inputs which is computed using the same format converter. Critical path delay of the multiplier is minimized by multiplying one of the inputs by four which simplifies necessary intermediate calculations. The total time required for one complete multiplication is significantly minimized due to reduction in required number of clock cycles with optimum critical path delay. Experimental results show that the proposed multiplier achieves significant speed and throughput improvement as compared to previous designs.

Modular multiplication is used in a wide range of applications. Most of the existing modular multiplication algorithms in the literature often focus on large size moduli. However, those large moduli oriented modular multiplication solutions are also used to implement modular arithmetic for applications requiring modular arithmetic on moduli of size inferior to a word size i.e., 32/64bits. As it happens, a large majority of applications are using word size modular arithmetic. In this work, we propose a new modular multiplication designed to be computed on one word size only. For word size moduli, in a large majority of instances, our solution outperforms other existing solutions including generalist solutions like Montgomery's and Barrett's modular multiplication as well as classes of moduli like Mersenne, Pseudo-Mersenne, Montgomery-Friendly and Generalized Mersenne.

With the advancements of communication technology, security threats are also increasing. RSA is a robust cryptosystem to protect classified information. The efficiency of RSA cryptosystem depends on the efficient execution of Montgomery modular multiplication. A low latency and throughput efficient Montgomery modular multiplier is proposed in this paper. The input and final output of this multiplier are binary, but intermediate input and output are carry-saved i.e. sum and carry bits are stored in separate registers. Sum and carry bits are obtained from the addition of operands using carry-save adder (CSA). Montgomery multipliers require quotient calculation for subsequent iteration. The proposed multiplier computes two subsequent quotients in parallel with carry-save addition. Output of carry-save addition is right shifted by two bits to obtain the next-to-next intermediate output. This calculation also requires integer multiples of the inputs. Computation of next output is skipped. Format conversion of output is performed using a carry look-ahead unit (CLU). CLU along with one cycle of carry save addition is also utilized for pre-computation of integer multiples of inputs. The proposed multiplier is implemented on NEXYS4DDR and VIRTEX VII FPGA and the following result is obtained. NEXYS4DDR: Area (LUT + REG): 38903, Delay: 5.84 ns, Cycles: 1158, Latency: 6.76 µs, Throughput: 302.96 Mbps. VIRTEX VII: Area (LUT): 16447, Delay: 1.62 ns, Cycles: 1158, Latency: 1.88 µs, Throughput: 1089.4 Mbps. Results verify the improved area, latency and throughput performance of the proposed work.

This chapter discusses the better performing approaches for modular exponential techniques that are adaptable by the different architectures of PKC. The importance of PKC in the field of information security including militarily level security is decisive. The security of these PKCs depends upon their complex arithmetic problems (e.g. IFP and DLP) which include modular exponentiation as a critical operation. Modular exponentiation is an expensive operation, that is comprised of a series of modular multiplications. The overall performance of PKC is affected by the efficient implementation of modular exponentiation. There are different ways of improving the performance of modular exponentiation, either reduce the modular multiplication operation’s internal architecture to reduce the latency, or reduce the number of modular multiplications required for the computation of modular exponentiation. This chapter discusses the techniques of reducing the number of the required modular multiplications by Bit Forwarding (BFW) techniques and how they can be implemented. The Montgomery multiplication algorithm is modified according to the requirements of BFW techniques. There are two varieties of Montgomery multiplication discussed

The motivation of exploring a better way of computing modular multiplication is driven by its application in public key cryptography, especially the RSA algorithm and Diffie–Hellman algorithm. These algorithms are very much important to attain better information security over a public network. Cryptosystems have an important step of key exchange for which confidentiality is achieved by modular exponentiation. The modular exponentiation problem is further divided into series of modular multiplications with the help of various methods.

This chapter discusses the implementation of modular Exponentiation in Dual-core with High Radix Multiplication (DCHRM), for further reduction of clock cycles and better frequency. The main mathematical operation in maximum public-key cryptography (PKC) (William 2006) is a Modular Exponentiation (ME). The ME evaluation is done by performing a series of modular multiplications (MMs). As ME is a core operation thus, the competent implementation of PKC is directly proportional to the efficient performance of ME. similarly efficient implementation of ME is directly proportional to the better performing MM. In order to obtain efficient computation, high-radix implementation is preferable. As increment in radix is done, the number of digits to be executed in each iteration is decreased. Thus, reduces the required number of the clock cycles but, increases the frequency and additional space. This chapter also explores the conventional right-to-left ME approach for DCRSAP

This paper discusses and demonstrates the construction of a quantum modular exponentiation circuit in the Qiskit simulator for use in Shor's Algorithm for integer factorization problem (IFP), which is deemed to be able to crack RSA cryptosystems when a large-qubit quantum computer exists. We base our implementation on Vedral, Barenco, and Ekert (VBE) proposal of quantum modular exponentiation, one of the firsts to explicitly provide the aforementioned circuit. Furthermore, we present an example simulation of how to construct a 7xmod 15 circuit in a step-by-step manner, giving clear and detailed information and consideration that currently not provided in the existing literature, and present the whole circuit for use in Shor's Algorithm. Our present simulation shows that the 4-bit VBE quantum modular exponentiation circuit can be constructed, simulated, and measured in Qiskit, while the Shor's Algorithm incorporating this VBE approach itself can be constructed but not yet simulated due to an overly large number of QASM instructions.

Modular exponentiation is fundamental in computer arithmetic and is widely applied in cryptography such as ElGamal cryptography, Diffie-Hellman key exchange protocol, and RSA cryptography. Implementation of modular exponentiation in residue number system leads to high parallelism in computation, and has been applied in many hardware architectures. While most RNS based architectures utilizes RNS Montgomery algorithm with two residue number systems, the recent modular multiplication algorithm with sum-residues performs modular reduction in only one residue number system with about the same parallelism. In this work, it is shown that high-performance modular exponentiation and RSA cryptography can be implemented in RNS. Both the algorithm and architecture are improved to achieve high performance with extra area overheads, where a 1024-bit modular exponentiation can be completed in 0.567 ms in Xilinx XC6VLX195t-3 platform, costing 26,489 slices, 87,357 LUTs, 363 dedicated multipilers of $18\times 18$ bits, and 65 Block RAMs.

We analyze the security of RSA prime generation implemented on embedded devices by a practical power analysis attack. Unlike previous differential power analysis-based attack on primality tests of RSA prime generation exploiting the deterministic relationship among multiple prime candidates manipulated by consecutive primality tests, we propose a collision-based power analysis attack on the Miller-Rabin test for a single prime candidate which can recover the secret prime with a single attempt by exploiting collision characteristics of simple power analysis resistant modular exponentiation algorithms. Hence, our attack does not require the incremental prime search assumption and is applicable when countermeasures against previous attacks are deployed since it also does not require the assumption of trial divisions with small primes on prime candidates. For a realistic setting, where five 512-bit modular exponentiations are operated on an ARM Cortex-M4 microcontroller as recommended by FIPS 186-4 standard, we successfully recover the secret exponent to an extent that a feasible exhaustive search is needed for the full recovery of the secret prime. This is a first practical result of recovering a full secret of modular exponentiation which manipulates 512-bit RSA primitives with collision-based power analysis in a single attempt, where the previous attack demonstrates the result for 192-bit ECC primitive implementations. We also present a countermeasure against our attack which requires only one additional modular subtraction for the loop of square-and-multiply-always exponentiation algorithm. An experimental result for the effectiveness of our proposed countermeasure is presented.

This paper presents the implementation of the ELGamal cryptoalgorithm for information flows encryption / decryption, which is based on the application of the vector-modular method of modular exponentiation and multiplication. This allows us to replace the complex operation of the modular exponentiation with multiplication and the last one with addition that increases the speed of the cryptosystem. In accordance with this, the application of the vector-modular method allows us to reduce the modular exponentiation and multiplication temporal complexity in comparison with the classical one.

We present an efficient algorithm for batch modular exponentiation which improves upon the previous generalized intersection method with respect to the cost of multiplications. The improvement is achieved by adopting an extended common-multiplicand multiplication technique that efficiently computes more than two multiplications at once. Our algorithm shows a better time-memory tradeoff compared to the previous generalized intersection method. We analyze the cost of multiplications and storage requirement, and show how to choose optimal algorithm parameters that minimize the cost of multiplications.

This study presents an approach to compute randomised modular exponentiation through non-uniform exponent partitioning. The exponent has been first partitioned into multiple parts and then shuffled by Fisher Yates method. Thereafter, every partition randomly computes modular exponentiation followed by a final modulo operation to generate the desired result. The shuffling has been introduced to randomise the execution order of individual modular exponentiation. This work is implemented in Rivest-Shamir-Adleman (RSA) and Chinese remainder theorem RSA as they are modular exponentiation based public key cryptosystems. The results have been analysed during decryption with different key sizes. The results indicate that the proposed work can generate non-uniform partitions of the exponent which could not be easily anticipated even in multiple iterations. Also, the shuffling method could completely randomise the execution order of modular exponentiation operations. With non-uniform exponent partitions and randomised modular exponentiation, the proposed work could challenge all the variances of power analysis attacks.

We present a secure variant of modular exponentiation implemented in RSA and CRT-RSA to resist power analysis attacks. For speeding up the computation, modular exponentiation is generally done through “squaring and multiplication” according to the binary bit of the secret exponent. This is popularly known as straight forward method. However, such computation leaves behind distinct traces of power consumption leading to power analysis attacks. These attacks were so powerful that they could reveal the secret exponent or the key challenging the vulnerability of any cryptosystem. In this work, we have enhanced the security of modular exponentiation by first randomizing the exponent or the secret key and then executing comparative bitwise squaring and multiplication. Our proposed work could be implemented in left-to-right or right-to-left without any modification of the algorithm which removed the dependency of “squaring and multiplication” on the bits of the key. As RSA decryption has more security privilege, we have implemented our proposed work only while decrypting the message. However, it can be used during encryption too. The randomized key, bit-independent squaring–multiplication and comparative modular exponentiation would generate non-uniform and random power traces resisting it from power analysis attacks.

International audience; In a series of recent articles (from 2011 to 2017), Schindler et al. show that exponent/scalar blinding is not as effective a countermeasure as expected against side-channel attacks targeting RSA modular exponentiation and ECC scalar multiplication. Precisely, these works demonstrate that if an attacker is able to retrieve many randomizations of the same secret, this secret can be fully recovered even when a signi-ficative proportion of the blinded secret bits are erroneous. With a focus on ECC, this paper improves the best results of Schindler et al. in both the generic case of random-order elliptic curves and the specific case of structured-order elliptic curves. Our results show that larger blinding material and higher error rates can be successfully handled by an attacker in practice. This study also opens new directions in this line of work by the proposal of a three-steps attack process that isolates the attack critical path (in terms of complexity and success rate) and hence eases the development of future solutions.

Diffie-Hellman and RSA encryption/decryption involve computationally intensive cryptographic operations such as modular exponentiation. Computing modular exponentiation using appropriate pre-computed pairs of bases and exponents was first proposed by Boyko et al. In this paper, we present a reconfigurable architecture for pre-computation methods to compute modular exponentiation and thereby speeding up RSA and Diffie-Hellman like protocols. We choose Diffie-Hellman key pair (a, ga mod p) to illustrate the efficiency of Boyko et al’s scheme in hardware architecture that stores pre-computed values a i and corresponding ga i in individual block RAM. We use a Pseudo-random number generator (PRNG) to randomly choose a i values that are added and corresponding ga i values are multiplied using modular multiplier to arrive at a new pair (a, ga mod p). Further, we present the advantage of using Montgomery and interleaved methods for batch multiplication to optimise time and area. We show that a 1024-bit modular exponentiation can be performed in less than 73μs at a clock rate of 200MHz on a Xilinx Virtex 7 FPGA.

International audience; Digital Signature Algorithm (DSA) (resp. ECDSA) involves modular exponentiation (resp. scalar multiplication) of a public and known base by a random one-time exponent. In order to speed-up this operation, well-known methods take advantage of the memorization of base powers (resp. base multiples). Best approaches are the Fixed-base Radix-R method and the Fixed-base Comb method. In this paper we present a new approach for storage/online computation trade-off, by using a multiplicative splitting of the digits of the exponent radix-R representation. We adapt classical algorithms for modular exponentiation and scalar multiplication in order to take advantage of the proposed exponent recoding. An analysis of the complexity for practical size shows that our proposed approach involves a lower storage for a given level of online computation. This is confirmed by implementation results showing significant memory saving, up to 3 times for the largest NIST standardized key sizes, compared to the state of the art approaches.

Recently, an identity-based quadratic exponentiation randomized cryptosystem scheme using the discrete logarithm problem and the integer factorization problem has been developed. Their contribution lies in that they initiated an idea to create the identity-based cryptographic scheme without bilinear pair. This scheme can achieve the security goal of protecting data and prevent the adversary from snooping the encrypted data, and finding the secrete keys. In this paper, we have proposed some modification in setup phase using floor function and super-increasing sequence, and modified the encryption and decryption process in the identity-based quadratic exponentiation randomized cryptographic scheme. We also discuss how to enhance the security of proposed scheme and processing cost of the proposed scheme.

The times of multiplication for encryption and decryption of cryptosystem is primarily determined by implementation efficiency of the modular exponentiation of (mod m). The most frequently used among standard modular exponentiation methods is a standard binary method, of which n-ary() is most popular. The n-ary() is a square-and-multiply method which partitions $b

—Today's rapid progress in the physical implementation of quantum computers demands scalable synthesis methods to map practical logic designs to quantum architectures. There exist many quantum algorithms which use classical functions with superposition of states. Motivated by recent trends, in this paper, we show the design of quantum circuit to perform modular exponentiation functions using two different approaches. In the design phase, first we generate quantum circuit from a verilog implementation of exponentiation functions using synthesis tools and then apply two different Quantum Error Correction techniques. Finally the circuit is further optimized using the Linear Nearest Neighbor (LNN) Property. We demonstrate the effectiveness of our approach by generating a set of networks for the reversible modular exponentiation function for a set of input values. At the end of the work, we have summarized the obtained results, where a cost analysis over our developed approaches has been made. Experimental results show that depending on the choice of different QECC methods the performance figures can vary by up to 11%, 10%, 8% in T-count, number of qubits, number of gates respectively.

Modular exponentiation represents a significant workload for public key cryptosystems. Examples include not only the classical RSA, DSA, and DH algorithms, but also the partially homomorphic Paillier encryption. As a result, efficient software implementations of modular exponentiation are an important target for optimization. This paper studies methods for using Intel’s forthcoming AVX512IFMA instructions in order to speed up modular (Montgomery) squaring, which dominates the cost of the exponentiation. We further show how a minor tweak in the architectural definition of AVX512IFMA has the potential to further speed up modular squaring.

Modular exponentiation is one of the core operations in most of the public-key cryptosystems. It consists of a sequence of modular multiplications. The performance of public-key cryptographic transformations is strongly influenced by the competent implementation of modular exponentiation and modular multiplication. This paper presents the hardware implementation of modular exponentiation on two processor cores. Montgomery multiplication method is modified according to the needs of dual-core implementation to improve the core utilization. It is implemented with different radices ranging from \(2^2\) to \(2^{32}\). The performance of the proposed design is analyzed and compared with the existing techniques in terms of number of clock cycles, throughput, power, and area. The proposed design has been developed using Verilog and synthesized using Xilinx-14.6 ISE for usage in FPGA, and the same has been synthesized using Cadence for ASIC. But here the results are presented based on FPGA.

The aim of this paper is to present the improvement of Chinese Remainder Theorem (CRT) to speed up RSA’s decryption process by changing sub exponents and transforming ciphertext in another domain. Although applying CRT with RSA, called CRT-RSA, can be chosen to decrease time in decryption side, computing modular exponentiation still consumes enormous time whenever sub exponents are large. In addition, the proposed method suits to apply with high sub exponents of CRT-RSA because the new sub exponents are smaller. On the other hand, both of them become larger when CRT-RSA’s exponents are small. Therefore, the proposed method cannot be chosen to replace CRT-RSA but it is one of two choices for the implementation. If sub exponents are small, CRTRSA is a better choice to speed up RSA’s decryption. Nevertheless, the proposed method should be selected when sub exponents are large. The experimental results show that the proposed method can finish the process faster than CRT-RSA for both of key generation process and decryption process whenever sub exponents are large. Furthermore, in decryption side, the proposed method is faster than CRT-RSA about 20 – 40%.

This paper presents a case for intra-module multiple clock domain design in FPGAs using a high-radix Montgomery multiplier. Our design aims at simple hardware description from algorithm description, avoiding the decrease of clock rate by a long combinatorial path. According to our evaluation with 1024-bit modular exponentiation units, the calculation time reduced by 1.0% on average. The additional logic units for the proposed design was 2,556 LUTs and 1,043 flip-flops per multiplier at a maximum.

This paper presents a new approach to integer multiple precision (MP) modular exponentiation, using double-precision floating point (DPF) operations, that is suitable for GPU implementation. We show speedups ranging from 20 % to 34 % over the best prior G PU times for sizes corresponding to common RSA cryptographic operations (2048 to 4096 bits). Three techniques are described. First, by adding 2104to the high half of the product, and 252 to the low half, we set the implicit leading 1 in the DPF mantissa so that the full 52 explicit bits are available for each half of the 104-bit products of samples. Second, the DPF values are cast bitwise to 64-bit integers for adding the column sums to get the MP result. Normally the cast would require masking off the exponents, but because they are constant, we can include them in the column sums and correct just once for their total. Third, by initializing the column sums with the appropriate negative value to compensate for the exponent sums, no corrective subtraction is needed. Our implementation on an NVIDIA GTX Titan Black GPU achieves between 132.5K and 161.9K modular exponentiations per second of size 1024 bits, with latencies ranging from 21.7 ms to 17.8 ms, making it practical for online RSA applications. Proportional results are shown for 1536 and 2048 bits. The implementation is so efficient that its maximum sustained performance is actually bounded by the thermal limit of the GPU.

Modular multiplication is initial operation for modular exponention to generate public key cryptography schemes. The modular exponentiation can be defined by repeated operation of modular multiplication. The performance of any public key cryptography system like RSA, ECC, is determined by the efficient implementation of the modular multiplication. Encryption/Decryption processes are time consuming so it is necessary to reduce time requirement and Area-Delay Product (ADP) of modular multiplications operation. To speed up the computation, Montgomery modular multiplication algorithm is used; this algorithm does all the process without using a trial division. Precomputation of the quotient is used to reduce the ADP (Area Delay Product). We proposed an algorithm which reduces ADP and speed up all operation. This algorithm supports up to 512-bits. Our proposed algorithm reduces ADP (area delay product) 28.18% and 42.94% compared to normal and fast Montgomery algorithm respectively.

With the advancement in communication systems, security is a prime concern which is offered by cryptosystems Modular arithmetic is core operation in most of the cryptosystems. Many cryptosystems including RSA, DSA and ECC systems requires modular multiplication for private key generation. It uses modular exponentiation of large numbers to encrypt data, which is a slow process due to repeated modular multiplications. The efficiency of cryptography systems practically depend on how fast the modular multiplication is done, since these are at the base of computation. Many hardware and software implementations for faster modular multiplication have been proposed, Montgomery Multiplication Algorithm is recognized as the most efficient among these. This paper presents a 32-bit implementation of a Faster Montgomery algorithm for performing modular multiplication. The algorithm is based on the method proposed by Montgomery for modular multiplication and is complementary to the available techniques. Simulation shows that our design performs faster in terms of clock frequency while it requires lower area.

Finite field arithmetic operations have been traditionally used in different applications ranging from error control coding to cryptographic computations. Among these computations are normal basis multiplications and exponentiations which are utilized in efficient applications due to their advantageous characteristics and the fact that squaring (and subsequent powering by two) of elements can be obtained with no hardware complexity. In this paper, we present 2-D decomposition systolic-oriented algorithms to develop systolic structures for digit-level Gaussian normal basis multiplication and exponentiation over $ {GF}({2}^{m})$ . The proposed high-performance architectures are suitable for a number of applications, e.g., architectures for elliptic curve Diffie–Hellman key agreement scheme in cryptography. The results of the benchmark of efficiency, performance, and implementation metrics of such architectures through a 65-nm application-specific integrated circuit platform confirm high-performance structures for the multiplication and exponentiation architectures presented in this paper are suitable for high-speed architectures, including cryptographic applications.

Modular exponentiation with a large modulus and exponent is a fundamental operation in many public-key cryptosystems. This operation is usually accomplished by repeating modular multiplications. Montgomery modular multiplication has been widely used to relax the quotient determination. The carry–save adder has been employed to reduce the critical path. This paper presents and evaluates a new and efficient Montgomery modular multiplication architecture based on a new digit serial computation. The proposed architecture relaxes the high-radix partial multiplication to a binary multiplication. It also performs several multiplications of consecutive zero bits in one clock cycle instead of several clock cycles. Moreover, the right-to-left and left-to-right modular exponentiation architectures have been modified to use the proposed modular multiplication architecture as its structural unit. We provide the implementation results on a Xilinx Virtex 5 FPGA demonstrating that the total computation time and throughput rate of the proposed architectures outperform most results so far in the literatures.

Modular exponentiation is an important operation in public-key cryptography. The Common-Multiplicand-Multiplication (CMM) modular exponentiation is an efficient exponentiation algorithm. This paper presents a novel method for speeding up the CMM modular exponentiation algorithm based on a Modified Montgomery Modular Multiplication (M4) algorithm. The M4 algorithm uses a new multi bit scan-multi bit shift technique by employing a modified encoding algorithm. In the M4 algorithm, three operations (the zero chain multiplication, the required additions and the nonzero digit multiplication) are relaxed to a multi bit shift and one binary addition in only one clock cycle. Our computational complexity analysis shows that the average number of required multiplication steps (clock cycles) is considerably reduced in comparison with other CMM modular exponentiation algorithms.

This paper improves the quotient-pipelined high radix scalable Montgomery modular multiplier by processing w-bit and k-bit words in carry save form instead of some (w + k)-bit length operands. It directly reduces both the critical path and the area overhead of the original processing elements. Then based on this improved high-radix scalable Montgomery modular multiplier, we propose an efficient hardware architecture for RSA decryption with Chinese Remainder Theorem. With simple configuration logics, the hardware unit works in three modes: (1) scalable modular reduction for precomputation, (2) scalable Montgomery modular multiplication for modular exponentiation, where an approximation method is developed to reduce the expanded result below the modulus, and (3) scalable multiplication for post-processing. Hardware implementation shows that the proposed architecture is optimal with reference to the literature in terms of speed, area, and frequency. A 4096-bit RSA decryption in XC2V6000-6 FPGA can be completed in 11.05 ms with 14041 slices/17409 LUTs, 128 16 × 16 multipliers, and 70 kbits of block RAMs. Finally, by the use of Montogmery powering ladder the modular exponentiation unit based on the improved high radix scalable Montgomery modular multiplier can be built resistant to fault and simple power attacks. A 1024-bit modular exponentiation unit with such resistances costs about 255K NAND2 gates in.18 μm CMOS process, and one full modular exponentiation takes about 1.44 ms at 250 MHz.

Koc, Cetin Kaya ( isu author) Modular multiplication forms the basis of many cryptographic functions such as RSA, Diffie-Hellman key exchange, and ElGamal encryption. For large RSA moduli, combining the fast Fourier transform (FFT) with McLaughlin's Montgomery modular multiplication (MLM) has been validated to offer cost-effective implementation results. However, the conditional selections in McLaughlin's algorithm are considered to be inefficient and vulnerable to timing attacks, since extra long additions or subtractions may take place and the running time of MLM varies. In this work, we restrict the parameters of MLM by a set of new bounds and present a modified MLM algorithm involving no conditional selection. Compared to the original MLM algorithm, we inhibit extra operations caused by the conditional selections and accomplish constant running time for modular multiplications with different inputs. As a result, we improve both area-time efficiency and security against timing attacks. Based on the proposed algorithm, efficient FFT-based modular multiplication and exponentiation are derived. Exponentiation architectures with dual FFT-based multipliers are designed obtaining area-latency efficient solutions. The results show that our work offers a better efficiency compared to the state-of-the-art works from and above 2048-bit operand sizes. For single FFT-based modular multiplication, we have achieved constant running time and obtained area-latency efficiency improvements up to 24.3 percent for 1,024-bit and 35.5 percent for 4,096-bit operands, respectively. © 2012 IEEE. The authors would like to thank the anonymous reviewers for their valuable comments and suggestions to improve the quality of the paper. They are also grateful to Mr. Jingwei Hu who contributed the key ideas on side-channel analysis. This work was supported by the Research Grant Council of the Hong Kong Special Administrative Region, China (Project No. CityU 111913) and Croucher Statup Allowance, 9500015.

RSA is a public key cryptosystem in which encryption and decryption are modular exponentiation functions. Modular exponentiation is achieved by repeated modular multiplications. Montgomery modular multiplication is an efficient algorithm, hence is widely used for RSA public key cryptosystem. Performance of RSA depends on throughput of Montgomery modular multiplication. This paper presents RSA with Early Word based Montgomery modular multiplication. Early word based approach is scalable and Radix 4 Early Word Based Common Multiplicand Montgomery is proposed. RSA cryptosystem is implemented on virtex 5 FPGAs. The processing elements in Early Word based Montgomery use target device resources DSP48E for addition of operands. Two factors: algorithmic approach and use of target device resources have improved the performance of RSA on FPGAs.

We report on a machine assisted verification of an efficient implementation of Montgomery Multiplication which is a widely used method in cryptography for efficient computation of modular exponentiation. We shortly describe the method, give a brief survey of the VeriFun system used for verification, present the formal proofs and report on the effort for creating them. Our work uncovered a serious fault in a published algorithm for computing multiplicative inverses based on Newton-Raphson iteration, thus providing further evidence for the benefit of computer-aided verification.

For big data security, high-speed arithmetic units are needed. Finite field arithmetic has received much attention in error-control codes, cryptography, etc. The modular exponentiation over finite fields is an important and essential cryptographic operation. The modular exponentiation can be performed by a sequence of modular squaring and multiplication based on the binary method. In this paper, we propose a combined algorithm to concurrently perform multiplication and squaring over \(GF(2^{m})\) using the bipartite method and common operations. We expect that the architecture based on the proposed algorithm can reduce almost a half of latency compared to the existing architecture. Therefore, we expect that our algorithm can be efficiently used for various applications including big data security which demands high-speed computation.

Secure transmission of data in a system over the network makes use of various cryptographic techniques. A good and efficient cryptosystem would play a crucial role in providing security services as Data-integrity, Confidentiality, and Authenticity. The security aspect of a cryptosystem is dependent on the computational difficulty involved in solving the mathematical problems involved in the cryptographic technique. Modular exponentiation which makes use of repeated modular multiplication is a tedious process, which is the core operation utilized in cryptosystems. So one can say that the performance of a cryptosystem confides in the performance of modular multiplication and exponentiation. Montgomery multiplication is considered to be a method for performing fast modular multiplication. In this paper comparative study of Montgomery multiplier for various bits is carried out by implementing in Spartan 3E FPGA board and it's different parameters are categorically analyzed.

Modular exponentiation (ME) that computes by repeating modular multiplications (M2), is main operation in public-key cryptosystems. In recent years, many researchers studied on improving M2 and ME methods. This paper presents an improved and efficient modular exponentiation method. In the developed method, the compact SD and bit forwarding techniques and k-partition parallel structure are used to accelerate the modular exponentiation algorithm. The complexity analysis results demonstrate that the proposed method provides an improvements in terms of the number of required clock cycles in comparison with other ME methods.

International audience; The leak resistant arithmetic in RNS was introduced in 2004 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 faster version of the approach of Bajard et al. 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 Bajard et al. after a few number of loop iterations.

This work presents an algorithm to generate depth, quantum gate and qubit optimized circuits for $GF(2^m)$ squaring in the polynomial basis. Further, to the best of our knowledge the proposed quantum squaring circuit algorithm is the only work that considers depth as a metric to be optimized. We compared circuits generated by our proposed algorithm against the state of the art and determine that they require $50 \%$ fewer qubits and offer gates savings that range from $37 \%$ to $68 \%$. Further, existing quantum exponentiation are based on either modular or integer arithmetic. However, Galois arithmetic is a useful tool to design resource efficient quantum exponentiation circuit applicable in quantum cryptanalysis. Therefore, we present the quantum circuit implementation of Galois field exponentiation based on the proposed quantum Galois field squaring circuit. We calculated a qubit savings ranging between $44\%$ to $50\%$ and quantum gate savings ranging between $37 \%$ to $68 \%$ compared to identical quantum exponentiation circuit based on existing squaring circuits., To appear in conference proceedings of the 2017 IEEE Computer Society Annual Symposium on VLSI (ISVLSI 2017)

This paper describes the first attack utilizing the photonic side channel against a public-key crypto-system. We evaluated three common implementations of RSA modular exponentiation, all using the Karatsuba multiplication method. We discovered that the key length had marginal impact on resilience to the attack: attacking a 2048-bit key required only 9% more decryption attempts than a 1024-bit key. We found that the most dominant parameter impacting the attacker's effort is the minimal block size at which the Karatsuba method reverts to naive multiplication: even for parameter values as low as 32 or 64 bits our attacks achieve 100% success rate with under 10,000 decryption operations. Somewhat surprisingly, we discovered that Montgomery's Ladder — commonly perceived as the most resilient of the three implementations to side-channel attacks — was actually the most susceptible: for 2048-bit keys, our attack reveals 100% of the secret key bits with as few as 4000 decryptions.

Blinding has been one of the most effective approaches to resist power analysis attacks on asymmetric cryptosystems like RSA. Blinding is similar to masking in symmetric cryptosystems, but masking can be implemented in various ways like Boolean, affine, polynomial masking, etc. However, for asymmetric cryptosystems with modular exponentiation as a fundamental operation, arithmetic masking or simply blinding has been extremely popular. In this paper, we have presented a secured approach for modular exponentiation in RSA and CRT-RSA cryptosystems with dual blinding. Through dual blinding, we have masked both secret exponent and message twice before executing the fundamental operations. We have also injected two ineffectual instructions between the fundamental operations and blinded the intermediate results to felicitate hiding and resist simple power analysis. The implementation results shows that with a nominal penalty, RSA and CRT-RSA with dual blinding can effectively resist some popular simple power analysis and differential power analysis attacks to a significant extent.

The power analysis attack is a cryptanalytic technique to retri eve an user's secret key using the side-channel power leakage occurred during the execution of cryptographic algorithm embedd ed on a physical device. Especially, many power analysis attacks have targeted on an exponentiation algorithm which is c omposed of hundreds of squarings and multiplications and adopted in public key cryptosystem such as RSA. Recently, a new correlation power attack, which is tried when two modular multiplications have a same input, is proposed in order to reco ver secret key. In this paper, after reviewing the principle of side-channel attack based on input collisions in modular multip lications, we analyze the vulnerability of some exponentiation algorithms having regularity property. Furthermore, we present an improved exponentiation countermeasure to resist against the input collision-based CPA(Correlation Power Analysis) attack an d existing side channel attacks and compare its security with other countermeasures.Keywords: Power Analysis Attack, Exponentiation Algorithm, Modular Multi plication, Input Collision-based CPA

In this paper, we address the problem of finding low cost addition-subtraction sequences for situations where a doubling step is significantly cheaper than a non-doubling one. One application of this setting appears in the computation of the final exponentiation step of the reduced Tate pairing defined on ordinary elliptic curves. In particular, we report efficient addition-subtraction sequences for the Kachisa-Schaefer-Scott family of pairing-friendly elliptic curves, whose parameters involve computing the multi-exponentiation of relatively large sequences of exponents with a size of up to 26 bits.

We present a new mental poker protocol, which achieves negligible probability of cheating in constant round. All of previous secure mental poker protocol use L-round zero-knowledge protocols to ensure the probability of successful active cheating to be O ( 2 - L ) . Our protocol uses a different way to verify the integrity of the shuffle. The cryptosystem and the basic structure of our protocol is based on Castella-Roca’s mental protocol, which is very efficient and secure. The L-round zero-knowledge shuffle verification is replaced by a checksum-like framework. There are two kinds of checksums used in our shuffle: linear checksum and double exponentiation. The “linear checksum” is used to make sure that every card in the deck is distinct. The “double exponentiation checksum” is used to make sure that every card has a legitimate face value. The security can be proved under DDH assumption. The probability of successful cheating is negligible, even if the adversary can actively corrupt the majority of players. It is also very fast. For a 9 player game, the computation cost of our shuffle is comparable to the L-round verification with L = 4 . The time complexity of our shuffle is Θ ( MN + N 2 ) E (compares to Θ ( MN 2 L ) E for a L-round shuffle), where N is the number of players, M is the number of cards, and E is the computation cost of one modular exponentiation. The communication cost is also reduced. Compares to the L-round protocol we based on, number of messages is reduced from Θ ( N 3 L ) to Θ ( N 2 ) , and the total length of messages is reduced from Θ ( N 2 L ( M + N ) ) η to Θ ( MN 2 ) η , where η is the length of an encryption key. For a 9-player game, our shuffle requires only 53% messages, and total length of messages is only 7%(compares to the case L = 30 and all L rounds of shuffle verification are allowed to run in parallel). It is the first constant round mental poker protocol that is provably secure and efficient enough to satisfy the practical needs. The probability of successful cheating is negligible