Skip to main content

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
132 votes
7 answers
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 ...
Inaimathi's user avatar
  • 1,587
47 votes
4 answers
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: ...
Gilles 'SO- stop being evil''s user avatar
38 votes
7 answers
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 ...
mjs's user avatar
  • 483
10 votes
3 answers
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 ...
T.B's user avatar
  • 1,292
12 votes
1 answer
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$ ?
user61922's user avatar
  • 123
10 votes
1 answer
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 ...
Rick's user avatar
  • 103
9 votes
3 answers
9k 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 \...
SquareRootOfTwentyThree's user avatar
8 votes
2 answers
3k views

Prime factorization (102 digits)

I have a number that consists of 102 digits and I need to factor it. I ran it in alpertrom.com.ar, but it'll take up to 40 hours if I counted all right. Is there any way to make it by hand (stupid ...
user avatar
19 votes
1 answer
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 ...
mikeazo's user avatar
  • 38.7k
10 votes
2 answers
6k views

Is it proven that breaking RSA is equivalent to factoring as of 2021?

I can't find any publication that proves this.
Tomas's user avatar
  • 155
2 votes
2 answers
3k views

Factors of RSA modulus

In the article A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, the original RSA article, it is mentioned that Miller has shown that n (the modulus) can be factored using any ...
user3343768's user avatar
97 votes
4 answers
45k views

Does Schnorr's 2021 factoring method show that the RSA cryptosystem is not secure?

Claus Peter Schnorr recently posted a 12-page factoring method by SVP algorithms. Is it correct? It says that the algorithm factors integers $N \approx 2^{400}$ and $N \approx 2^{800}$ by $4.2 \cdot ...
Blanco's user avatar
  • 1,622
24 votes
4 answers
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 ...
DanBeale's user avatar
  • 343
7 votes
1 answer
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 ...
rt_mn's user avatar
  • 83
19 votes
5 answers
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 ...
javic's user avatar
  • 293
18 votes
3 answers
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, ...
kodlu's user avatar
  • 22.7k
12 votes
2 answers
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 ...
Naka Wai's user avatar
  • 163
9 votes
1 answer
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 certified smart cards: Coppersmith in the wild. In the last slide, it was ...
meta_warrior's user avatar
8 votes
3 answers
2k views

Quadratic residuosity problem reduction to integer factorization

How can one show how to reduce the quadratic residuosity problem to an integer factorization?
Faith's user avatar
  • 455
7 votes
1 answer
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 ...
Faith's user avatar
  • 455
6 votes
1 answer
801 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?
Xiaopeng Zhao's user avatar
12 votes
2 answers
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$?
boran's user avatar
  • 131
2 votes
1 answer
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 ...
Yunus Karakaya's user avatar
2 votes
1 answer
937 views

Factoring RSA weak modulus

Given a public key for RSA, I have extracted the modulus which looks like this : ...
Mzem's user avatar
  • 75
0 votes
0 answers
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 ...
bd55's user avatar
  • 33
-1 votes
1 answer
100 views

Is there a fast way to solve $k = n \cdot g^a \mod P$? (get $a$ for unknown $n$)

Would a factor besides the normal discrete logarithm problem increase or decrease the solving time? $k = n \cdot g^a \mod P$ with given $k,g,P$ and the knowledge $P= 2 \cdot N \cdot f+1$, while $...
J. Doe's user avatar
  • 453
30 votes
1 answer
5k views

How was this 2048 bit number factored so fast?

I'm working on a CTF. The challenge is to get the contents of an encrypted message given the ciphertext and the 2048-bit RSA public key. I did finally get the flag after a few hours, but I'm still not ...
rainbowkitty227's user avatar
16 votes
1 answer
21k 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 ...
R1w's user avatar
  • 1,960
14 votes
2 answers
17k 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 ...
Jus12's user avatar
  • 1,659
12 votes
3 answers
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 ...
fgrieu's user avatar
  • 142k
10 votes
2 answers
548 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 ...
BoFatom's user avatar
  • 171
9 votes
3 answers
10k 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 ...
user56036's user avatar
  • 101
7 votes
1 answer
541 views

When is factoring semi-primes thought to be hard?

In Lattice Cryptography, problems like LWE or SIS have relatively easy to specify distributions that are thought to be average case hard. I'm curious what specific distributions on semi-primes $(p,q)$ ...
Mark Schultz-Wu's user avatar
  • 13.5k
7 votes
1 answer
604 views

How fast is Factorization reduced to a Discrete Logarithm?

Given a RSA modulus $n$, which is the product of two safe primes: \begin{align*} P &= 2p + 1 \quad\quad\quad Q = 2q + 1 \\ n &= P \cdot Q = 4p q + 2 p + 2 q + 1 \end{align*} The ...
RobinLinus's user avatar
6 votes
1 answer
2k views

How does the Number Field Sieve find the target number for Diffie-Hellman?

