Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
81 votes
Accepted

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

No. If the claim was true, then there would be an extremely simple way to prove it: $10^{10}$ arithmetic operations is nothing. There are tons of 800-bit factoring challenges available online. The ...
Geoffroy Couteau's user avatar
55 votes
Accepted

Cracking RSA (or other algorithms) manually by a savant

Mental calculators do not have the result appearing in their brain by staring at the input. They follow some (broadly sequential) algorithm┬╣. And computers vastly outperform them when they use the ...
fgrieu's user avatar
  • 142k
44 votes

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

Big issue at the bottom of page 2 where the determinant is quoted as $N^{n+1}\frac{n(n+1)}2 \ln n$ when it should be $N^{n+1} n! \ln n$. If this formula is used directly in the numerical estimates ...
Daniel S's user avatar
  • 23.9k
43 votes
Accepted

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

I've never heard that RSA becomes less secure when the modulus grows. Obviously the strength doesn't grow as fast as the number of bits, but that only means that it grows sub-exponentially. If it ...
Maarten Bodewes's user avatar
  • 92.9k
43 votes
Accepted

How was this 2048 bit number factored so fast?

That number was so quick to factor because its factors are extremely close together, i.e., it factors as $\left(\lfloor\sqrt{n}\rfloor + 70\right)\left(\lfloor\sqrt{n}\rfloor - 68\right)$. Some ...
Samuel Neves's user avatar
  • 12.6k
28 votes
Accepted

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

2) Has anyone claimed to make any progress with this challenge? Ah that question I can answer now... I found the solution on the 15th of April 2019 and sent it to the MIT's CSAIL on the 16th of ...
TacticalCoder's user avatar
26 votes

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

I don't understand at all what this claim is on the website. The claim that RSA becomes very expensive for large $N$ is true, but to say that the gap between encryption/decryption cost and factoring ...
Yehuda Lindell's user avatar
24 votes

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

The error in upper bounding the determinant of the matrix $\mathbf{R}_{n,f}$ by $$N^{n+1} \frac{n(n+1)}{2} \ln N$$ instead of by $$N^{n+1} n! \ln N$$ seems to lead to an error in upper bounding the ...
kodlu's user avatar
  • 22.6k
22 votes

Cracking RSA (or other algorithms) manually by a savant

Your thinking is against the common sense in cryptography and computing. And to be blunt, it's blatant pseudoscience. Human brains and the neurons within operate on scalar states. While it's arguable ...
DannyNiu's user avatar
  • 9,361
21 votes
Accepted

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

RSA-768 took 2000 years of 2.2Ghz single-core Opteron from the year 2009. DJB et al wrote in 2013 (see page 30) (see also: 29C3: FactHacks (EN); slide 87/112; about 10 minutes) that RSA-1024 would ...
Z.T.'s user avatar
  • 824
17 votes

Safe primes in RSA

First we may want RSA primes to be something like a safe prime, ie a prime $p$ where $(p-1)/2$ is prime as well. Back in 1974 Pollard found an algorithm to factor moduli whereby you can factor $N=pq$ ...
SEJPM's user avatar
  • 46.1k
17 votes

What is the efficiency of the new Crown Sterling semiprime factoring method?

The bozos at Clown Sterling have adapted the advanced technology of bogosort to factoring: randomly blow a candidate solution out your nose and check whether it works. For a semiprime $n$ chosen by ...
Squeamish Ossifrage's user avatar
17 votes
Accepted

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

There is no proof that the integer factorization is computationally difficult and similarly, there is no proof that the RSA problem is similarly difficult. The RSA problem RSA problem is finding the $...
kelalaka's user avatar
  • 48.7k
17 votes
Accepted

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

TL;DR This appears unlikely to work at scale, at least with current parameter choices. There's a classical post-processing step which is worse than the quadratic sieve in complexity unless the quantum ...
Daniel S's user avatar
  • 23.9k
16 votes
Accepted

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

