Search

With the fast development of cloud computing, clients without enough computational power can widely outsource their heavy computations to cloud service providers. One of the most widely used and costly operations in cryptographic protocols is modular exponentiation, which can be computed at a lower cost by enjoying advantages of cloud computing, however, at the same time we need to address new challenges such as data privacy and verification of results. In this paper, first, we propose a secure outsourcing of single modular exponentiation protocol with verifiability one. Although the proposed single exponentiation scheme has the same verifiability as Ren’2018, but our scheme requires one less modular multiplication. However, the main contribution of this paper is proposing a scheme for outsourcing of multiplications of several modular exponentiations, hereafter called as composite exponentiation, which to the best of our knowledge, and is the first outsourcing scheme with full verification for composite exponentiation. As the evaluation results show, the advantages of this scheme, in comparison with state of the art schemes, are evident in terms of performance and verifiability criteria. [ABSTRACT FROM AUTHOR]

A comparison and analysis of using the developed software implementation of the MontgomeryArithmetic class for computing modular exponentiation are conducted. The performance speed of the developed Montgomery modular multiplication is compared to that of the regular modular multiplication for calculating the modular exponentiation based on the right-to-left binary method for a fixed basis with precomputation of a reduced set of residues. The obtained results of modular exponentiation computing with parallelization based on multithreading on general-purpose computers speed up the computation by an average of 1.5 times using the developed modular Montgomery multiplication compared to the modular exponentiation functions of the MPIR, OpenSSL, and Crypto++ software libraries. [ABSTRACT FROM AUTHOR]

Modular exponentiation is crucial for secure data exchange in cryptography, especially for resource-constrained Internet of Things (IoT) devices. These devices often rely on third-party servers to handle computationally intensive tasks like modular exponentiation. However, existing outsourcing solutions for the RSA algorithm may have security vulnerabilities. This work identifies a critical flaw in a recent outsourcing protocol for RSA proposed by Hu et al. We demonstrate how this flaw compromises the security of the entire RSA system. Subsequently, we propose a robust solution that strengthens the RSA algorithm and mitigates the identified vulnerability. Furthermore, our solution remains resilient against existing lattice-based attacks. The proposed fix offers a more secure and efficient way for IoT devices to leverage the power of third-party servers while maintaining data integrity and confidentiality. An extensive performance evaluation confirms that our solution offers comparable efficiency while significantly enhancing security compared to existing approaches. [ABSTRACT FROM AUTHOR]

With the development of the Internet of Things, smart grids have become indispensable in our daily life and can provide people with reliable electricity generation, transmission, distribution and control. Therefore, how to design a privacy-preserving data aggregation protocol has been a research hot-spot in smart grid technology. However, these proposed protocols often contain some complex cryptographic operations, which are not suitable for resource-constrained smart meter devices. In this paper, we combine data aggregation and the outsourcing of computations to design two privacy-preserving outsourcing algorithms for the modular exponentiation operations involved in the multi-dimensional data aggregation, which can allow these smart meter devices to delegate complex computation tasks to nearby servers for computing. By utilizing our proposed outsourcing algorithms, the computational overhead of resource-constrained smart meter devices can be greatly reduced in the process of data encryption and aggregation. In addition, the proposed algorithms can protect the input's privacy of smart meter devices and ensure that the smart meter devices can verify the correctness of results from the server with a very small computational cost. From three aspects, including security, verifiability and efficiency, we give a detailed analysis about our proposed algorithms. Finally, through carrying out some experiments, we prove that our algorithms can improve the efficiency of performing the data encryption and aggregation on the smart meter device side. [ABSTRACT FROM AUTHOR]

On account of the high computational cost of modular exponentiation, the local clients with limited resources can delegate the modular exponentiation to the cloud servers with strong computing capacity. This paper mainly studied the outsourcing algorithm of the modular exponentiation like u" ( mod N), where N is the product of two large prime numbers. The method used Euler theorem to design a new modular exponentiation outsourcing scheme based on two servers model. In the process of computing and outsourcing, it guaranteed the privacy protection of base u, exponent a and calculation results for the two severs. The safety and efficiency analysis and experimental simulation show that compared with the existing schemes, the proposed new scheme has better execution efficiency and verifiability, the efficiency is higher on the client side, and the probability of verifiability of the new scheme is 1. [ABSTRACT FROM AUTHOR]

The CMERE algorithm was designed to resist DPA attacks on modular exponentiation. It was implemented and tested at the algorithmic level for different key sizes of the RSA cryptosystems. The strength of CMERE lied on the facts that it could be implemented both on left-to-right and right-to-left binary methods for modular exponentiation without any changes in the original algorithm. Also, the execution of modular exponentiation was completely bit independent making it a very strong countermeasure against simple and differential power analysis attacks. In this paper, we have verified the CMERE algorithm at hardware level using VHDL. During formal verification with VHDL on FPGA, the algorithm was modified for practical implementation. However, the overall strength of the improved CMERE algorithm remains the same as the original algorithm. [ABSTRACT FROM AUTHOR]

