Search

Roughly four decades ago, Taher ElGamal put forward what is today one of the most widely known and best understood public key encryption schemes. ElGamal encryption has been used in many different contexts, chiefly among them by the OpenPGP email encryption standard. Despite its simplicity, or perhaps because of it, in reality there is a large degree of ambiguity on several key aspects of the cipher. Each library in the OpenPGP ecosystem seems to have implemented a slightly different "flavor" of ElGamal encryption. While-taken in isolation-each implementation may be secure, we reveal that in the interoperable world of OpenPGP, unforeseen cross-configuration attacks become possible. Concretely, we propose different such attacks and show their practical efficacy by recovering plaintexts and even secret keys.

Exponentiation in finite fields is an essential operation used in many applications ranging from error control coding to cryptographic computations, while representation in Gaussian normal basis offers low complexity arithmetic, especially in hardware architectures. In this paper, we propose several new hardware architectures for binary exponentiation in Gaussian normal basis. The proposed architectures make use of different levels of precomputation and the efficient digit-level parallel-in parallel-out, and hybrid-double multipliers. We support our new designs with novel countermeasures against side-channel analysis that require minimal implementation overhead. Moreover, we obtain implementation results for all architectures and provide realistic and fair comparisons with the previously known works available in the literature. It is shown that our newly proposed architectures outperform the existing hardware architectures in terms of area and time complexities and security.

Devices in the Internet-of-Things (IoT) are networked and perform massive computations to support various social IoT systems. Applications in social IoT systems often involve complicated computations that are out of the computation capacity of some resource-constrained IoT devices. Thus, how to enable resource-constrained IoT devices to accomplish complex computations efficiently and securely is of significant importance. To address this problem, we develop a secure edge-aided computation scheme for the social IoT systems. We scope the framework of edge-aided computations and identify the security threats in such a system. We define the security requirements that the outsourcing algorithms should meet. Then, we provide two examples of secure outsourcing algorithms (matrix multiplication and modular exponentiation) that meet the given security requirements. The efficiency and security of the proposed algorithms are supported through the theoretical analysis and experimental results.

In recent years, the growth of vehicles in the urban areas has been massive; thus, we require a secure means via which we can monitor traffic, gain data about traffic conditions, weather, accidents, road defects, speed of the vehicle, condition of the roads, etc. VANET helps us deliver a secure and more efficient means of moni A VANET is an Ad-Hoc network, which helps in exchanging information with different entities from time to time. To ensure secure communication, we want to ensure that there is a presence of a secure session key such that an adversary is not able to gain access to privileged information. Thus, we focus on designing a probabilistic key exchange protocol that can be used in the Vehicular Ad hoc Network (VANET) setting. The proposed protocol is lightweight and is more efficient than bilinear pairing, modular exponentiation, and Elliptic Curve Cryptography. The security proof of the proposed system can be witnessed via Automated Validation of Internet Security Protocols and Applications and BAN logic.

We investigate the problem of securely outsourcing the modular exponentiations in cryptography to an untrusted server, and analyze the security and the efficiency of three privacy-preserving outsourcing protocols for exponentiations proposed in Ding et al. (2017) [18] . Based on Coppersmith's lattice-based method, we present heuristic polynomial-time and ciphertext-only weak-key attacks on these protocols, which shows that the recommended size of the secret keys in their protocols can not assure the input privacy of the exponents. Correspondingly, we explicitly estimate the size of the secure secret keys to circumvent our attacks, and analyze the efficiency of the revised protocols with security settings. Our theoretical analysis and experimental results demonstrate that the protocol of single modular exponentiation is unavailable, the protocol of simultaneous modular exponentiations is not so efficient as claimed but still available, and the protocol of multiple modular exponentiations becomes more efficient as the number of exponentiations increases.

