## CryptoDB

### Santanu Sarkar

#### Affiliation: Chennai Mathematical Institute, Chennai, India

#### Publications

**Year**

**Venue**

**Title**

2015

EPRINT

2015

EPRINT

2012

CHES

2010

EPRINT

Some Applications of Lattice Based Root Finding Techniques
Abstract

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

Deterministic Polynomial-Time Equivalence of Computing the CRT-RSA Secret Keys and Factoring
Abstract

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

Revisiting Wiener's Attack -- New Weak Keys in RSA
Abstract

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

RSA Cryptanalysis with Increased Bounds on the Secret Exponent using Less Lattice Dimension
Abstract

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

#### Coauthors

- Avishek Adhikari (1)
- Anubhab Baksi (2)
- Subhadeep Banik (1)
- Prakash Dey (1)
- Pramit Dey (1)
- Subhamoy Maitra (11)
- Willi Meier (1)
- Goutam Paul (2)
- Sumanta Sarkar (1)
- Sourav Sen Gupta (2)