Verifiable computation (VC) enables a computationally weak client to outsource the computation of a function f to a more powerful but untrusted server. The server returns an answer that allows the client to recover the correct result, accompanied by a proof of correctness. The basic requirement of a VC scheme is efficiency, i.e., the time consuming in preparing its input and verifying the server's proof must be less than the time required to compute the function on its own. In this paper, we propose a novel outsourcing scheme for modular exponentiation from shareable functions, which is secure even in the presence of adaptive adversaries. Compared with previous works, our algorithm is superior in both efficiency and checkability. In order to keep the exponent privacy, our algorithm invokes the less subroutine, which accounts for the largest proportion of the time spent. The client can detect the error with overwhelming probability. We then gave a comparation that demonstrates the efficiency of the proposed outsourcing algorithm and scheme. Finally, we propose a generic scheme for shareable function family, and analyze the concrete security. [ABSTRACT FROM AUTHOR]

This paper presents an approach to compute secured modular exponentiation to mitigate power analysis attacks. Two processes have been designed based on 'multiply-always' binary method, which injects dummy multiplications so that the original multiplications can remain intact. The two processes are being invoked based on a random variable, which generated either 0 or 1. With these randomised modular exponentiation, the proposed approach can resist simple and differential power analysis attacks to a large extent. The proposed approach has been implemented using conventional 'squaring-multiplication' and 'Montgomery-Ladder' methods. Further, the work has also been extended to CRT-RSA, which is widely used for fast computation. The proposed method has been implemented for different key sizes of 1024-bit, 1536-bit and 2048-bit RSA & CRT-RSA. The analysis and results show that with a complexity of O (n) , the proposed approach can resist some of the standard DPA attacks on modular exponentiation. [ABSTRACT FROM AUTHOR]

This paper presents an FPGA implementation of the most critical operations of Public Key Cryptography (PKC), namely the Modular Exponentiation (ME) and the Modular Multiplication (MM). Both operations are integrated as Programmable System on Chip (PSoC) where the processor Microblaze of Xilinx is used for flexibility. Our objective is to achieve a best trade-off between time execution, occupied area and flexibility. The implementation of these operations on such environment requires taking into account several criteria. Indeed, the Hardware (HW) architectures data bus should be smaller than the input data length. The design must be scalable to support different security levels. The implementation achieves optimums execution time and HW resources number. In order to satisfy these constraints, Montgomery Power Ladder (MPL) and Montgomery Modular Multiplication (MMM) algorithms are utilized for the ME and the MM implementations as HW accelerators, respectively. Our implementation approach is based on the digit-serial method for performing the basic arithmetic operations. Efficient parallel and pipeline strategies are developed at the digit level for the optimization of the execution times. The application for 1024-bits data length shows that the MMM run in 6.24 μ s and requires 647 slices. The ME is executed in 6.75 ms using 2881 slices. [ABSTRACT FROM AUTHOR]