I have read some papers relating to the Number Field Sieve, but I could not figure out how this algorithm helps in Logjam, or even what is meant by the number field. What is this? What is meant by ...
Hamm's user avatar
  • 169
6 votes
2 answers
5k 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 ...
yydl's user avatar
  • 699
3 votes
1 answer
359 views

Does choosing N to be product of safe primes avoid William's p+1 factoring attack on RSA?

In this post, I found that choosing RSA modulus $N$ to be product of safe primes avoids Willam's $p + 1$ factoring attack. Suppose $N = p \cdot q$, where $p$, $q$, $(p-1)/2$ and $(q-1)/2$ are primes. ...
satya's user avatar
  • 1,414
3 votes
1 answer
157 views

Logjam-style attack on Factoring?

We're all aware of the Logjam attack, which is known as "FREAK on discrete logarithms". The attack works by doing a large pre-computation step, which needs only to be done once per field and then ...
SEJPM's user avatar
  • 46.1k
3 votes
1 answer
216 views

What is the (classical) algorithm of choice for finding discrete logarithms in composite-moduli groups?

I've recently written an answer on how to find the factorization of a $n$ if we can find the order(s) of elements in the associated group $\mathbb Z_n^*$. This also lead me to Shor's algorithm which ...
SEJPM's user avatar
  • 46.1k
3 votes
1 answer
1k views

Fermat's factorization method on weak RSA modulus

Given a public key for RSA, I have extracted the modulus which looks like this: ...
Mzem's user avatar
  • 75
3 votes
0 answers
307 views

How can the Number Field Sieve attack the discrete log in $\mathbb Z_p^*$ of DSA?

The Digital Signature Algorithm (DSA) uses $L$-bit prime $p$ and $N$-bit prime $q$ with $q| p-1$, i.e., $p = r\cdot q +1$ ( Schnorr group if $r>2$ and safe prime if $r=2$). In a way, the security ...
kelalaka's user avatar
  • 49k
3 votes
0 answers
268 views

RSA security assumptions - does breaking the DLP also break RSA? [duplicate]

Possible Duplicate: Would the ability to efficiently find Discrete Logs have any impact on the security of RSA? I'm wondering if breaking the DLP, that is the basis for ElGamal and DSA, would ...
MartinSuecia's user avatar
  • 2,450
3 votes
1 answer
4k views

Factoring large $N$ given oracle to find square roots modulo $N$

When $p$ and $q$ are distinct odd primes and $N = pq$, the points in $\mathbb Z_N^\ast$ have either zero or four square roots. A quarter of the points have four square roots; the rest have no square ...
Tom Corless's user avatar
3 votes
1 answer
201 views

Is Fermat's Factorization Method used in any practical application?

Is there any use for Fermat's Factorization Method in the world of cryptography? I see that several algorithms are based on it, such as the quadratic sieve and general number field sieve. I understand ...
Raine's user avatar
  • 33
2 votes
1 answer
162 views

Does knowing modular eth roots help in factoring n?

Consider $x^e \equiv a\pmod n$, given $n$, $a$, and $e>2$, with $n$ being a composite integer and unknown $x$. Can a hypothetical function $f(a)=x$, an $eth$ root extractor, be used / adapted to ...
Ruan Sunkel's user avatar
2 votes
1 answer
612 views

Pollard's $(p - 1)$ factorization method runtime

Wondering if anyone knows a good reference for Pollard's $p-1$ algorithm's runtime? I was looking on the Wikipedia page and the runtime cited there is $\mathcal{O}(B\cdot \log B\cdot \log^2 n)$. ...
Dead_Ling0's user avatar
2 votes
1 answer
2k views

Attack for RSA 1024 bit with Low Public Exponent

I am facing a challenge at university. Our teacher give us the challenge to try to break an RSA 1024 bit. We have public modulus N and public exponent e (0x03), we don't know the padding. We have a ...
itseeder's user avatar
  • 271
2 votes
1 answer
809 views

Breaking RSA with P,Q LSB bits

Let's say we have a certain amount of LSB bits of P and Q and we want to fully reconstruct them given N=P*Q. I know this problem was studied in literature by Coppersmith and that Lattice methods are ...
gram's user avatar
  • 31
2 votes
1 answer
1k views

Square roots, prime factorization

I´m stuck in my homework and since its homework, I would rather get some hints than full solution. The problem goes: factorize n = 88416763 in case that you know that the square roots of 51733469 (...
dante's user avatar
  • 23
1 vote
0 answers
112 views

Question about sequence length/count/security of $x\mapsto x^\alpha \mod (N=Q\cdot R)$, with $Q=2q_1q_2+1$ and $R=2r_1r_2+1$ and $\alpha = 2q_2r_2$

Given a number $N$ with $$N=Q\cdot R$$ $$Q=2\cdot q_1 \cdot q_2+1$$ $$R=2\cdot r_1\cdot r_2+1$$ with different primes $P,Q,q_1,q_2,r_1,r_2$. If we now choose an exponent $\alpha$ containing prime ...
J. Doe's user avatar
  • 453