Context. Providing the problem of fast calculation of the modular exponentiation requires the development of effective algorithmic methods using the latest information technologies. Fast computations of the modular exponentiation are extremely necessary for efficient computations in theoretical-numerical transforms, for provide high crypto capability of information data and in many other applications. Objective – the runtime analysis of software functions for computation of modular exponentiation of the developed programs based on parallel organization of computation with using multithreading. Method. Modular exponentiation is implemented using a 2k-ary sliding window algorithm, where k is chosen according to the size of the exponent. Parallelization of computation consists in using the calculation of the remainders of numbers raised to the power of 2i modulo, and their further parallel multiplications modulo. Results. Comparison of the runtimes of three variants of functions for computing the modular exponentiation is performed. In the algorithm of parallel organization of computation with using multithreading provide faster computation of modular exponentiation for exponent values larger than 1K binary digits compared to the function of modular exponentiation of the MPIR library. The MPIR library with an integer data type with the number of binary digits from 256 to 2048 bits is used to develop an algorithm for computing the modular exponentiation with using multithreading. Conclusions. In the work has been considered and analysed the developed software implementation of the computation of modular exponentiation on universal computer systems. One of the ways to implement the speedup of computing modular exponentiation is developing algorithms that can use multithreading technology on multi-cores microprocessors. The multithreading software implementation of modular exponentiation with increasing from 1024 the number of binary digit of exponent shows an improvement of computation time with comparison with the function of modular exponentiation of the MPIR library.

Modular exponentiation, an operation widely utilized in cryptographic protocols to transfer text and other forms of data, can also be applied to Internet-of-Things (IoT) devices with high security requirements. However, due to the high resource consumption of modular exponentiation, IoT devices can face the problem of resource insufficient. Fortunately, the secure outsourcing scheme offers a new solution for resource-constrained devices. In this article, we apply a parallel secure outsourcing scheme to provide the possibility for modular exponentiation operation, which is used in the IoT devices. After that, the task of modular exponentiation is decomposed and we introduce the scheme in more detail. In addition, based on this scheme, we designed an extension scheme for RSA, providing enhanced security for IoT devices. Finally, the analysis of experimental results based on 512–4096 b of data indicates the superiority in scalability and time consumption over the previous schemes.

The fifth-generation (5G) mobile communication technology with higher capacity and data rate, ultra-low device to device (D2D) latency, and massive device connectivity will greatly promote the development of vehicular ad hoc networks (VANETs). Meantime, new challenges such as security, privacy and efficiency are raised. In this article, a hybrid D2D message authentication (HDMA) scheme is proposed for 5G-enabled VANETs, in which a novel group signature-based algorithm is used for mutual authentication between vehicle to vehicle (V2V) communication. In addition, a pre-computed lookup table is adopted to reduce the computation overhead of modular exponentiation operation. Security analysis shows that HDMA is robust to resist various security attacks, and performance analysis also points out that, the authentication overhead of HDMA is more efficient than some traditional schemes with the help of the pre-computed lookup table in V2V and vehicle to infrastructure (V2I) communication.