Modular exponentiation is an expensive discrete-logarithm operation, difficult for resource-constrained users to perform locally. Fortunately, thanks to burgeoning cloud computing, users are willing to securely outsourcing modular exponentiations to cloud servers to reduce computation overhead. In this paper, we contrive a fully verifiable secure outsourcing scheme for modular exponentiation with only a single server, named MExp. MExp not only prevents users’ private information leakage during outsourcing by our new logical division method, but also eliminates collusion attacks occurring in algorithms with two untrusted servers. Moreover, our MExp allows outsourcers to detect any misbehavior with a probability of 1, which shows significant improvement in checkability when compare to other single-server-based schemes. With a view to reducing computation overhead, MExp is extended to multiple modular exponentiations, named M2Exp. The algorithm significantly diminishes the local costs of multiple modular exponentiation calculations and the checkability is still 1. Compared with existing state-of-the-art schemes, MExp and M2Exp have outstanding performance in both efficiency and checkability. Finally, MExp and M2Exp are applied to Cramer-Shoup encryptions and Schnorr signatures. [ABSTRACT FROM 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. [ABSTRACT FROM AUTHOR]

This paper presents the computation of a specific hexadecimal digit of π by using a Bailey–Borwein–Plouffe (BBP)-type formula on a cluster of Intel Xeon Phi processors. The BBP-type formula can be computed using modular exponentiation. We use Montgomery multiplication for the modular multiplication, which is the most time-consuming part of the modular exponentiation. We vectorize multiple modular exponentiations and multiple integer divisions by using Intel Advanced Vector Extensions 512 (Intel AVX-512) instructions. A parallel implementation of the BBP-type formula is presented. The 100 quadrillionth hexadecimal digit of π was computed on a 512-node cluster of Intel Xeon Phi processors with an elapsed time of 641 h 29 min that includes the time required for verification. [ABSTRACT FROM AUTHOR]

Modular multiplication (MM) is the main operation in cryptography algorithms such as elliptic‐curve cryptography (ECC) and Rivest–Shamir–Adleman, where repeated MM is used to perform elliptic curve point multiplication and modular exponentiation, respectively. The algorithm for the proposed architecture is derived from the Chinese remainder theorem and performs MM completely within a residue number system (RNS). Moreover, a 40‐channel RNS moduli‐set is proposed for this architecture to benefit from the short‐channel width of the RNS moduli‐set. The throughput of the architecture is enhanced by pipelining and pre‐computations. The proposed architecture is fabricated as an ASIC using 65‐nm CMOS technology. The measurement results are obtained for energy dissipation at different voltage levels from 0.43 to 1.25 V. The maximum throughput of the proposed design is 1037 Mbps while operating at a frequency of 162 MHz with an energy dissipation of 48 nJ. The proposed architecture enables the construction of low‐voltage and energy‐efficient ECCs. [ABSTRACT FROM AUTHOR]

Modular exponentiation is a fundamental and most time-consuming operation in several public-key cryptosystems such as the RSA cryptosystem. In this paper, we propose two new parallel algorithms. The first one is a fast parallel algorithm to multiply n numbers of a large number of bits. Then we use it to design a fast parallel algorithm for the modular exponentiation. We implement the parallel modular exponentiation algorithm on Google cloud system using a machine with 32 processors. We measured the performance of the proposed algorithm on data size from $$2^{12}$$ to $$2^{20}$$ bits. The results show that our work has a fast running time and more scalable than previous works. [ABSTRACT FROM AUTHOR]

The chosen-message method is used to be employed in conducting Simple Power Analysis (SPA) attack by means of selecting special input messages. However, it is difficult to make distinction by visual observation i.e., SPA in practical IoT hardware environment. In this paper, we proposed a practical chosen-message correlation power analysis (CPA) attack which combines the chosen-message method with CPA for side channel attack. Then, we adopt other two practical chosen-messages, 1 and n + 1, to attack Boscher's right-to-left binary exponentiation algorithm which is wildly considered as an efficient side channel resistant algorithm. Finally, this paper presents a countermeasure to resist the chosen-message CPA attack over Boscher's algorithm without nullifying its countermeasure features to Differential Power Analysis (DPA) and Differential Fault Analysis (DFA). To validate the proposed attack method and countermeasure, a 1024-bit RSA coprocessor is constructed on the Xilinx Virtex-5 with the Side-channel Attack Standard Evaluation Board (SASEBO) to implement Boscher's algorithm as well as our proposed algorithm and launched the proposed attack on it separately. The experiment results show that the proposed attack and countermeasure are feasible and efficient. [ABSTRACT FROM AUTHOR]

Several ways to perform data encryption have been found, and one of the functions involved in standard algorithms such as RSA is the modular exponentiation. Basically, the RSA algorithm uses some properties of modular arithmetic to cipher and decipher plain text, with a certain performance dependence on text lengths. The growth in computing capacity has created the need to use robust systems that can perform calculations with significantly large numbers and the formulation of procedures focused on improving the speed to achieve it. One of these is the M-ary algorithm for the execution of the modular exponential function. This paper describes an implementation of this algorithm in reprogrammable hardware (FPGA) to evaluate its performance. The first section of this work introduces the M-ary algorithm. The second section uses block description for implementation understanding. The third section shows the results in time diagrams, and finally, the last section conclusions. [ABSTRACT FROM AUTHOR]

Digital Signatures can be considered analogous to an ordinary handwritten signature for signing messages in the Digital world. Digital signature must be unique and exclusive for each signer. Multiple Digital Signatures signed by either single or multiple signers can be verified at once through Batch Verification. There are two main issues with respect to Batch Verification of Digital Signatures; first is the security problem and the second is the computational speed. Due to e-commerce proliferation, quick verification of Digital Signatures through specific hardware or efficient software becomes critical. Internet companies, banks, and other such organizations use Batch verification to accelerate verification of large number of Digital Signatures. Many Batch Verification techniques have been proposed for various Digital Signature algorithms. But most of them lack the security requirements such as signature authenticity, integrity, and non-repudiation. Hence there is a need for the study of batch verification of Digital Signatures. The main contributions of our survey include: (a) Identifying and categorizing various Batch verification techniques for RSA, DSS, and ECDSA(includes schemes based on Bilinear Pairing) (b) Providing a comparative analysis of these Batch Verification techniques (c) Identifying various research challenges in the area of Batch verification of signatures. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Modular exponentiation is the basic operation of public key cryptosystem，but the cost is expensive. Verifiable outsourcing delegates the computing cost to servers， which can greatly improve the computing efficiency of user， and verify the result returned from servers. In study of outsourcing multiple modular exponentiations， this paper proposed a new algorithm of double modular exponentiations by hiding the exponent， and then proposed an algorithm of multiple modular exponentiations similarly. These schemes used two untrusted servers to achieve the privacy of base and index， and the user could detect the error with probability close to 1. Compared with the previous algorithms， proposed algorithms increase the computational efficiency and verifiable probability. Finally， theoretical analysis and simulation experiments show that they greatly reduce the computational cost of user. [ABSTRACT FROM AUTHOR]

Modular exponentiation is a time-consuming operation widely used in cryptography. Modular multi-exponentiation, a generalization of modular exponentiation also used in cryptography, deserves further analysis from the algorithmic point of view. The parallelization of modular multi-exponentiation can be obtained by generalizing methods used to parallelize modular exponentiation. In this paper, we present a new parallelization method for the modular multi-exponentiation operation with two optimizations. The first one searches for the fastest solution without taking into account the number of processors. The second one balances the load among the processors and finds the smallest number of processors that achieves the fastest solution. In detail, our algorithms compute the product of i modular exponentiations. They split up each exponent in j blocks and start j threads. Each thread processes together i blocks from different exponents. Thus, each block of an exponent is processed in a different thread, but the blocks of different exponents are processed together in the same thread. Using addition chains, we show the minimum number of threads with load balance and optimal running time. Therefore, the algorithms are optimized to run with the minimum time and the minimum number of processors. [ABSTRACT FROM AUTHOR]

Reducing computational cost of cryptographic computations for resource-constrained devices is an active research area. One of the practical solutions is to securely outsource the computations to an external and more powerful cloud server. Modular exponentiations are the most expensive computation from the cryptographic point of view. Therefore, outsourcing modular exponentiations to a single, external and potentially untrusted cloud server while ensuring the security and privacy provides an efficient solution. In this paper, we propose new efficient outsourcing algorithms for modular exponentiations using only one untrusted cloud server. These algorithms cover public-base and private-exponent, private-base and public-exponent, private-base and private-exponent, more generally private-base and private-exponents simultaneous modular exponentiations. Our algorithms are the most efficient solutions utilizing only one single untrusted server with the best checkability probabilities. Furthermore, unlike existing schemes, which have fixed checkability probability, our algorithms provide adjustable predetermined checkability parameters. Finally, we apply our algorithms to outsource oblivious transfer protocols and blind signatures which are expensive primitives in modern cryptography. [ABSTRACT FROM AUTHOR]

Computation of the AX mod n or AX BY mod n is complex in many ElGamal-like public-key cryptosystems. This paper used the block method in sparse form to improve the performance of modular exponentiation and analyzed the computational cost using state transition diagram. This method also extended the concept of block method and improved its applicability. Analysis results show that its effective with only limited pre-calculation, thus is suitable for some devices with limited storage space, such as smart card. [ABSTRACT FROM AUTHOR]

With the rapid development of cloud services, the techniques for securely outsourcing the prohibitively expensive computations to untrusted servers are getting more and more attention in the scientific community. Exponentiations modulo a large prime have been considered the most expensive operations in discrete-logarithm-based cryptographic protocols, and they may be burdensome for the resource-limited devices such as RFID tags or smartcards. Therefore, it is important to present an efficient method to securely outsource such operations to (untrusted) cloud servers. In this paper, we propose a new secure outsourcing algorithm for (variable-exponent, variable-base) exponentiation modulo a prime in the two untrusted program model. Compared with the state-of-the-art algorithm, the proposed algorithm is superior in both efficiency and checkability. Based on this algorithm, we show how to achieve outsource-secure Cramer-Shoup encryptions and Schnorr signatures. We then propose the first efficient outsource-secure algorithm for simultaneous modular exponentiations. Finally, we provide the experimental evaluation that demonstrates the efficiency and effectiveness of the proposed outsourcing algorithms and schemes. [ABSTRACT FROM AUTHOR]

This paper presents an implementation of Rivest, Shamir and Adleman (RSA) cryptosystem based on hardware/software (HW/SW) co-design. The main operation of RSA is the modular exponentiation (ME) which is performed by repeated modular multiplications (MMs). In this work, the right-to-left (R2L) algorithm is used for the implementation of the ME as a programmable system on chip (PSoC). The processor MicroBlaze of Xilinx is used for flexibility. The R2L method is often suggested to improve the timing performance, since it is based on parallel computations of MMs. However, if the optimization of HW resources is a constraint, this method can be executed sequentially using a single modular multiplier as a custom intellectual property (IP). Consequently, the execution time of the ME becomes dependent of three factors, namely the capability of the custom IP to perform the MMs, the nonzero bit string of the exponent and the communication link between the processor and the custom IP. In order to achieve the best trade-off between area, speed and flexibility, we propose three implementations in this work. The first one is a pure software solution. The second one takes benefit of a HW accelerator dedicated to the MM execution. The last one is based on a dual strategy. Two parallel MMs are implemented within a custom IP and local memories are used close to the arithmetic units to minimize the communication link influence. The results show that in the application to RSA 1024-bits, the ME runs in 22,25 ms, while using only 1,848 slices. [ABSTRACT FROM AUTHOR]

Multiprecision modular exponentiation has a variety of uses, including cryptography, prime testing and computational number theory. It is also a very costly operation to compute. GPU parallelism can be used to accelerate these computations, but to use the GPU efficiently, a problem must involve many simultaneous exponentiation operations. Handling a large number of TLS/SSL encrypted sessions in a data center is an important problem that fits this profile. We are developing a framework that enables generation of highly efficient implementations of exponentiation operations for different NVIDIA GPU architectures and problem instances. One of the challenges in generating such code is that NVIDIA's PTX is not a true assembly language, but is instead a virtual instruction set that is compiled and optimized in different ways for different generations of GPU hardware. Thus, the same PTX code runs with different levels of efficiency on different machines. And as the precision of the computations changes, each architecture has its own break-even points where a different algorithm or parallelization strategy must be employed. To make the code efficient for a given problem instance and architecture thus requires searching a multidimensional space of algorithms and configurations, by generating PTX code for each combination, executing it, validating the numerical result, and evaluating its performance. Our framework automates much of this process, and produces exponentiation code that is up to six times faster than the best known hand-coded implementations for the NVIDIA GTX 580. Our goal for the framework is to enable users to relatively quickly find the best configuration for each new GPU architecture. However, in migrating to the GTX 680, which has three times as many cores as the GTX 580, we found that the best performance our system could achieve was significantly less than for the GTX 580. The decrease was traced to a radical shift in the NVIDIA architecture that greatly reduces the storage resources for each core. Further analysis and feasibility simulations indicate that it should be possible, through changes in our code generators to adapt for different storage models, to take greater advantage of the parallelism on the GTX 680. That will add a new dimension to our search space, but will also give our framework greater flexibility for dealing with future architectures. [ABSTRACT FROM AUTHOR]

Cloud computing is an emerging computing paradigm in which IT resources and capacities are provided as services over the Internet. Promising as it is, this paradigm also brings forth new challenges for security when users want to securely outsource the computation of cryptographic operations to the untrusted cloud servers. As we know, modular exponentiation is one of the basic operations among most of current cryptosystems. In this paper, we present the generic secure outsourcing schemes enabling users to securely outsource the computations of exponentiations to the untrusted cloud servers. With our techniques, a batch of exponentiations (e.g. t exponentiations) can be efficiently computed by the user with only O( n+ t) multiplications, where n is the number of bits of the exponent. Compared with the state-of-the-art algorithm, the proposed schemes are superior in both efficiency and verifiability. Furthermore, there are not any complicated pre-computations on the user side. Finally, the schemes are proved to be secure under the Subset Sum Problem. [ABSTRACT FROM AUTHOR]

Abstract: The modular exponentiation operation of the current algorithms for asymmetric cryptography is the most expensive part in terms of computational cost. The RSA algorithm, for example, uses the modular exponentiation algorithm in encryption and decryption procedure. Thus, the overall performance of those asymmetric cryptosystems depends heavily on the performance of the specific algorithm used for modular exponentiation. This work proposes new parallel algorithms to perform this arithmetical operation and determines the optimal number of processors that yields the greatest speedup. The optimal number is obtained by balancing the processing load evenly among the processors. Practical implementations are also performed to evaluate the theoretical proposals. [Copyright &y& Elsevier]

Modular exponentiation with large modulus and exponent, which is usually accomplished by repeated modular multiplications, has been widely used in public key cryptosystems. Typically, the Montgomery's modular-multiplication algorithm is used since no trial division is necessary, and the carry–save addition (CSA) is employed to reduce the critical path. In this paper, we optimize the Montgomery's multiplication and propose architectures to perform the least significant bit first and the most significant bit first algorithms. The developed architecture has the following distinctive characteristics: 1) use of digit serial approach for Montgomery multiplication. 2) Conversion of the CSA representation of intermediate multiplication using carry–skip addition. This allows the critical path to be reduced, albeit with a small-area speed penalty; and 3) precompute the quotient value in Montgomery's iteration in order to speed up the operating frequency. In this paper, we present results in Xilinx Virtex 5 and in 0.18-\mu\m application-specified integrated circuit technologies. For fair comparison with previous works, Xilinx Virtex 2 results are reported. Experimental results show that the proposed modular exponentiation and modular-multiplication design obtain the best delay performance compared with the published works and outperform them in terms of area–time complexity as well. [ABSTRACT FROM AUTHOR]

