New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

# Tag Info

### 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 ...
• 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 ...
• 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$...
• 142k
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 ...

### 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 ...
• 142k
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 ...
• 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 ...
• 22.6k

Top 50 recent answers are included