Algorithm An RSA modulus $N$ product of large distinct primes can be factored given any non-zero multiple $f$ of $\lambda(N)$ (where $\lambda$ is the Carmichael function), including $f=\varphi(N)$ (...
fgrieu's user avatar
  • 142k
15 votes

What happens for factoring algorithms if P=NP?

Proving P=NP would not necessarily give you an algorithm, because there are many different methods to prove something (i.e. Direct proof, Proof by contradiction, etc.). But it is shown that if you ...
AleksanderCH's user avatar
  • 6,463
15 votes
Accepted

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

I'm one of the authors of the paper. In order to make the paper more approachable, we factored each major optimizations out into its own paper. There are three of these sub-papers, and they each ...
Craig Gidney's user avatar
15 votes
Accepted

Prime factorization (102 digits)

Your 102-digit nuber is two digits more than the first RSA challenge RSA-100 that has 330-bit. This can be easily achieved with existing libraries like; CADO-NFS ; http://cado-nfs.gforge.inria.fr/ ...
kelalaka's user avatar
  • 48.7k
13 votes

Quadratic residuosity problem reduction to integer factorization

Factoring $\longrightarrow$ square roots. Computing square roots modulo a prime $p$ is easy: if $p \equiv 3 \pmod 4$ and $a$ is a quadratic residue modulo $p$, then $a^{(p + 1)/4}$ is a square root of ...
Squeamish Ossifrage's user avatar
12 votes
Accepted

What is the fastest integer factorization to break RSA?

The IEEE paper is silly. The factorization method they give is quite slow, except for rare cases. For example, in their table 1, where they proudly show that their improved algorithm takes 653.14 ...
poncho's user avatar
  • 148k
12 votes
Accepted

Does the security of RSA come from just the carries in multiplication?

might have the terminology wrong when I say "GF(2) polynomial multiplication" You are thinking of multiplication in the ring of binary polynomials, that is polynomials with coefficients in ...
fgrieu's user avatar
  • 142k
12 votes

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

No, it's not proved that solving the RSA problem [that is, finding $x$ from the value of $x^e\bmod n$ for unknown random integer $x$ in interval $[0,n)$, and $(n,e)$ a proper RSA key ] is equivalent ...
fgrieu's user avatar
  • 142k
12 votes

Cracking RSA (or other algorithms) manually by a savant

For human brains, it's all too easy to ignore the depth of the 2048+ bit figure. Let's do some engineering guesstimation exercise to illustrate. The original post by @derjack measures almost 700 ...
ulidtko's user avatar
  • 349
12 votes
Accepted

RSA given n % (q-1)

We can use the same trick as in this previous answer: since we have the value $n \bmod (p-1)$, $n - n \bmod (p-1)$ is going to be $0$ modulo $p-1$, that is, a multiple of $p-1$, and having a multiple ...
Samuel Neves's user avatar
  • 12.6k
11 votes

What happens for factoring algorithms if P=NP?

Bill Garsarch just posted about this the other day. The short answer is that there is an explicit algorithm, which is known today, such that if P = NP (or even just FACTORING ∈ P) then the ...
Aaron Rotenberg's user avatar
11 votes
Accepted

How did they factor RSA 240?

$\exp((\log n)^{1/3})\neq n^{1/3}$. If you work through the formula for $L[\tfrac{1}{3},1.92]$ and set the $o(1)$ term to $0$, you get $2.4\cdot 10^{23}$ operations for $n\approx 10^{240}$. The ...
Sam Jaques's user avatar
  • 1,192
9 votes

How big an RSA key is considered secure today?

An adversary with a moderately large quantum computer to run Shor's algorithm will cut through a 1024-bit RSA modulus like a hot knife through butter, and maybe through a 2048-bit RSA modulus like a ...
Squeamish Ossifrage's user avatar
9 votes

Is it feasible to build an index of prime factors?

The Prime Number Theorem proves that there are approximately $\frac{x}{\ln x}$ primes less than any positive integer $x$. There are thus about $\frac{2^{2048}-1}{\ln (2^{2048}-1)}-\frac{2^{2047}}{\ln (...
SAI Peregrinus's user avatar
9 votes

I can divide a very large integer - did I discover anything?

Unfortunately you haven't made a scientific discovery. One of the places where large integer division is required is when testing for prime values. Primality tests are required to find real prime ...
Maarten Bodewes's user avatar
  • 92.9k
9 votes

What is the fastest integer factorization to break RSA?

Which of these is actually right? Both. From reading the abstract it appears the papper doesn't claim that "VFactor" or Fermat Factorization ("FFM") or Trial Division ("TDM") are the best methods in ...
SEJPM's user avatar
  • 46.1k

Only top scored, non community-wiki answers of a minimum length are eligible