# Questions tagged [factoring]

The decomposition of an integer number to the product of other integers. Algorithms such as RSA are based on the premise that no practical way has been found was to factorize large integers when they have been produced by multiplying two large primes.

54 questions
Filter by
Sorted by
Tagged with
89k views

### How big an RSA key is considered secure today?

I think 1024 bit RSA keys were considered secure ~5 years ago, but I assume that's not true anymore. Can 2048 or 4096 keys still be relied upon, or have we gained too much computing power in the ...
• 1,587
35k views

### Security strength of RSA in relation with the modulus size

NIST SP 800-57 §5.6.1 p.62–64 specifies a correspondence between RSA modulus size $n$ and expected security strength $s$ in bits: ...
7k views

### Is it feasible to build an index of prime factors?

Would it be possible to break an RSA key, in for example 1 week of time, if the cracker have already spent X number of years building an index of primes by performing every permutation of existing ...
• 483
8k views

### Is knowing the private key of RSA equivalent to the factorization of $N$?

Given the RSA modulus $N$ the fastest method to factor it is of sub-exponent order. But, now if I know the private key $d$ of RSA, does that mean I can factor $N$ efficiently?. It intuitively seems ...
• 1,292
5k views

### Algorithm to factorize $N$ given $N$, $e$, $d$

I have an RSA public key (public modulus $N$ and public exponent $e$), and the private exponent $d$ of matching private key. How can I compute $p$ and $q$, the primes factor of $N$ ?
• 123
5k views

### Why can ECC key sizes be smaller than RSA keys for similar security?

I understand how ECC is based on the discrete log problem and RSA on integer factorization. I've read several references that show how a solution to either of these problems can typically be adapted ...
• 103
9k views

• 1,622
5k views

### What is the progress on the MIT LCS35 Time Capsule Crypto-Puzzle?

Ron Rivest posed a puzzle in 1999. MIT LCS35 Time Capsule Crypto-Puzzle. The problem is to compute $2^{2^t} \pmod n$ for specified values of $t$ and $n$. Here $n$ is the product of two large ...
• 343
3k views

### Why should the primes used in RSA be distinct?

The two primes $p$ and $q$ part of the public key need to be distinct. What's the reason for them to be distinct? Is it because factorization of $p^2$ where $p$ is a prime is relatively easier, or is ...
• 83
4k views

### RSA leak bits to factor N

Suppose you randomly generate large primes p and q as in RSA, and then tell me N=pq but not p or q. Then, you would like to actually let me factor N, except you should tell me as few bits of ...
• 293
6k views

### Quantum Computing Used to Break RSA by "fixing" Schnorr's Recent Factorization Claim?

There is a claim by Chinese researchers making the rounds (Schneier's blog here) that RSA can be broken by Quantum Computers. The paper is on arXiv. Wading through the discussion in Schneier's blog, ...
• 22.7k
3k views

### uniqueness of the RSA public modulus

What is the probability that two separate RSA public moduli are the same? For example, consider a 2048-bit modulus. The number seems to be huge, but the choice for prime factors p and q is much more ...
• 163
1k views

### Adi Shamir's secret database of all primes

I was going through these presentation slides (PDF) on Crypto 2013. It summarizes the paper, Factoring RSA keys from certiﬁed smart cards: Coppersmith in the wild. In the last slide, it was ...
• 469
2k views

### Quadratic residuosity problem reduction to integer factorization

How can one show how to reduce the quadratic residuosity problem to an integer factorization?
• 455
7k views

### Reduction of Integer factorization to Discrete logarithm problem

I was reading Eric Bach paper entitles Discrete logarithms and factoring, in which he states the following reductions: solving the integer factorization problem suffices to solve the discrete ...
• 455
801 views

Let $N=pq$ where $p$ and $q$ are safe primes. If the adversary knows the inverse of $p$ mod $q$ and the inverse of $q$ mod $p$, can this help him factor $N$ or break the textbook RSA?
5k views

### Safe primes in RSA

It's my understanding that there's no longer a requisite of safe primes for $q$ and $p$ when choosing a RSA modulus. How is it that this does not change the hardness of factoring $N$?
• 131
137 views

### Is RSA-OAEP secure against Shor's factoring algorithm

I've seen in this answer Can Shor's algorithm compromise RSA when both the public and private key are secret? that if textbook RSA is used (deterministic) the Shor's algorithm can reak it. However, if ...
937 views

### Factoring RSA weak modulus

Given a public key for RSA, I have extracted the modulus which looks like this : ...
• 75
339 views

### RSA : Is there a way to compute phi(n) or N itself if we only know e, d and a ciphertext?

I am trying to solve a problem where private key exponent d, ciphertext c, and public key exponent e (65537) are known. How can I calculate φ(n) or n itself? An extended version of the problem would ...
• 33