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

New answers tagged

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.3k
1 vote

How to better generate large primes: sieving and then random picking or random picking and then checking?

If you look at 1024 bit numbers, about one in 700 is a prime. Eventually you check a prime, the effort for that is about 50 or 64 rounds of the Miller-Rabin test. If you just pick random numbers, one ...
gnasher729's user avatar
  • 1,256
1 vote

RSA small private key attack: the private key is slightly larger than the bound given by Boneh and Durfee

Although I'm not stating this will suceed, I'd try the Boneh and Durfee attack (open access) and hope for the best. Their statement is that, for $e\cdot d\equiv1\pmod{\frac{\phi(N)}2}$ and $d=N^\delta$...
fgrieu's user avatar
  • 142k
3 votes
Accepted

Shannon's Perfect Security for Asymmetric Encryption

There is no perfectly secured public-key encryption scheme. In the asymmetric world, an adversary is allowed to encrypt a message of its choice using the public key, so it can't be that "that ...
Yahav Boneh's user avatar
3 votes

Why does it take longer to generate suitably large primes for Diffie-Hellman key exchange as opposed to for RSA encryption / decryption?

generating arbitrarily large primes for DH typically takes much longer than for RSA Yes. That's for several reasons For comparable security, the prime $p$ in DH needs to have about as many bits as ...
fgrieu's user avatar
  • 142k
10 votes
Accepted

Why does it take longer to generate suitably large primes for Diffie-Hellman key exchange as opposed to for RSA encryption / decryption?

The question specifically states that generating arbitrarily large primes for DH typically takes much longer than for RSA, and I am to verify this claim. Well, yes. In the simplest terms, to ...
poncho's user avatar
  • 148k
1 vote

Why does it take longer to generate suitably large primes for Diffie-Hellman key exchange as opposed to for RSA encryption / decryption?

The complexity of generating a prime depends only on the size (bitlength) of the prime. So whether for DH or not this won't change and will be polynomial complexity (polynomial in $\log p$ see details ...
kodlu's user avatar
  • 22.6k

Top 50 recent answers are included