Public-key cryptographic primitives are time consuming for resource-constrained devices. A classical problem is to securely offload group exponentiations from a (comparatively) weak device—the client—to an untrusted more powerful device—the server. A delegation protocol must usually meet two security objectives: privacy—the exponent or the base should not be revealed to a passive adversary—and verifiability—a malicious server should not be able to make the client accept an invalid value as the result of the delegated computation. Most proposed protocols relies on a secret splitting of the exponent and the base, and a considerable amount of literature has been devoted to their analysis. Recently, Su et al. (Su, Q., Zhang, R. and Xue, R. (2020) Secure outsourcing algorithms for composite modular exponentiation based on single untrusted cloud. Comput. J., 63, 1271.) and Rangasamy and Kuppusamy (Rangasamy, J. and Kuppusamy, L. (2018) Revisiting Single-Server Algorithms for Outsourcing Modular Exponentiation. In Chakraborty, D. and Iwata, T. (eds), Progress in Cryptology - INDOCRYPT 2018: 19th International Conference in Cryptology in India, New Delhi, India, December 912, Vol. 11356, Lecture Notes in Computer Science. Springer, Heidelberg, Germany, pp. 320. proposed outsourcing protocols for modular exponentiations. They claim that their protocols achieve security (privacy and verifiability). We show that these claims are flawed and that their schemes are broken beyond repair. They remain insecure even if one increases significantly the proposed parameters (and consequently the protocols computational and communication complexities). Our attacks rely on standard lattice-based cryptanalytic techniques, namely the Coppersmith methods to find small integer zeroes of modular multivariate polynomials and simultaneous Diophantine approximation methods for the so-called approximate greatest common divisor problem.

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

Outsourcing computation allows an outsourcer with limited resource to delegate the computation load to a powerful server without the exposure of true inputs and outputs. It is well known that modular exponentiation is one of the most expensive operations in public key cryptosystems. Currently, most of outsourcing algorithms for modular exponentiation are based on two untrusted servers or have small checkability with single server. In this paper, we first propose an efficient outsourcing algorithm of modular exponentiation based on two untrusted servers, where the outsourcer can detect the error based on Euler theorem with a probability of 1 if one of the servers misbehaves. We then present an outsourcing algorithm of modular exponentiation with single server, and the outsourcer can also check the failure with a probability of 1. Therefore, the proposed algorithm with single server improves efficiency and checkability simultaneously compare with the previous ones. Finally, we provide the experimental evaluations to demonstrate that the proposed two algorithms are the most efficient ones in all of the outsourcing algorithms for an outsourcer.

The modular exponentiation has been proved better in terms of computational efficiency as compared to bilinear pairing. Therefore, discrete logarithm, a concept of modular exponentiation may be incorporated to present improved security schemes. With this aim, an efficient public key encryption scheme with equality test (PKEwET) is proposed in this paper. Unlike the most of existing bilinear pairing based PKEwET schemes, the presented scheme employs discrete logarithm to improve the computational efficiency. Moreover, we introduce the verification process during the test phase to validate the ciphertext and to improve the security comparative to the prevalent schemes. The performance analysis depicts that the proposed scheme is quite efficient and more practical than the existing PKEwET schemes. More precisely, compared to Lin et al.’s scheme, the time cost has been reduced by at least 39% for the decryption process. Furthermore, for the type-3 test phase, the time cost has been reduced by at least 68%.

With the development of Internet of Things (IoT) and 5G, edge computing, as a new computing paradigm, has been widely popularized in academia and industry. Due to the distributed architecture and being close to the user, edge computing can faster respond to the IoT device’s request and provide a better quality of service for IoT applications. An important application of edge computing is to outsource the complicated computation task to the nearby edge nodes. Modular exponentiation is widely considered as one of the most common and expensive operations in cryptographic protocols. As far as we know, all secure outsourcing algorithms of modular exponentiation are based on the centralized cloud server, but not based on multiple edge nodes. In this article, we propose the first secure and distributed outsourcing algorithm for modular exponentiation (fixed base and variable exponent) under the multiple noncolluding edge node model. In our algorithm, the exponent is divided into a certain number of parts. In addition, we propose another secure and distributed outsourcing algorithm of modular exponentiation (variable base and variable exponent). The user can protect the privacy in the process of outsourcing and detect the invalid results from edge nodes with high probability. Finally, we provide the experimental evaluation to support that our proposed algorithms are efficient on both the user side and the edge node side.

Rivest–Shamir–Adleman (RSA) is one of the widely deployed public-key algorithms. Yet, its decryption facet is very time consuming for resource-constrained Internet-of-Thing (IoT) devices, as it is based on the modular exponentiation of a large number. Although several variants of RSA have been designed to accelerate decryption, the outcomes have been far from satisfactory. Therefore, it is of imminent importance to investigate how to securely outsource RSA decryption to computational powerful parties as an alternative solution. In this article, we introduce the first efficient and secure outsourcing scheme for RSA decryption in IoT. Though RSA decryption is achieved via modular exponentiation, existing secure outsourcing schemes for modular exponentiation either assume the modulus to be prime and are not applicable to RSA or incur massive computation costs and are heavy laden in practice. To address these issues, we have designed our scheme based on the Chinese remainder theorem (CRT). In our scheme, the private keys (including the exponent and the modulus) and the plaintext are concealed concurrently, and the proposed scheme is highly efficient for both client and cloud. In addition, our scheme enables the client to detect any misbehavior of the cloud server with a probability of 99.17%. To validate the effectiveness of our proposed scheme, we provide rigorous proofs of security and verifiability, as well as efficiency analysis. The effectiveness and efficiency of our scheme are further confirmed based on experimental results.

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 streng...

IoT in Wireless Sensor Networkis a network of physical objects connected to internet such as RFID and sensors. As these types of objects have limited computation power and memory, execution of public key cryptography would be a daunting task. So a light weight encryption with Elliptic Curve Cryptography (ECC) is proposed in this work. A major issue in ECC is its computational cost as it is complicated to compute the scalar multiplication. To address this issue, a novel method called graph based addition chaining (GBAC) is proposed. This graph technique produces all possible optimum addition chains for the given integer n by utilizing edge weight of all possible numbers created from each number of addition chain. This addition chain technique can be used in modular exponentiation which is an essential step in the implementation of public cryptographic algorithms like ElGamal, RSA, etc., so that the time for encryption and decryption for these algorithms can be reduced drastically. The proposed GBAC technique has used addition chaining technique instead of scalar multiplication in ECC which greatly reduces the computation time as well as computation cost. It also reduces the complexity in ECC. Numerous experiments has been made and proved that our work decreases the decryption time by at least 10% than RSA algorithm, reduces computation cost and improves the performance of parameters like CPU time, Memory requirement and key preparation time and better than RSA in decryption.

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.

Edge computing provides users with nearby services, promotes the development of the Internet of Things and transforms the mode of traditional electronic medical system that improves the speed and accuracy of medical diagnosis. However, edge computing has introduced new security challenges, such as the difficulty in applying standard encryption algorithms because of the limited computing capability of devices on the edge and concerns of privacy leakage. In this article, we propose a data access scheme by employing a lightweight attribute-based encryption (ABE) to address the security weaknesses of edge computing for e-health. Our novel modular exponential outsourcing algorithm outsources the shared data to the untrusted edge server and verifies the correctness of the returned results while achieving a lightweight computational load. The proposed Mask Algorithm along with blind pairs conceals the bases and exponents of the encrypted data, thus preserving the privacy of sensitive data in the process of outsourced computing. Security analysis and performance evaluation confirmed the security and efficiency of the proposed method.

Recently in IEEE Access (DOI: 10.1109/ACCESS.2018.2890565), Li et al. proposed a secure outsourcing algorithm for modular exponentiation in one single untrusted server model and a new method of generating transformation keys. They claimed that their solution can securely outsource encryption and decryption to untrusted ESP (encryption service providers) and DSP (decryption service providers), leaving only a constant number of simple operations for the DO (data owner) and eligible users to perform locally. In addition, both DO and qualified users can check the correctness of the results returned from ESP and DSP, respectively. Although the authors provide security proofs for their scheme, unfortunately, after carefully observing their scheme, we find that the scheme has security vulnerabilities. These vulnerabilities allow the adversary to generate the sub-key for any attribute and replace ciphertext sub-item, which result in the adversary to be able to break their scheme. In response to this problem, we propose an improved solution and proved its security.

Modular exponentiation is one of the most fundamental operations in lots of encryption and signature systems. Due to the heavy computation cost of modular exponentiation, many schemes have been put forward to securely outsource modular exponentiation to cloud. However, most of the existing approaches need two non-colluded cloud servers to securely complete the modular exponentiation, which will result in private data leakage upon the cloud servers collude. Besides, most existing schemes assume both base and exponent in modular exponentiation are private, which does not conform to many real-world applications. For example, in public key encryption system that uses modular exponentiation, one of base and exponent is the public key, and the other is a message. Usually, only the message should be privately protected. In this paper, we propose two secure outsourcing schemes for fixed-base (public base and private exponent) and fixed-exponent (private base and public exponent), respectively. In the proposed schemes, we employ only one cloud server and can thus avoid collusion attack. Further, we achieve an efficient and secure Paillier encryption outsourcing scheme based on our secure modular exponentiation outsourcing methods. Additionally, we theoretically analyze our overheads and leverage simulation experiments to evaluate our proposed solutions, which show our schemes can achieve high efficiency.

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).

