Cryptanalysis of variants of RSA with multiple small secret exponents
In this paper, we analyze the security of two variants of the RSA public key cryptosystem where multiple encryption and decryption exponents are used with a common modulus. For the most well known variant, CRT-RSA, assume that n encryption and decryption exponents (el, dpl, dql), where l = 1, …, n, are used with a common CRT-RSA modulus N. By utilizing a Minkowski sum based lattice construction and combining several modular equations which share a common variable, we prove that one can factor N when (Formula presented) for all l = 1, …, n. We further improve this bound to (Formula presented) for all l = 1, …, n. Moreover, our experiments do better than previous works by Jochemsz-May (Crypto 2007) and Herrmann-May (PKC 2010) when multiple exponents are used. For Takagi’s variant of RSA, assume that n key pairs (el, dl) for l = 1, …, n are available for a common modulus N = prq where r ≥ 2. By solving several simultaneous modular univariate linear equations, we show that when (Formula presented), for all l = 1, …, n, one can factor the common modulus N.
Revisiting orthogonal lattice attacks on approximate common divisor problems
In this paper, we revisit three existing types of orthogonal lattice (OL) attacks and propose optimized cases to solve approximate common divisor (ACD) problems. In order to reduce both space and time costs, we also make an improved lattice using the rounding technique. Further, we present asymptotic formulas of the time complexities on our optimizations as well as three known OL attacks. Besides, we give specific conditions that the optimized OL attacks can work and show how the attack ability depends on the blocksize β in the BKZ-β algorithm.
Solving a class of modular polynomial equations and its relation to modular inversion hidden number problem and inversive congruential generator
In this paper we revisit the modular inversion hidden number problem (MIHNP) and the inversive congruential generator (ICG) and consider how to attack them more efficiently. We consider systems of modular polynomial equations of the form aij+bijxi+cijxj+xixj=0(modp) and show the relation between solving such equations and attacking MIHNP and ICG. We present three heuristic strategies using Coppersmith’s lattice-based root-finding technique for solving the above modular equations. In the first strategy, we use the polynomial number of samples and get the same asymptotic bound on attacking ICG proposed in PKC 2012, which is the best result so far. However, exponential number of samples is required in the work of PKC 2012. In the second strategy, a part of polynomials chosen for the involved lattice are linear combinations of some polynomials and this enables us to achieve a larger upper bound for the desired root. Corresponding to the analysis of MIHNP we give an explicit lattice construction of the second attack method proposed by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001. We provide better bound than that in the work of PKC 2012 for attacking ICG. Moreover, we propose the third strategy in order to give a further improvement in the involved lattice construction in the sense of requiring fewer samples.
Analysis of hidden number problem with hidden multiplier
In Crypto 1996, the Hidden Number Problem was introduced by Boneh and Venkatesan. Howgrave-Graham, Nguyen and Shparlinski (Mathematics of Computation 2003) generalized this problem and called it Hidden Number Problem with Hidden Multiplier (HNPHM). It has application in security analysis of timed-release crypto. They proposed a polynomial time algorithm to solve HNPHM. They showed that one can solve it if absolute error is less than m0.20 for some positive integer m. They improved this bound up to m0.25 heuristically. It was also proved that one can not solve HNPHM if error is larger than m0.5. In this paper, we show that one can solve HNPHM in polynomial time heuristically if error is bounded by m0.5.
Cryptanalysis of multi-prime Φ -hiding assumption
In Crypto 2010, Kiltz, O’Neill and Smith used m -prime RSA modulus N with m ≥ 3 for constructing lossy RSA. The security of the proposal is based on the Multi-Prime Φ -Hiding Assumption. In this paper, we propose a heuristic algorithm based on the Herrmann-May lat- tice method (Asiacrypt 2008) to solve the Multi-Prime Φ -Hiding Problem when prime e > N2/3M. Further, by combining with mixed lattice tech- niques, we give an improved heuristic algorithm to solve this problem when prime e > N2/3M-1/4m2. These two results are verified by our experiments. Our bounds are better than the existing works.
Improving Bounds on Elliptic Curve Hidden Number Problem for ECDH Key Exchange
Elliptic Curve Hidden Number Problem (EC-HNP) was first introduced by Boneh, Halevi and Howgrave-Graham at Asiacrypt 2001. To rigorously assess the bit security of the Diffie–Hellman key exchange with elliptic curves (ECDH), the Diffie–Hellman variant of EC-HNP, regarded as an elliptic curve analogy of the Hidden Number Problem (HNP), was presented at PKC 2017. This variant can also be used for practical cryptanalysis of ECDH key exchange in the situation of side-channel attacks. In this paper, we revisit the Coppersmith method for solving the involved modular multivariate polynomials in the Diffie–Hellman variant of EC-HNP and demonstrate that, for any given positive integer d, a given sufficiently large prime p, and a fixed elliptic curve over the prime field Fp, if there is an oracle that outputs about 1d+1 of the most (least) significant bits of the x-coordinate of the ECDH key, then one can give a heuristic algorithm to compute all the bits within polynomial time in log 2p. When d> 1, the heuristic result 1d+1 significantly outperforms both the rigorous bound 56 and heuristic bound 12. Due to the heuristics involved in the Coppersmith method, we do not get the ECDH bit security on a fixed curve. However, we experimentally verify the effectiveness of the heuristics on NIST curves for small dimension lattices.
Revisiting Prime Power RSA
Recently Sarkar (DCC 2014) has proposed a new attack on small decryption exponent when RSA Modulus is of the form N=prq for r≥2. This variant is known as Prime Power RSA. The work of Sarkar improves the result of May (PKC 2004) when r≤5. In this paper, we improve the work of Sarkar when 2
New Results on Modular Inversion Hidden Number Problem and Inversive Congruential Generator
The Modular Inversion Hidden Number Problem (MIHNP), introduced by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001, is briefly described as follows: Let$${\mathrm {MSB}}_{\delta }(z)$$ refer to the$$\delta $$ most significant bits of z. Given many samples$$\left(t_{i}, {\mathrm {MSB}}_{\delta }((\alpha + t_{i})^{-1} \bmod {p})\right) $$ for random$$t:i \in \mathbb {Z}_p$$, the goal is to recover the hidden number$$\alpha \in \mathbb {Z}_p$$. MIHNP is an important class of Hidden Number Problem. In this paper, we revisit the Coppersmith technique for solving a class of modular polynomial equations, which is respectively derived from the recovering problem of the hidden number$$\alpha $$ in MIHNP. For any positive integer constant d, let integer$$n=d^{3+o(1)}$$. Given a sufficiently large modulus p,$$n+1$$ samples of MIHNP, we present a heuristic algorithm to recover the hidden number$$\alpha $$ with a probability close to 1 when$$\delta /\log _2 p>\frac{1}{d\,+\,1}+o(\frac{1}{d})$$. The overall time complexity of attack is polynomial in$$\log _2 p$$, where the complexity of the LLL algorithm grows as$$d^{\mathcal {O}(d)}$$ and the complexity of the Gröbner basis computation grows as$$(2d)^{\mathcal {O}(n^2)}$$. When$$d> 2$$, this asymptotic bound outperforms$$\delta /\log _2 p>\frac{1}{3}$$ which is the asymptotic bound proposed by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001. It is the first time that a better bound for solving MIHNP is given, which implies that the conjecture that MIHNP is hard whenever$$\delta /\log _2 p<\frac{1}{3}$$ is broken. Moreover, we also get the best result for attacking the Inversive Congruential Generator (ICG) up to now.