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.

Filter by
Sorted by
Tagged with
117
votes
7answers
69k 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 ...
44
votes
4answers
23k 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: ...
32
votes
6answers
6k 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 ...
25
votes
2answers
6k views

Why is it not possible to increase the size of RSA keys indefinitely?

According to this primer on elliptic curves by Ars Technica, when composite numbers get "too" big, they become easier to factorize with Quadratic Sieve and General Number Field Sieve. While this is ...
20
votes
4answers
4k 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 ...
19
votes
1answer
664 views

Quantum complexity of LWE

As per my understanding, LWE is quantum secure because there is no known quantum algorithm to solve LWE in polynomial time. Due to the reductions given by Regev et al., if there is any algorithm that ...
17
votes
1answer
2k views

Why are elliptic curve variants of RSA “chiefly of academic interest”?

Yesterday I was thinking about elliptic curve variants of popular protocols/algorithms (ECDH, ECES[1], etc) and the thought occured that I had never seen an elliptic curve variant of RSA. My ...
17
votes
2answers
1k views

RSA factorization for special primes $p$ and $q$

I want to factorize the modulus $n = pq$ knowing that $p$ and $q$ are not random, but constructed based on integer numbers $a$ and $b$ as following ($a$ and $b$ are not given): $$p = a^2 + b^2, \...
16
votes
5answers
2k 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 ...
16
votes
1answer
646 views

Is this paper's technique for factoring RSA 2048 with noisy qubits realistic?

A paper titled How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits has just come out which proposes a technique to factor RSA keys with moduli up to 2048 bits with a design ...
15
votes
3answers
2k views

Are there asymmetric cryptographic algorithms that are not based on integer factorization and discrete logarithm?

In the computer security class (in which cryptography is a big chapter) that I took, I remembered the professor said about current asymmetric cryptography algorithms are based on integer factorization ...
14
votes
0answers
237 views

Fewest qubits required for the discrete logarithm problem and integer factorization

According to a paper from 2002, the most efficient circuit to factor an $n$-bit integer requires $2n+3$ qubits and $O(n^{3}\lg(n))$ elementary quantum gates, assuming ideal qubits. Later on, according ...
13
votes
3answers
3k views

What happens for factoring algorithms if P=NP?

If someone ever demonstrates that P=NP, will it give us a polynomial factoring algorithm, or will it only tell us that such an algorithm exists, but we still have to find it?
13
votes
1answer
8k views

How long does it take to crack RSA 1024 with a PC?

Using an Intel Core i5 CPU, how long does it take to crack RSA using a key size of 1024 bit (generated using a secure key pair generation function)? Suppose for instance that we have thousands of ...
13
votes
2answers
13k views

Why has the RSA factoring challenge been withdrawn?

Wikipedia states that RSA challenge has been withdrawn. Does it mean that an efficient factoring algorithm is "just around the corner"? or are there some other reasons? If the challenge was still ...
12
votes
2answers
592 views

How can I create an RSA modulus for which no one knows the factors?

It's easy to create an RSA modulus where almost no one knows the factors: for example, I can generate two 1024-bit primes $p$ and $q$ and set $n=pq$. If I publish $n$, I will be the only person in ...
11
votes
3answers
4k views

Which algorithms are used to factorize large integers?

Even if RSA decided to cancel the Factoring Challenge, it seems that some teams keep working on it. According to Wikipedia, RSA-768 has been factored in late 2009. What are the current large integer ...
11
votes
1answer
2k 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$?
11
votes
1answer
191 views

Is it easy to factorize a number of the form $n = t^{2} \cdotp p$?

Is it easy to factorize a number of the form $n = t^{2} \cdotp p$, where $t$ and $p$ are large primes?
10
votes
2answers
291 views

What role plays Quantum Fourier Transformation in Shor's integer factorization algorithm?

I cannot seem to understand the role or goal of Quantum Fourier Transformation in Shor's integer factorization algorithm. Is it used to collapse all quantum states into one, in which it has a factor ...
10
votes
3answers
2k views

In the Quadratic Sieve, why restrict the factor base?

In the Quadratic Sieve, when factoring a number $N$, many descriptions and most implementations select as the factor base the set of small primes $p_j$ less than some bound $B$ restricted to having ...
10
votes
1answer
1k views

What is the difference between Shor's algorithm for factoring and Shor's algorithm for logarithm

There is a paper from Peter W. Shor from 1994: http://www.csee.wvu.edu/~xinl/library/papers/comp/shor_focs1994.pdf "Algorithms for Quantum Computation: Discrete Logarithms and Factoring", and I have a ...
9
votes
3answers
5k views

What is the fastest integer factorization to break RSA?

I read on Wikipedia, the fastest Algorithm for breaking RSA is GNFS. And in one IEEE paper (MVFactor: A method to decrease processing time for factorization algorithm), I read the fastest algorithms ...
9
votes
2answers
2k 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 ...
9
votes
1answer
3k 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 ...
9
votes
3answers
6k views

RSA and prime difference

It is known that the two prime factors $p$ and $q$ of an RSA modulus $n$ should not be too close to each other, otherwise an attacker may factor the modulus. In other words, $\Delta = \left| p - q \...
9
votes
1answer
1k views

What does “Inverting the RSA function is as hard as factoring” mean (a rigorous explanation or intuitive will do)?