Advanced encryption standard (AES) crypto-algorithm design can be implemented in software and hardware. No known attacks are available that can break the AES with brute force or cryptanalysis in finite time. However, when the AES is implemented in hardware, test infrastructure such as scan chain, stimuli decompressor, response compactor and built-in self-test (BIST) are included in the normal design for making the crypto-chip easily testable after manufacturing. This test infrastructure is highly susceptible to attacks. The attacker may misuse the scan-chain content for the retrieval of secret key from AES hardware. In this study, the authors investigated scan-chain attack based on different distributions of key-related flip-flops of AES hardware implementation with X-tolerant response compactor-based test infrastructure. The modular exponentiation security scheme as a counter measure against test infrastructure attacks is proposed. In this study, the statistical security analyses are performed with and without the proposed countermeasure in case of AES hardware followed by X-tolerant test response compactor. The experimental result shows that the proposed countermeasure thwarts the attack with almost constant rate for different distributions of key-related flops in the scan-chain, and hence it is not dependent on the nature of scan-chain architecture design.

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, whic...

This paper introduces a computational scheme for calculating the exponential bw where b and w are positive integers. This two-step method is based on elementary number theory that is used routinely in this and similar contexts, especially the Chinese remainder theorem (CRT), Lagrange’s theorem, and a variation on Garner’s algorithm for inverting the CRT isomorphism. We compare the performance of the new method to the standard fast algorithm and show that for a certain class of exponents it is significantly more efficient as measured by the number of required extended multiplications.

