Skip to main content
5 votes
Accepted

Big prime factor of the prime number you feed to Diffie Hellman

My question is: HOW BIG of a prime factor does (N-1) need to have, in order for Diffie-Hellman to be considered secure, Background: if Diffie-Hellman, we have a generator $g$; the size of the ...
poncho's user avatar
  • 148k
3 votes
Accepted

Reduction from factoring to RSA and the Oracle RSA problem

About the Generic Model of Computation, in "On the Analysis of Cryptographic Assumptions in the Generic Ring Model" by Jager and Schwenk they state that, "We prove in the generic ring ...
Alex Them's user avatar
  • 322
2 votes

Factoring 350 to 400 bits long rsa number with a factor that has a known bitlength… But in less than 5 to 7 minutes and less than $100

One thought is the highly parallelisable elliptic curve method. There is a page of the largest prime factors found using ECM and the corresponding composite. By both metrics, the problem size seems to ...
Daniel S's user avatar
  • 24.1k
2 votes

How could a 1024‒bits RSA modulus be most economically factored within months today?

No serious paper later seems to have explored the cost of factoring a 1024‒bits RSA modulus in the last 15 years. There are at least two things you would probably be interested in. The Factoring as a ...
Mark Schultz-Wu's user avatar
  • 13.5k
2 votes

Can a very efficient RSA factoring algorithm be worth money?

Yes, almost any improvement on state of the art factoring is monitizeable. Small improvements will probably not be worth a lot of money. But an algorithm which can factor commonly used 2048 bit keys ...
Meir Maor's user avatar
  • 11.8k
1 vote
Accepted

Why doesn't the existence of the Quadratic Sieve algorithm imply that integer factorization is in the class SUBEXP?

Yes both QS and NFS (Number Field Sieve) imply that factorization is subexponential. But the exact relationship between SUBEXP and NP is unknown. See the answer to the question here. And as pointed ...
kodlu's user avatar
  • 22.8k
1 vote

How often do hard-to-factor numbers occur?

As I commented already, the easier problem of finding many hard-to-factor numbers in the (big) interval $[2^k, 2^{k+1}]$ is relatively easy, as this is exactly what an RSA key generation has to do: ...
garfunkel's user avatar
1 vote

finding r-th root in $\mathbb{Z}/n\mathbb{Z}$

The key is to use extended euclidean algorithm. Here's a numerical example, see if you can figure it out yourself. Given $z, a := z^{1 / 3}, b := z^{1 / 5}$, we can compute $z^{1 / 15} = a^{-1} \cdot ...
Gareth Ma's user avatar
  • 350
1 vote
Accepted

RSA given 30% MSB of p and 30%MSB of q

Since the reference given in the other answer is 18 years old, as well as being erroneous w.r.t. division as pointed out by @fgrieu, I did some digging around for more recent results/updates on ...
kodlu's user avatar
  • 22.8k
1 vote

RSA given 30% MSB of p and 30%MSB of q

No, knowing the MSB of p you could calculate the MSB of q dividing it by n, so knowing MSB of p AND q is redundant. ~50% with coppersmith is the best u can do (for now...) https://cacr.uwaterloo.ca/...
akonzu's user avatar
  • 59
1 vote

Can a very efficient RSA factoring algorithm be worth money?

There may be secrets protected by RSA that would be worth a million dollars to uncover. But there’s a problem: If I sent out ten encrypted messages, and you don’t know which one contains the valuable ...
gnasher729's user avatar
  • 1,272
1 vote

Can a very efficient RSA factoring algorithm be worth money?

To add to the perfectly fine other answer: Your question "how long must it take" depends on the computing power you have, and can only be answered in the context of specific hardware and ...
kodlu's user avatar
  • 22.8k

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