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]

We designed an image encryption algorithm based on a non-degeneracy 3D chaotic map and a keyed strong S-Box, which is capable of encrypting color image with any size. First, we constructed a non-degeneracy 3D discrete hyperchaotic map (3D-DHCM), and based on it we constructed a keyed strong S-Box without fixed point, reverse fixed point or short period rings. The map is based on modular exponentiation operation, and its inverse function is the discrete logarithm problem. Finally, we applied blurring techniques to the plain image prior to encryption and employed permutation, confusion, and diffusion techniques to shuffle all pixels. Experimental and analytical results demonstrated that the NPCR and UACI are all close to their ideal values 99.6094070% and 33.4635070%, and the pixels of the cipher image are completely confused, which are all close to the ideal value 8. In addition, the chi-square values for encrypted images are significantly lower than before, with a maximum value of 255.1503. It is showed that the algorithm is superior to others in terms of its ability to encrypt images with any size and withstand common attacks. [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]

A comparison and analysis of the use of the developed software implementation of the class MontgomeryArithmetic for computing modular exponentiation are conducted. The computation speed of the developed Montgomery modular multiplication is compared to the regular modular multiplication for calculating the modular exponentiation based on the right-to-left binary elevation method for a fixed basis with a preliminary calculation of a reduced set of remainders. The obtained results of performing modular exponentiation computations with parallelization based on multithreading on general-purpose computers speed up the computations 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]

Side-Channel Attacks target the recovery of key material in cryptographic implementations by measuring physical quantities such as power consumption during the execution of a program. Simple Power Attacks consist in deducing secret information from a trace using a single or a few samples, as opposed to differential attacks which require many traces. Software cryptographic implementations usually contain a data-independent execution path, but often do not consider variations in power consumption associated to data. In this work, we show that a technique commonly used to select a value from different possible values in a control-independant way leads to significant power differences depending on the value selected. This difference is actually so important that a single sample can be considered for attacking one condition, and no training on other traces is required. We exploit this finding to propose a single-trace attack without any knowledge gained on previous executions, using trace folding. We target the two modular exponentiation implementations in Libgcrypt, getting respectively 100% and 99.998% correct bits in average on 30 executions using 2,048-bit exponents. We also use this technique to attack the scalar multiplication in ECDSA, successfully recovering all secret nonces on 1,000 executions. Finally, the insights we gained from this work allow us to show that a proposed countermeasure from the literature for performing the safe loading of precomputed operands in the context of windowed implementations can be attacked as well.

Let $ N = \left\{{n}_{1}, {n}_{2}, \;\dots , {n}_{k}\right\} $ be a finite set of positive numbers. The problem of finding the minimal number of additions required to compute all elements of N starting from 1 (called the addition sequence problem) is NP-complete. It is equivalent to finding the minimum number of multiplications needed to compute a group exponentiation $ {g}^{{n}_{1}}, {g}^{{n}_{2}}, \;\dots , {g}^{{n}_{k}} $, where g is an element in a group. This paper aims to propose a new metaheuristic algorithm using a simulated annealing strategy to generate a short addition sequence. The performance of the proposed algorithm is measured by considering two parameters: The size of N and the domain of $ {n}_{\mathrm{i}}, 1\le i\le k $. The proposed algorithm is a new trade-off between the length of the generated addition sequence and the average running time of generating addition sequences. It sometimes produces longer addition sequences than exact algorithms that are slower, and it is slower than suboptimal algorithms that produce longer addition sequences.

Let N = {n1, n2, ..., nk} be a finite set of positive numbers. The problem of finding the minimal number of additions required to compute all elements of N starting from 1 (called the addition sequence problem) is NP-complete. It is equivalent to finding the minimum number of multiplications needed to compute a group exponentiation gn1, gn2, ..., gnk, where g is an element in a group. This paper aims to propose a new metaheuristic algorithm using a simulated annealing strategy to generate a short addition sequence. The performance of the proposed algorithm is measured by considering two parameters: The size of N and the domain of ni,1 ≤ i ≤ k. The proposed algorithm is a new trade-off between the length of the generated addition sequence and the average running time of generating addition sequences. It sometimes produces longer addition sequences than exact algorithms that are slower, and it is slower than suboptimal algorithms that produce longer addition sequences. [ABSTRACT FROM AUTHOR]