This article developed a system of choosing of modular exponentiation method, built on the basis of fuzzy logic. This system allows for optimum protection of information in userdefined conditions. [ABSTRACT FROM AUTHOR]

This article are shown theoretical bases of modular multiplication operations and exponentiation using a theoretical-numbers bases of Rademacher and Krestenson. It's authors created new analytical expressions calculation complexity of high speed algorithms. [ABSTRACT FROM AUTHOR]

This paper proposes new chosen-message power-analysis attacks for public-key cryptosystems based on modular exponentiation, where specific input pairs are used to generate collisions between squaring operations at different locations in the two power traces. Unlike previous attacks of this kind, the new attack can be applied to all standard implementations of the exponentiation process, namely binary (left-to-right and right-to-left), m-ary, and sliding window methods. The proposed attack can also circumvent typical countermeasures, such as the Montgomery powering ladder and the double-add algorithm. The effectiveness of the attack is demonstrated in experiments with hardware and software implementations of RSA on an FPGA and a PowerPC processor, respectively. In addition to the new collision generation methods, a highly accurate waveform matching technique is introduced for detecting the collisions even when the recorded signals are noisy and there is a certain amount of clock jitter. [ABSTRACT FROM AUTHOR]

Modular exponentiation is a basic operation in various applications, such as cryptography. Generally, the performance of this operation has a tremendous impact on the efficiency of the whole application. Therefore, many researchers have devoted special interest to providing smart methods and efficient implementations for modular exponentiation. One of these methods is the sliding-window method, which pre- processes the exponent into zero and non-zero partitions. Zero partitions allow for a reduction of the number of modular multiplications required in the exponentiation process. In this paper, we devise a novel hardware for computing modular exponentiation using the sliding-window method. The partitioning strategy used allows variable-length non-zero partitions, which increases the average number of zero partitions and so decreases that of non-zero partitions. It performs the partitioning process in parallel with the pre-computation step of the exponent so no overhead is introduced. The implementation is efficient when compared against related existing hardware implementations. [ABSTRACT FROM AUTHOR]