The emergence of Internet of Things (IoT) brings us the possibility to form a well connected network for ubiquitous sensing, intelligent analysis, and timely actuation, which opens up many innovative applications in our daily life. To secure the communication between sensor nodes, gateway devices and cloud servers, cryptographic algorithms (e.g., digital signature, block cipher, and hash function) are widely used. Although cryptographic algorithms are effective in preventing malicious attacks, they involve heavy computation that may not be executed efficiently in resource constraint sensor nodes. In particular, the authentication of a sensor node is usually performed through a digital signature (e.g., RSA and elliptic curve cryptography), which can be slow when executed on a microcontroller. In this paper, an IoT architecture that offloads the digital signature generation to a nearby signature gateway equipped with graphic processing unit (GPU) accelerator are proposed. The communication process for signature offloading, together with optimized implementation techniques for RSA in signature gateway, are also presented in this paper. We have evaluated two different ways to implement modular exponentiation in RSA, namely residue number system and multiprecision montgomery multiplication (MPMM). The experimental results show that our RSA implementation using MPMM is 10.1% faster than the best RSA implementation in GPU. Our proposed IoT architecture with signature gateway can successfully reduce the burden of sensor nodes to generate signatures, at the same time preserve the ability to authenticate the sensor nodes.

Security plays a major role in data transmission and reception. Providing high security is indispensable in communication systems. The RSA (Rivest–Shamir–Adleman) cryptosystem is used widely in cryptographic applications as it offers highly secured transmission. RSA cryptosystem uses Montgomery multipliers and it involves modular exponentiation process which is attained by performing repeated modular-multiplications. This leads to high latency and owing to improve the speed of multiplier, highly efficient modular multiplication methodology needs to be applied. In the conventional methodology, Carry Save Adder (CSA) is used in the multiplication and it consumes more area and it has larger delay, but in the suggested methodology, the Reverse Carry Propagate (RCP) adder is used in the place of CSA adder and the obtained output shows promising results in terms of area and latency. The simulation is done with Xilinx ISE design suite. The proposed multiplier can be used effectively in signal processing, image processing and security based applications.

Multi-Party Non-Interactive Key Exchange (MP-NIKE) is a fundamental cryptographic primitive in which users register into a key generation centre and receive a public/private key pair each. After that, any subset of these users can compute a shared key without any interaction. Nowadays, IoT devices suffer from a high number and large size of messages exchanged in the Key Management Protocol (KMP). To overcome this, an MP-NIKE scheme can eliminate the airtime and latency of messages transferred between IoT devices. MP-NIKE schemes can be realized by using multilinear maps. There are several attempts for constructing multilinear maps based on indistinguishable obfuscation, lattices and the Chinese Remainder Theorem (CRT). Nevertheless, these schemes are inefficient in terms of computation cost and memory overhead. Besides, several attacks have been recently reported against CRT-based and lattice-based multilinear maps. There is only one modular exponentiation-based MP-NIKE scheme in the literature which has been claimed to be both secure and efficient. In this article, we present an attack on this scheme based on the Euclidean algorithm, in which two colluding users can obtain the shared key of any arbitrary subgroup of users. We also propose an efficient and secure MP-NIKE scheme. We show how our proposal is secure in the random oracle model assuming the hardness of the root extraction modulo a composite number., 14 pages, 3 figures

