## CryptoDB

### Santanu Sarkar

#### Publications

Year
Venue
Title
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2014
JOFC
2014
FSE
2012
CHES
2012
CHES
2010
EPRINT
In this paper we present some problems and their solutions exploiting lattice based root finding techniques. In CaLC 2001, Howgrave-Graham proposed a method to find the Greatest Common Divisor (GCD) of two large integers when one of the integers is exactly known and the other one is known approximately. In this paper, we present three applications of the technique. The first one is to show deterministic polynomial time equivalence between factoring $N$ ($N = pq$, where $p > q$ or $p, q$ are of same bit size) and knowledge of $q^{-1} \bmod p$. Next, we consider the problem of finding smooth integers in a short interval. The third one is to factorize $N$ given a multiple of the decryption exponent in RSA. In Asiacrypt 2006, Jochemsz and May presented a general strategy for finding roots of a polynomial. We apply that technique for solving the following two problems. The first one is to factorize $N$ given an approximation of a multiple of the decryption exponent in RSA. The second one is to solve the implicit factorization problem given three RSA moduli considering certain portions of LSBs as well as MSBs of one set of three secret primes are same.
2009
EPRINT
Let $N = pq$ be the product of two large primes. Consider CRT-RSA with the public encryption exponent $e$ and private decryption exponents $d_p, d_q$. It is well known that given any one of $d_p$ or $d_q$ (or both) one can factorize $N$ in probabilistic poly$(\log N)$ time with success probability almost equal to 1. Though this serves all the practical purposes, from theoretical point of view, this is not a deterministic polynomial time algorithm. In this paper, we present a lattice based deterministic poly$(\log N)$ time algorithm that uses both $d_p, d_q$ (in addition to the public information $e, N$) to factorize $N$.
2008
EPRINT
In this paper we revisit Wiener's method (IEEE-IT, 1990) of continued fraction (CF) to find new weaknesses in RSA. We consider RSA with $N = pq$, $q < p < 2q$, public encryption exponent $e$ and private decryption exponent $d$. Our motivation is to find out when RSA is insecure given $d$ is $O(n^\delta)$, where we are mostly interested in the range $0.3 \leq \delta \leq 0.5$. We use both the upper and lower bounds on $\phi(N)$ and then try to find out what are the cases when $\frac{t}{d}$ is a convergent in the CF expression of $\frac{e}{N - \frac{3}{\sqrt{2}} \sqrt{N} + 1}$. First we show that the RSA keys are weak when $d = N^\delta$ and $\delta < \frac{3}{4} - \gamma - \tau$, where $2q - p = N^\gamma$ and $\tau$ is a small value based on certain parameters. This presents additional results over the work of de Weger (AAECC 2002). We also discuss how the idea of Boneh-Durfee (Eurocrypt 1999) works better to find weak keys beyond the bound $\delta < \frac{3}{4} - \gamma - \tau$. Further we show that, the RSA keys are weak when $d < \frac{1}{2} N^\delta$ and $e$ is $O(N^{\frac{3}{2}-2\delta})$ for $\delta \leq \frac{1}{2}$. Using similar idea we also present new results over the work of Bl{\"o}mer and May (PKC 2004).
2008
EPRINT
We consider RSA with $N = pq$, $q < p < 2q$, public encryption exponent $e$ and private decryption exponent $d$. Boneh and Durfee (Eurocrypt 1999, IEEE-IT 2000) used Coppersmith's method (Journal of Cryptology, 1997) to factorize $N$ using $e$ when $d < N^{0.292}$, the theoretical bound. However, the experimental bound that has been reached so far is only $N^{0.280}$ for 1000 bits integers (and less for higher number of bits). The basic idea relied on LLL algorithm, but the experimental bounds were constrained by large lattice dimensions. In this paper we present theoretical results and experimental evidences to extend the bound of $d$ for which RSA is weak. This requires the knowledge of a few most significant bits of $p$ (alternatively these bits need to be searched exhaustively). We provide experimental results to highlight that the problem can be solved with low lattice dimensions in practice. Our results outperform the existing experimental results by increasing the bounds of $d$ and also we provide clear evidence that RSA with 1000 bit $N$ and $d$ of the order of $N^{0.3}$ can be cryptanalysed in practice from the knowledge of $N, e$.