In this work we re-examine a modular multiplication and a modular exponentiation method. The multiplication method, proposed by Hayashi in 1998, uses knowledge of the factorization of both N ++ 1 and N ++ 2 to compute a multiplication modulo N. If both N ++ 1 and N ++ 2 can be factored into k equally sized relatively prime factors then the computations are done modulo each of the factors and then combined using the Chinese Remainder Theorem. It was suggested that the (asymptotic) computational costs of the method is 1/ k of simply multiplying and reducing modulo N. We show, however, that the computational costs of the method is (asymptotically) at least as costly as simply multiplying and reducing modulo N for both squarings and general multiplications when efficient arithmetic is used. The exponentiation method, proposed by Hwang, Su, Yeh and Chen in 2005, is based on Hayashi's method and uses knowledge of the factorization of P ++ 1 and P -- 1 to compute an exponentiation modulo an odd prime P. We begin by showing that the method cannot be used as a general purpose exponentiation method and then modify the method so that it can work as a general purpose modular multiplication method. Like Hayashi's method, however, this method is at best (asymptotically) only as efficient as simply multiplying and reducing modulo P. [ABSTRACT FROM AUTHOR]

Modular exponentiation is a basic operation in cryptosystems. Generally, the performance of this operation has a tremendous impact on the efficiency of the whole application. The efficiency of the modular exponentiation, in turn, depends mainly on that of modular multiplications as the former is somehow a repetition of the latter. One of the methods that computes the modular power is the sliding-window method, which pre-processes the exponent into zero and nonzero partitions. Zero partitions allow for a reduction of the number of modular multiplications required in the exponentiation process. In this paper, we devise a novel System-on-Chip (SoC) implementation for computing modular exponentiation using the sliding-window method. We also propose a hardware-only implementation for that operation. The partitioning strategy used in both approaches allows constant-length nonzero partitions, which increases the average number of zero partitions and so decreases that of nonzero partitions. The partitioning strategy allows variable-length zero partitions. The hardware/software co-design implements the modular multiplication on hardware and the rest of the system in software. We provide a useful comparison of the SoC-based implementation against hardware-only implementation. Both of the proposed implementations can be used in any industrial embedded system that needs to secure the handled information. [ABSTRACT FROM AUTHOR]