Internet-of-things (IoT) is the latest revolution in electronic industry after internet. Smart appliances, portable computing devices, mobile phones and handheld system dominates in IoT, because a large portion of world population use it. Major applications, mainly financial, e-commerce, information security and sensitive data-communication need special attention in terms of security. This creates a strong requirement for providing security solutions into these devices. Incorporating security module inside an Integrated-Circuit(IC) is a major challenge as most of the portable devices are smaller in size and highly power efficient. Hence, an optimized cryptographic implementation techniques, which differ from high-throughput desktop computers and servers need to be developed. RSA algorithm is extensively used public key cryptosystem but it suffers from long execution time. In this paper, we have designed and implemented a high performance, smaller area and low power consumption scalable Systolic-Montgomery-Multiplication based RSA (modulus sizes-1K, 2K and 4K) algorithm targeted for various IoT applications. Huffman compression is used to enhance the execution time. The design is evaluated on Xilinx Artix-7 FPGA. A practical RSA application was run on the design and the performance is superior than X86, ARM, MIPS, NEC and ST architectures. Further the design is integrated with Microblaze processor and we achieved data rate of approximately 56.76 Mbps at 44 MHz operating clock frequency for modular exponentiation operation using dedicated Direct-Memory-Access (DMA).

19th International Conference, ACNS 2021, Kamakura, Japan, June 21–24, 2021, Proceedings, Part II; International audience; The Secure Remote Password protocol is a password-based authenticated key-exchange between two parties. One advantage is to prevent offline dictionary attacks from an adversary eavesdropping the communication. We present how such an attack is feasible if the modular exponentiation at the heart of the protocol is vulnerable and leaks some data related to the password.In the case of a fixed exponent, adding randomness during the execution is a classical protection mechanism, and such a mechanism is present in Apple’s cryptographic library to randomize the exponent. Despite being intended to protect against complex side-channel attacks, we show that its usage makes the implementation vulnerable to simple side-channels such as power analysis.This leakage observed in the library is mild but is useful for the attack we propose on the Secure Remote Password protocol.

As an asymmetric encryption algorithm, RSA is currently known as the ripest and most widely used one. However, it is showed in many documents in recent years that RSA algorithm is lack of security, due to its weakness in defending side channel attacks, especially power analysis attacks. This paper proposes an RSA coprocessor resistant to power analysis attack, which adds pseudo operation and exponential randomization masking to defend SPA and DPA. Then, this paper improves the speed of RSA by using 256-base subtracted-free Montgomery multiplier combining with two-layer Karatsuba multiplier and CSA adder. This design is able to be implemented on both FPGA and ASIC. With a technology of 100 MHz clock frequency and SMIC 130 nm process, DC synthesis is implemented as well. The experiment result shows that our 1024-bit RSA design costs an area of 310 K gates and has a throughput of 110 Kbps.

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

This chapter illustrates the energy-efficient hardware implementation of the BFW technique for modular exponentiation. Hardware accomplishments of the given BFW techniques have been estimated with respect to energy, power and throughput. The performance of PKCs can be enhanced either by hardware or by software approaches. The software approaches are simple and less complex for maintaining, on the other hand, hardware approaches are more secure while implementing PKC for high-risk applications.

The efficiency and throughput primarily of public key cryptography(PKC) are determined by the efficient execution of modular multiplication and thus modular exponentiation. If we wish to optimize the time complexity of the PKC, it is essential to develop a transformation algorithm that minimizes the required number of modular multiplications. If we succeed in minimizing the number of required modular multiplications it will result in the reduction of clock cycles and energy with increased throughput i.e., the overall system will be more energy-efficient. Performance and a higher level of security for cryptographic techniques can be achieved by hardware means and by software means. Most of the existing works are focused on hardware, as it offers more security.

Asymmetric cryptography is commonly used to safeguard computer network security. Particularly, RSA algorithm is one of the most predominantly deployed crypto-algorithms. However, the standard RSA algorithm relies on multiple big-number modular exponentiation operations, which increase the execution time for encryption and decryption. In this research, we focus on the parallelization of several accelerated methods of RSA in a GPU environment. We have analyzed and developed improved parallel algorithms based on two recently improved variants of the RSA algorithm, implementing and optimizing them with NVIDIA-P100 Graphic Card. The accelerated parallel RSA algorithms we proposed and demonstrated under the specific hardware configuration achieved parallel speed-up factors up to 57 and 42 in encrypting and decrypting messages of lengths up to 8192-bytes, respectively.

