80
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 ...
- 19.1k
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 ...
- 138k
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 ...
- 91.9k
43
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 ...
- 21.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 ...
- 12.4k
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 ...
- 446
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 ...
- 27.6k
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 ...
- 21.2k
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 ...
- 9,001
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 ...
- 814
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$ ...
- 45.7k
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 ...
- 47.9k
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 $...
- 47.6k
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)$ (...
- 138k
16
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 ...
- 21.9k
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 ...
- 6,405
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 ...
- 496
14
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/
...
- 47.6k
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 ...
- 47.9k
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 ...
- 145k
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 ...
- 138k
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 ...
- 138k
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 ...
- 349
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 ...
- 211
11
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 ...
- 12.4k
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 ...
- 1,105
10
votes
Accepted
Public key crypto without modular arithmetic?
Breaking such a scheme is easy.
Suppose Alice wants to transmit a message $M$ to Bob. First thing, Alice picks an integer $R_a$ and sends the cipher text $C_a = M \times R_a$ to Bob. Bob then picks ...
- 10.4k
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 ...
- 47.9k
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 (...
- 5,786
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 ...
- 91.9k
Only top scored, non community-wiki answers of a minimum length are eligible