Due to the computational limitations at present, there is no efficient integer factorization algorithm that can break at least 2048 bits of RSA with strong prime factors in polynomial time. Although Shor's algorithm based on a quantum computer has been presented, the quantum computer is still in its early stages of the development. As a result, the integer factorization problem (IFP) is a technique that is still being refined. Pollard's p − 1 is an integer factorization algorithm based on all prime factors of p − 1 or q − 1, where p and q are two distinct prime factors of modulus. In fact, Pollard's p − 1 is an efficient method when all prime factors of p − 1 or q − 1 are small. The aim of this paper is to propose a variant of Pollard's p − 1 in order to decrease the computation time. In general, the proposed method is very efficient when all prime factors of p − 1 or q − 1 are the members of B-smooth. Assuming this condition exists, the experimental results demonstrate that the proposed method is approximately 80 to 90 percent faster than Pollard's p − 1. Furthermore, the proposed technique is still faster than Pollard's p − 1 for some values of modulus in which at least one integer is a prime factor of p − 1 or q − 1 while it is not a member of B-smooth. In addition, it is demonstrated that the proposed method's best-case running time is O (x) ,where x is represented as bits length of n . [ABSTRACT FROM AUTHOR]

Abstract: Finite field operations have been widely used in the data communication security applications. This paper proposes two AB 2 multipliers based on the cellular automata over finite field. They deploy the mixture advantages in the perspective of both in area and time complexity by applying the property of irreducible all one polynomial as a modulus. First, an AB 2 multiplier is proposed with a new algorithm. Then, another algorithm and its architecture for AB 2 multiplication are derived to reduce the complex wiring in the first architecture. They can be used as a basic architecture for the public key cryptosystems in IEEE P1363. [Copyright &y& Elsevier]

We present a compact FPGA implementation of a modular exponentiation accelerator suited for cryptographic applications. The implementation efficiently exploits the properties of modern FPGAs. The accelerator consumes 434 logic elements, four 9-bit DSP elements, and 13604 memory bits in Altera Stratix EP1S40. It performs modular exponentiations with up to 2250-bit integers and scales easily to larger exponentiations. Excluding pre-and post-processing time, 1024-bit and 2048-bit exponentiations are performed in 26.39ms and 199.11ms, respectively. Due to its compactness, standard interface, and support for different clock domains, the accelerator can effortlessly be integrated into a larger system in the same FPGA. The accelerator and its performance are demonstrated in practice with a fully functional prototype implementation consisting of software and hardware components. [Copyright &y& Elsevier]

Abstract: The motivation for designing fast modular exponentiation algorithms comes from their applications in computer science. In this paper, a new CSD-EF Montgomery binary exponentiation algorithm is proposed. It is based on the Montgomery algorithm using the canonical-signed-digit (CSD) technique and the exponent-folding (EF) binary exponentiation technique. By using the exponent-folding technique of computing the common parts in the folded substrings, the same common part in the folding substrings can be simply computed once. We can thus improve the efficiency of the binary exponentiation algorithm by decreasing the number of modular multiplications. Moreover, the “signed-digit representation” has less occurrence probability of the nonzero digit than binary number representation. Taking this advantage, we can further effectively decrease the amount of modular multiplications and we can therefore decrease the computational complexity of modular exponentiation. As compared with the Ha–Moon’s algorithm 1.261718m multiplications and the Lou-Chang’s algorithm 1.375m multiplications, the proposed CSD-EF Montgomery algorithm on average only takes 0.5m multiplications to evaluate modular exponentiation, where m is the bit-length of the exponent. [Copyright &y& Elsevier]