The efficiency of fully homomorphic encryption has always affected its practicality. With the dawn of Internet of things, the demand for computation and encryption on resource-constrained devices is increasing. Complex cryptographic computing is a major burden for those devices, while outsourcing can provide great convenience for them. In this paper, we firstly propose a generic blockchain-based framework for secure computation outsourcing and then propose an algorithm for secure outsourcing of polynomial multiplication into the blockchain. Our algorithm for polynomial multiplication can reduce the local computation cost to O n . Previous work based on Fast Fourier Transform can only achieve O n log n for the local cost. Finally, we integrate the two secure outsourcing schemes for polynomial multiplication and modular exponentiation into the fully homomorphic encryption using hidden ideal lattice and get an outsourcing scheme of fully homomorphic encryption. Through security analysis, our schemes achieve the goals of privacy protection against passive attackers and cheating detection against active attackers. Experiments also demonstrate our schemes are more efficient in comparisons with the corresponding nonoutsourcing schemes.

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 a multi-core RSA processor along with its hardware scheduler. This processor can execute multiple cryptographic transformations simultaneously, for achieving higher throughput with a constant frequency. As we know that, modular exponentiation is a series of modular multiplications and in order to achieve better performance, we need an efficient implementation of modular multiplication. The modular multiplication has costly division operations. Therefore, the performance of RSA can be enhanced: 1. By minimizing the number of required modular multiplications for evaluating modular exponentiation. 2. By minimizing the required clock cycles for calculating a modular multiplication. 3. By implementing the cryptographic module efficiently in a multi-core processor.

Hardware techniques are more efficient than software for improving parallelism and performance. Suitable hardware not only provides better results but also helps in reducing the cost. The hardware techniques greatly affect the execution of an algorithm. The hardware techniques used for the implementation of the core operations of the PKC are discussed in this chapter.

The efficiency of homomorphic encryption has always affected its practicality. With the dawn of internet of things, the demand for computation and encryption on lightweight devices is increasing. Complex cryptographic computing is an important burden for lightweight devices, but outsourcing provides great convenience for them. In this paper, based on blockchain, we propose a secure outsourcing scheme for Fully Homomorphic Encryption using Hidden Ideal Lattice (FHEHIL), in which the time-consuming operations (including modular exponentiation and polynomial multiplication) are outsourced. For polynomial multiplication, we propose a secure outsourcing algorithm that reduces the local computation cost to \(O\left(n\right)\). Previous work based on Fast Fourier Transform can only achieve \(O\left(nlog(n)\right)\) for the local cost. Through security analysis, our scheme achieves the goals of privacy protection against passive attackers and cheating detection against active attackers. Experiments also demonstrate our scheme is more efficient in comparison with the non-outsourcing FHEHIL.

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

As one of the most expensive computations in public-key cryptosystems, modular exponentiation is typically out-sourced to the cloud servers. Traditional cloud-based outsourcing algorithms depend on multiple untrusted servers to guarantee the security, which may lead to vulnerability to the collusion attack. Although recent single-server multiple-requests outsourcing algorithms are more secure, they have to perform multiple requests to the single untrusted server to guarantee the security and checkability of the data, which will incur unacceptable latency and local computational costs. In comparison, the edge computing paradigm enhances security since it has multiple computational nodes, including some highly secure local computational nodes. In this paper, we propose the secure outsourcing algorithm of modular exponentiation for the edge computing paradigm. To address the dilemma that the computational resources of different nodes vary significantly, we design two lightweight algorithms to adaptively separate the modular exponentiation to the nodes based on the computational resources. To guarantee the outsourcing checkability, we propose a protocol verify the result returned from each node. We formally prove the security and checkability of our algorithm and validate the efficiency of our algorithm based on experiments and case studies.

Asymmetric cryptography algorithms, still considered the most robust tool available in the cryptography domain. It incorporates intensive modular exponentiation calculations, which entail considerable computing power, memory and storage space. Common IoT device is equipped with limited computing resources and so, for security purposes, it can execute symmetric and limited asymmetric cryptography. In most cases, IoT devices do not have the capacity required for executing massive modular multiplications of numbers of magnitude of 4 K bits and more. This leads to the lack of asymmetric cryptography in the IoT domain resulting with a reduction in security means to cope with the raising security challenges. The security problem increases as the number of IoT devices is expected to significantly grow soon. We propose a new implementation of asymmetric cryptography, which splits its heavy calculations into micro-processes, where each micro-process is distributed to an appropriate IoT device, connected to the network. The accepted result is transferred back to the distributing IoT. Once all the results are accumulated, a consolidation process is activated to generate the final calculation result, which then is fed into the cryptography process, to generate the Encrypted/Decrypted string, proving the ability to maintain asymmetric cryptography also at the IoT level without compromising security.