I was reading that a current open problem is if inverting the RSA function is as hard as factoring. Does this mean that, its an open problem whether, if given a subroutine that computes in ...
9
votes
0answers
587 views

RSA factorization with special primes

Suppose that primes for RSA modulus are generated using formula: $P_i(x,y) = \operatorname{next\_prime}(x^{z_i}+y^{z_i}) = x^{z_i}+y^{z_i}+d_i$ where $x,y$ are unknown random numbers with size 128 ...
8
votes
3answers
4k 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 ...
8
votes
1answer
969 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 certified smart cards: Coppersmith in the wild. In the last slide, it was ...
8
votes
1answer
233 views

Factoring two RSA moduli $N_i=p_i\cdot q_i$ knowing that $p_2=p_1+2$?

It is given two RSA moduli $N_1$ and $N_2$, known to be of the form $N_i=p_i\cdot q_i$, with $p_i$ and $q_i$ unknown primes, and such that $p_2=p_1+2$. Can we make use of that relation to factor the ...
8
votes
0answers
160 views

Time-memory tradeoffs in Shor's algorithm

Can a quantum computer with insufficient qubits to factor an integer of a given size make any progress in factoring it? For example, what if a quantum computer is only one qubit short of what is ...
7
votes
2answers
899 views

RSA: Letting $p$ and $q$ have different bit-size

I am aware that there are concerns if $p$ and $q$ are close i.e. $\Delta=|p-q|$ can't be too small. But I would like to know if there are any known attacks for cases where $p$ and $q$ take on ...
7
votes
2answers
448 views

Calculating RSA Public Modulus from Private Exponent and Public Exponent

If I know the private and public exponents ($d$ and $e$) of an RSA key pair, is it possible to (efficiently) calculate the public modulus $n$?
7
votes
1answer
1k 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$ ?
7
votes
2answers
2k views

Carmichael number factoring

Unsure whether this is the right forum for this question, worth a try. The task im faced with is to implement a poly-time algorithm that finds a nontrivial factor of a carmichael number. Many ...
7
votes
2answers
983 views

RSA: revealing the modulus factorization by choosing a bad message

I started reading the book Cryptanalysis of RSA and its variants by M. Jason Hinek and I stumbled upon a phrase that intrigued me: plaintext messages that are relatively prime to the modulus (i.e....
7
votes
1answer
90 views

Is phi-hiding assumption as hard as integer factorization?

Phi-hiding assumption can be simply stated as (wrt hardness) It is difficult to find small factors of $\varphi(m)$ where $m$ is a number whose factorization is unknown and $\varphi$ is Euler's ...
7
votes
1answer
189 views

Blinding to mask private key operations

Blinding is often used to mask private key operations when the underlying problem is integer factorization. For example, it's used in both RSA and Rabin-Williams signature schemes. This presumes ...
7
votes
0answers
89 views

Hardness of iterated squaring in Pailler group

The (computational) problem of iterated squaring (IS) in the RSA group is defined as follows, where $\leftarrow$ denotes sampling uniformly at random: Input: $(N,x,T)$, where $N$ is the RSA modulus, $...
6
votes
2answers
3k views

How to calculate the time it'll take to crack RSA or DH?

Sometimes the easiest way to describe security of a type of cryptography is to say that "the time it takes to solve for an x-bit key would be y years". How would one go about doing such a calculation ...
6
votes
3answers
493 views

Can Shor's algorithm factor multi-prime numbers?

I know that Shor's algorithm can factor semi-primes ($N = p \times q \space, \{p, \space q \in \Bbb{P} \space \vert \space p, \space q \gt 0 \} $). Assuming that all prime numbers are so large that ...
6
votes
2answers
214 views

Effect of $L_n[1/4,c]$ integer factorization on RSA-2048

Using the L-notation, integer factorization of an integer $n$ has the best known complexity of $L_n[1/3,c]$ using general number field sieve. Would discovery of an algorithm with complexity $L_n[1/4,c]...
6
votes
2answers
255 views

Are factorization algorithms parallelizable?

I was reading about the Blum-Blum-Shub random number generator, and its security depends on the hardness of factoring very large numbers (like many things in crypto do). I'm just wondering, if I have ...
6
votes
1answer
266 views

About integer factorization

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?
6
votes
0answers
172 views

What are the theoretical memory requirements for these factoring algotihms?

Given an $n$ bit integer quadratic sieve takes $L(\frac12,1+o(1))$ time and number field sieve takes $L(\frac13,1.922)$ time where $L$ notation is given in https://en.wikipedia.org/wiki/L-notation. ...
5
votes
3answers
1k views

Quadratic residuosity problem reduction to integer factorization

How can one show how to reduce the quadratic residuosity problem to an integer factorization?
5
votes
2answers
1k views

Why is Rabin encryption equivalent to factoring?

I don't understand the proof of equivalence I've read everywhere (e.g., in Rabin's paper or on Wikipedia). Here's my objection: let's say you have a Rabin decryption oracle that takes ...
5
votes
2answers
921 views

Public key crypto without modular arithmetic?

This comment from Reddit math, in response to a statement about how people can communicate secrets to each other with a third party listening, has a very small, simple example of public key ...
5
votes
3answers
489 views

Is it possible to check if a number is the product of two primes without factorizing it?

I have a large number which I suspect may be a private RSA key (although its size, at 613 bits, seems a bit unorthodox). I have started to run a factorization algorithm on it, and after a few hours ...

1
2 3 4 5