Abstract: Modular exponentiation is an important operation in several public-key cryptosystems. It is performed using successive modular multiplications. For the sake of efficiency, one needs to reduce the total number of required modular multiplications. In this paper, we propose two efficient hardware implementations for computing modular exponentiations, which are based on the m-ary method. The m-ary method includes a power pre-computation step. The first design ignores the exponent and pre-computes all possible powers while the second takes advantage of the formation of the exponent to compute only those powers that are really necessary for the rest of the computation. As it can be expected, the implementation of the first architecture, compared with that of the second one, requires more time to complete an exponentiation. In compensation, however, the first should require less hardware area than the second. We provide a comparison of these two implementations using the performance factor, which takes into account both space and time requirements. [Copyright &y& Elsevier]

Abstract: Most of cryptographic systems are based on modular exponentiation, wherein the operands are considerably large. Generally, modular exponentiation is implemented using a chain of modular multiplications. One way of improving the throughput of a cryptographic system implementation is reducing the number of the required modular multiplications. Given the exponent, finding the minimal number of multiplications that are necessary to reach the exponentiation results is a hard problem. We take advantage of an evolutionary stochastic process, commonly called genetic algorithms, to compute minimal addition chains, allow us to reduce drastically the number of the required modular multiplications. In this paper, we investigate two different ways to implement modular exponentiation based on the evolved addition chain: the first approach consists of implementing all the exponentiation operation on hardware and the second approach combines software and hardware. While the first approach attempts to optimise the encryption/decryption throughput regardless of the cost of system implementation, the second attempts to reach a balance between the throughput and the cost of the implementation. [Copyright &y& Elsevier]

Modular exponentiation in an abelian group is one of the most frequently used mathematical primitives in modern cryptography. Batch verification is an algorithm for verifying many exponentiations simultaneously. We propose two fast batch verification algorithms. The first one makes use of exponents of small weight, called sparse exponents, and is asymptotically 10 times faster than individual verification and twice as fast as previous works at the same security level. The second one can only be applied to elliptic curves defined over small finite fields. Using sparse Frobenius expansion with small integer coefficients, we give a complex exponent test which is four times faster than the previous works. For example, each exponentiation in one batch asymptotically requires nine elliptic curve additions on some ellipiic curves for 280 security. [ABSTRACT FROM AUTHOR]

Abstract: When the lengths of the operators are at least 1024 binary or 300 decimal digits, modular exponentiation can be time-consuming and is often the dominant part of the computation in many computer algebra systems. The prime approach on this computational problem is known as the square-and-multiply method, which includes two versions, i.e. the left-to-right binary algorithm and the right-to-left binary algorithm. For the past years, too many attentions have been paid to propose the fast modular exponentiation methods based on the left-to-right binary algorithm. However, extremely few attentions have been paid on developing the fast modular exponentiation methods based on the right-to-left binary algorithm. In this paper, we propose a t-fold exponent method based on the right-to-left binary algorithm. From the performance view, our t-fold exponent method is similar to the m-ary method based on the left-to-right binary algorithm. From the structure view, our t-fold exponent method offers a framework for the fast modular exponentiation methods based on the right-to-left binary algorithm. More important, it is the first but steady step to develop the fast modular exponentiation methods based on the right-to-left binary algorithm. [Copyright &y& Elsevier]

Cryptographic protocols are successfully analyzed using formal methods. However, formal approaches usually consider the encryption schemes as black boxes and assume that an adversary cannot learn anything from an encrypted message except if he has the key. Such an assumption is too strong in general since some attacks exploit in a clever way the interaction between protocol rules and properties of cryptographic operators. Moreover, the executability of some protocols relies explicitly on some algebraic properties of cryptographic primitives such as commutative encryption. We give a list of some relevant algebraic properties of cryptographic operators, and for each of them, we provide examples of protocols or attacks using these properties. We also give an overview of the existing methods in formal approaches for analyzing cryptographic protocols. [ABSTRACT FROM AUTHOR]

Since the advent of data communication over networks, it has become imperative to ensure security of information. Cryptography is a technique that is being employed. This paper takes a look at an important aspect of the public key encryption scheme, the modular exponentiation technique, with the view of optimizing it. Taking a look at some public key encryption schemes, it would be observed that the modular exponentiation process is primal to achieving high speed algorithms in data encryption. With special emphasis on the Montgomery exponentiation algorithm, a blend of this algorithm with the sliding window method of exponentiation is proposed. A detailed complexity analysis of the proposed and selected algorithms was carried out. Both algorithms were implemented and simulated using MATLAB 6.5. While the proposed algorithm did not prove to be faster than the classical Montgomery exponentiation algorithm, it was rather observed that it makes lesser number of calls to the Montgomery reduction sub-function. This means 10% lesser number of loops during execution and thus better optimized for lower memory applications. [ABSTRACT FROM AUTHOR]

