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.
6
votes
2answers
150 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 ...
1
vote
2answers
237 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
69 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
...
4
votes
1answer
85 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'?
5
votes
2answers
175 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$. ...
2
votes
1answer
69 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
224 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
...
5
votes
2answers
228 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 ...
2
votes
1answer
77 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
104 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 ...
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 ...
4
votes
1answer
179 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? ...
1
vote
0answers
83 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 ...
5
votes
1answer
173 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
2answers
335 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 ...
2
votes
2answers
244 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 ...
3
votes
1answer
127 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
1answer
215 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 ...
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 ...
7
votes
3answers
504 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 ...
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 ...
4
votes
0answers
78 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, ...
2
votes
3answers
273 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 ...
8
votes
5answers
421 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
943 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 ...
4
votes
2answers
230 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 ...
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 ...