This research aims to implement different modular exponentiation algorithms and evaluate the average complexity and compare it to the theoretical value. We use the library GMP to implement seven modular exponentiation algorithms. They are Left-to-right Square and Multiply, Right-to-left Square and Multiply, Left-to-right Signed Digit Square, and Multiply Left-to-right Square and Multiply Always Right-to-left Square and Multiply Always, Montgomery Ladder and Joye Ladder. For some exponent bit length, we choose 1024 bits and execute each algorithm on many exponent values and count the average numbers of squares and the average number of multiplications. Whenever relevant, our programs will check the consistency relations between the registers at the end of the exponentiation.

International audience; The modular exponentiation is crucial to the RSA cryptographic protocol, and variants inspired by the Montgomery ladder have been studied to provide more secure algorithms. In this paper, we abstract away the iterative conditional branching used in the Montgomery ladder, and formalize systems of equations necessary to obtain what we call the semi-interleaved and fully-interleaved ladder properties. In particular, we design fault-injection attacks able to obtain bits of the secret against semi-interleaved ladders, including the Montgomery ladder, but not against fully-interleaved ladders that are more secure. We also apply these equations to extend the Montgomery ladder for both the semi-and fully-interleaved cases, thus proposing novel and more secure algorithms to compute the modular exponentiation.

Past research has evidently proved that public key cryptosystems are usually slower than symmetric key cryptosystems due to the reason that they use one additional cryptographic key and different methods for encryption and decryption. RSA is one of the most common asymmetric key cryptography algorithms. Recent research has focused on speeding up RSA using various techniques. With the introduction of distributed computing, parallelization of algorithms enables them to run on multiple cores concurrently at a time. RSA consists of two resource intensive operations namely Modular Exponentiation of up to 1024-bit exponents and repeated calculation of Greatest common divisor. Thus, RSA lays the perfect base for application of Montgomery Reduction algorithm to optimize the Repeated Modular multiplication in exponentiation. In this paper we proposed a parallel scheme for RSA using a new parallel data structure known as Concurrent Indexed List of character blocks. The aim of our research was to improve the...

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.

With the growing popularity of cloud computing in recent years, data owners (DOs) now prefer to outsource their data to cloud servers and allow the specific data users (DUs) to retrieve the data. Searchable encryption is an important tool to provide secure search over the encrypted cloud data without infringing data confidentiality and data privacy. In this work, we consider a secure search service providing fine-grained and search functionality, called attribute-based multiple keyword search (ABMKS), which can be seen as an extension of searchable encryption. In the existing ABMKS schemes, the computation operations in the encrypted keyword index generation are time-consuming modular exponentiation, and the number of which is linearly growing with the factor $m$ . Here $m$ is the number of keywords embedded in a file. To reduce the computation overhead, in this paper, we propose an ABMKS with only multiplication operations in encrypted keyword index generation. As a result, the computation cost of the encrypted keyword index generation is more efficient than the existing schemes. In addition, the encrypted keyword indexes are aggregated into one item, which is regardless of the number of underlying keywords in a file data. Finally, the security and the performance analysis demonstrate that our scheme is both efficient and secure.

Modular exponentiation is an exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography. Most technological applications of modular arithmetic involve exponentials with very large numbers. In this paper, we propose a high radix reconfigurable implementation for the Right-to-Left Modular Exponentiation with NAF-Representation by exploiting the maximum possible parallelism of the internal operations. The proposed design targeted the ALTERA Cyclone IV FPGA (EP4CGX22CF19C7) along with Quartus II simulation package. The proposed design was evaluated in terms of the maximum operational frequency, the total path delay, the total design area and the total thermal power dissipation. The synthesized results revealed that the proposed high radix architecture implementation has recorded: critical path delay of 25.5 ns, maximum operational frequency of 44.59 MHz, hardware design area (number of logic elements) of 2556 LEs, and total thermal power dissipation estimated as 221.82 mW. Consequently, the proposed modular exponentiation architecture can be efficiently employed by many public key cryptographic mechanisms.

Lossy identification schemes derive tightly secure signature schemes via the Fiat-Shamir transformation. There exist several instantiations of lossy identification schemes by using several cryptographic assumptions. In this paper, we propose a new construction of lossy identification scheme from the decisional RSA assumption which are introduced by Groth. Our lossy identification scheme has efficient response algorithm because it requires no modular exponentiation.