Big number operation has always been a bottleneck to computer system as it imposes high demand on computing power. With a limited power available, operations such as exponentiation and multiplication involving large integer belonging to encryption process requires grave scrutiny. One way to address this issue is by replacing an original complex computation into a sequence of small computations that in the end produces the same results. This paper takes an evolutionary approach to survey numerous articles that have contributed to the advancement of integer representation. Numerous representations were proposed, those that come into play concentrated on reducing non-zero digits and limiting non-zero spacing other than allowing subtraction operation. A comparison was made to distinguish the properties of each method from the others. This detailed outlook can be a guide for identifying the correct representation to be chosen for implementation within specific application. [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 rapid development and application of artificial intelligence and block chain, the requirement of information and data security is also increased, in which the public-key cryptography, such as Rivest-Shamir-Adleman (RSA) cryptography, plays a significant role. Modular exponentiation is fundamental in computer arithmetic and is widely applied in cryptography, such as ElGamal cryptography, Diffie–Hellman key exchange protocol, and RSA cryptography. The implementation of modular exponentiation in a residue number system leads to high parallelism in computation and has been applied in many hardware architectures. While most residue number system (RNS)-based architectures utilize RNS Montgomery algorithm with two residue number systems, the recent modular multiplication algorithm with sum residues performs modular reduction in only one residue number system with about the same parallelism. In this work, it is shown that the high-performance modular exponentiation and RSA cryptography can be implemented in RNS. Both the algorithm and architecture are improved to achieve high performance with extra area overheads, where a 1024-bit modular exponentiation can be completed in 0.567 ms in Xilinx XC6VLX195t-3 platform, costing 26489 slices, 87357 LUTs, 363 dedicated multipilers of $18 \times 18$ bits, and 65 block RAMs. [ABSTRACT FROM AUTHOR]

In inter-system connections or between any two points in communication, it is necessary to make sure that the data goes securely. This is achieved by encrypting the sent data. As the disciplines of cryptography and network security matured, more practical applications were developed that were not readily available to ensure network security. Today, encryption has become a necessity in the digital environment. In this study, basic cryptography terms are mentioned. The RSA algorithm (Rivest-Shamir-Adleman) is the basis of a cryptographic system, a suite of cryptographic algorithms used for private security services or purposes, and this allows public key encryption, widely used to secure particularly sensitive data sent over an insecure network such as the internet. Commonly used methods were examined and RSA encryption method was chosen in accordance with the purpose of the study. RSA, a public key encryption technique, is built on the difficulty of generating and processing very large integers. In this study, operations with large numbers that take a long time are completed in a short time using various methods. It has been reflected in the study by creating a more secure structure by using large prime numbers for the key generation process. [ABSTRACT FROM AUTHOR]

The aim of this paper is to present a new design for a pseudorandom number generator (PRNG) that is cryptographically secure, passes all of the usual statistical tests referenced in the literature and hence generates high-quality random sequences, that is compact and easy to implement in practice, of portable design and offering reasonable execution times. Our procedure achieves those objectives through the use of a sequence of modular exponentiations followed by the application of Feistel-like boxes that mix up bits using a nonlinear function. The results of extensive statistical tests on sequences of about 2 40 bits in size generated by our algorithm are also presented. [ABSTRACT FROM AUTHOR]

In this paper, we propose a method of using Montgomery multiplication in the computation of binary Bailey–Borwein–Plouffe (BBP)-type formulas for mathematical constants. The most time-consuming part of the computation of a BBP-type formula is modular exponentiation. It is known that modular exponentiation can be performed efficiently using binary modular exponentiation and Montgomery multiplication. When computing a Montgomery multiplication in binary, the modulus of the modular exponentiation must be an odd number. However, if the denominator of the fraction in a binary BBP-type formula, excluding the power of the base, is an even number, then the modulus of the modular exponentiation is also an even number, so Montgomery multiplication cannot be used directly. The proposed method makes it possible to use Montgomery multiplication for binary BBP-type formulas even in such a case. [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]

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

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]

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]