Factorization is the problem of taking an integer and finding the set of prime numbers that produce the integer when multiplied together. For large integers with large factors, factorization is hard and is the basis for cryptosystems like RSA.
16
votes
3answers
1k 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 ...
9
votes
5answers
456 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 ...
8
votes
3answers
970 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 ...
7
votes
3answers
538 views
Modern integer factorization software
What are the modern software packages that can be used to factoring large numbers into primes. By modern I mean developed and made public within the last 5 years. I'm interested in things that are ...
7
votes
1answer
1k 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 ...
6
votes
2answers
184 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 ...
5
votes
2answers
369 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 ...
5
votes
2answers
184 views
Why would this method of discrete logarithm finding not work?
Say we do know $b$ but not $k$, and are given $g$ such that $g\equiv b^k\pmod p$. And say there exist factors $E = e + m'p$ ($e \equiv b^i \bmod p$) and $F = f + m''p$ ($f \equiv b^j \bmod p$) of $g$. ...
5
votes
1answer
188 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 ...
4
votes
1answer
116 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:
...
4
votes
1answer
88 views
In RSA, how to make sure that $p-1$ and $q-1$ are still hard to factorize?
See this question. The comment by Brett Hale stated:
On the other hand, ensuring $(p - 1)$ has a large prime factor requires very little extra effort.
What's actually the 'little extra effort'?
4
votes
2answers
357 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 ...
4
votes
1answer
186 views
Questions about William's p+1
First off, if you're doing William's p+1 test, then also doing Pollard's p-1 is redundant, since the p+1 test covers both cases, right?
Second, why is the recurrence $V_{n+1} = aV_n - V_{n-1}$ used? ...
4
votes
2answers
234 views
An Elliptic curve cryptography implementation which can be terminated
I'd like to have an implementation of elliptic curve cryptography along the lines of secp256k1 which is secure until some information is published after which it is broken.
One idea would be to use ...
4
votes
0answers
83 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, ...
3
votes
1answer
130 views
Impact of algorithms for factoring using elliptic curves over $\mathbb{Q}$
Recently a few papers have appeared that describe a new approach to factoring, using elliptic curves over $\mathbb{Q}$. See, e.g.,
Factoring integers and computing elliptic curve rational points, ...
2
votes
3answers
279 views
Is the new preprint “An Algorithm For Factoring Integers” by Yingpu Deng and Yanbin Pan worth reading?
I just discovered on the eprint server of the IACR the paper mentioned in the title. Scanning quickly over the paper I didn't find anything spectacular, so I doubt that their new(?) approach will be ...
2
votes
1answer
224 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 ...
2
votes
1answer
79 views
What's the strategy for future directions in cryptography? Bigger numbers/faster searching, or new methods, say, of factoring?
I'm taking a course in cryptography, and I would value any comments. This is not too technical a question, but more about directions or strategy in cryptography. My question is, is public key ...
2
votes
1answer
114 views
Choosing good parameter for Lenstra's elliptic curve factorization
In Wikipedia, there is an article explaining Lenstra's factorization algorithm. As far as I got it, we choose some $e \in \mathbb{N}$ and a point $P$ on the curve and then calculate $eP$. While ...
2
votes
2answers
254 views
Optimising Pollard's Rho algorithm for large semi-primes
I have programmed an implementation of Pollard's Rho factoring algorithm using C++ and the GMP library.
It is reasonably fast with large numbers, however I haven't implemented any form of cycle ...
2
votes
1answer
77 views
Discrete log analog of ECM factoring algorithm?
Anecdotally, most factoring algorithms have a corresponding variant algorithm that can be used to attack the discrete log problem using similar ideas.
Is there an analog of the elliptic curve (ECM) ...
2
votes
1answer
233 views
Attacks on the RSA Cryptosystem
I was reading some articles about attacks on RSA system and I wonder about some generalization of the following theorem.
Theorem (Coppersmith).
Let $N=pq$ be an $n$-bit RSA modulus, where
...
1
vote
2answers
241 views
Is there an algorithm for factoring N, which is just as simple as this one, but faster?
I found a simple algorithm for factoring semiprime numbers, you can read about it in Factoring Semiprimes and Possible Implications for RSA.
It basically works like this:
You reverse the digits in ...
1
vote
1answer
71 views
Security relevance of random factor in Paillier
In the Paillier cryptosystem [1] the encryption of $m \in \mathbb{Z}_N$ with randomness $r \in \mathbb{Z}_n^*$ is $c = g^m r^n \bmod{n^2}$.
The additive-homomorphic property of the system shows that
...
1
vote
1answer
2k views
OTP from Sony BIOS password recover
From Dogbert's blog:
Sony has a line of laptops ("Vaio") which compete mainly in the high value market segments. They implemented a master password bypass which is rather sane in comparison to the ...
1
vote
0answers
27 views
Generating Polynomials for the MPQS
I'm going to try and eventually factor RSA-100, but my current QS needs a lot of improvement, so I'm going to try and switch over to the MPQS.
I'm a bit confused as to how the MPQS works, which is ...
1
vote
0answers
85 views
Quadratic Sieve Bottleneck, Multiple Polynomials an option?
After my failed attempt at trying to implement the ECM, I started working on the quadratic sieve. It works, but the bottleneck is finding smooth values over the factor base.
The way I implemented it ...
0
votes
0answers
59 views
Why is it impractical to generate a semiprime dictionary? [duplicate]
This might be a very simple question. However, I am just learning the concept, so just excuse me.
I am wondering why there is not any attempt to generate all semiprime numbers? (as an dict. attack to ...
-1
votes
0answers
84 views
Factorization wanted [closed]
I am trying to factor
6770389183242962153995229561325734953985709474234543383365326043276409942870153199419967538710900938086776046853
which is a factor of 10*80!+1.
ECM did not find a factor, and ...