Efficient computation of the modular exponentiations is very important and useful for public-key cryptosystems. In this paper, an efficient parallel binary exponentiation algorithm is proposed which based on the Montgomery multiplication algorithm, the signed-digit-folding (SDF) and common-multiplicand-multiplicand (CMM) techniques. By using the CMM technique of computing the common part from two modular multiplications, the same common part in two modular multiplications can be computed once rather twice, we can thus improve the efficiency of the binary exponentiation algorithm by decreasing the number of modular multiplications. By dividing the bit pattern of the minimal-signed-digit recoding exponent into three equal length parts and using the technique of recording the common parts in the folded substrings, the proposed SDF-CMM algorithm can improve the efficiency of the binary algorithm, thus can further decrease the computational complexity of modular exponentiation. Furthermore, by using the proposed parallel SDF-CMM Montgomery binary exponentiation algorithm, on average the total number of single-precision multiplications can be reduced by about 61.3% and 74.1% as compared with Chang-Kuo-Lin's CMM modular exponentiation algorithm and Ha-Moon's CMM Montgomery modular exponentiation algorithm, respectively. [ABSTRACT FROM AUTHOR]

Abstract: This paper investigates all 8 variants of the He’s digital signature scheme based on factoring and discrete logarithms. Instead of using three modular exponentiation computation, the two most optimal schemes of the generalized He’s signature require only two modular exponentiation for signature verification. [Copyright &y& Elsevier]

An efficient computation of the modular exponentiations C = M E mod N is very useful for public-key cryptosystems. In this paper, an efficient parallel modular exponentiation algorithm is proposed based on both the common-multiplicand-multiplication (CMM) and signed-digit-folding (SDF) techniques. The 'minimal-signed-digit (SD) recoding algorithm' has less occurrence probability of the nonzero digit than the binary number representation. Taking this advantage, we can effectively decrease the amount of modular multiplications. By dividing the bit string of the minimal-SD recoding exponent E into three equal-length parts and by using the technique of recording the common parts in the folded substrings, the 'folding-exponent algorithm' can improve the efficiency of the binary algorithm, thus it can further decrease the computational complexity of modular exponentiation. As the modular squaring operation in GF(2 n ) over the normal basis can be done by a simple shift operation, the modular multiplications and the modular squaring operations in our proposed CMM-SDF algorithm can be executed in parallel. By using our proposed parallel CMM-SDF algorithm, we can obtain the optimal overall computational complexity as 0.689 k + 11 multiplications by folding the minimal-SD recoding exponent E exactly one-time in SD radix-2 recoding system, where k denotes the digit-length of the exponent and n denotes the folding time of the exponent. [ABSTRACT FROM AUTHOR]

For modern cryptographic systems, the public key cryptosystem such as RSA requires modular exponentiation ( M E mod  N ). The M , E and N are either as large as the 1024-bit integers or even larger, it is not a very good idea to directly compute M E mod  N . Recently, there are many techniques have been invented to solve the time-consuming computations of such time-consuming modular exponentiation. Among these useful algorithms, the "binary (square-and-multiply) algorithm" reduces the amount of modulo multiplications. As the "signed-digit representation algorithm" has the property of the nonzero digit occurrence probability equals to 1/3, taking this advantage, this method can more effectively decrease the amount of modular multiplications. Moreover, by using the technique of recording the common parts in the folded substrings, the "folding-exponent algorithm" can improve the efficiency of the binary algorithm, thus can further decrease the computational complexity of modular exponentiation. In this paper, a new modular exponentiation algorithm is proposed which based on the binary algorithm, signed-digit representation, and the folding-exponent technique. By using the parallel processing technique, in our proposed method, the modular multiplications and modular squaring can be executed in parallel, and thus lower down the computational complexity to k + 3 multiplications. As modular squaring operation over GF(2 n ) is carried out by a simple cyclic right shift operation, the computational complexity of our proposed method can be further reduced to 29 k /36 + 3 multiplications. [ABSTRACT FROM AUTHOR]

The multiplication operations in GF(2m) fields are widely used in cryptosystems. However, the multiplication operations for public-key cryptosystems require very large operands with 512 bits or more, and then existing multipliers are not available for such multiplications. In this paper, we will present a partition algorithm to divide large operands into small operands such as 32 bits or 64 bits, and then existing multipliers can be employed. We also present a parallel version of the partition algorithm by employing an important natural property of the multiplication operations in GF(2m) fields. [ABSTRACT FROM AUTHOR]

In many problems, modular exponentiation |xb|m is a basic computation, often responsible for the overall time performance, as in some cryptosystems, since its implementation requires a large number of multiplications.It is known that |xb|m=|x|b|ϕ(m)|m for any x in [1,m−1] if m is prime; in this case the number of multiplications depends on ϕ(m) instead of depending on b. It was also stated that previous relation holds in the case m=pq, with p and q prime; this case occurs in the RSA method.In this paper it is proved that such a relation holds in general for any x in [1,m−1] when m is a product of any number n of distinct primes and that it does not hold in the other cases for the whole range [1,m−1].Moreover, a general method is given to compute |xb|m without any hypothesis on m, for any x in [1,m−1], with a number of modular multiplications not exceeding those required when m is a product of primes.Next, it is shown that representing x in a residue number system (RNS) with proper moduli mi allows to compute |xb|m by n modular exponentiations |xib|mi in parallel and, in turn, to replace b by |b|ϕ(mi) in the worst case, thus executing a very low number of multiplications, namely ⌈log2mi⌉ for each residue digit.A general architecture is also proposed and evaluated, as a possible implementation of the proposed method for the modular exponentiation. [Copyright &y& Elsevier]