1

I want to give a presentation on school about RSA encryption and decryption. I understand the basic of calculating a public and private key with two small prime numbers. And how to use those keys to encode and decode a simple message.

After demonstrating the above i want to briefly talk about security,since it's a very large and complex subject. As far as my understanding, 2048 keys are safe, even for NSA. Everybody has heard about the news that NSA can(could) read e-mails, etc.. I red that they build a backdoor in the DUAL_EC_DRBG PRNG (Psuedorandom Number Generator) that is(was?) used by allot of company's, like RSA.

They can predict the outcome of those random number. But what does that have to do with the encryption and decryption of RSA? That is based on multiplying two massively large prime numbers, which company's can choose for them self?

What am i missing here, i hope someone can point me onto the right track?

Thanks!

Justin
  • 11
  • 2

2 Answers2

4

Nobody uses RSA to directly encrypt data transmitted over http (web) or SMTP (email). 2048 bit RSA would only allow you to encrypt 245 bytes at a time, and each such operation is expensive.

Protocols get one of the parties or both parties together to generate a new random number that is long enough to be unguessable and unique. 128 bits are enough, though TLS uses more. Then they use this number as a symmetric encryption key (technically, seed for KDF), which allows them to quickly encrypt a lot of data.

If the CSPRNG is backdoor-ed, adversary can predict the shared secret key. If the shared key is not secret, you completely break the security.

If one of the parties generated the shared secret key, they must transmit it to the other party, in a way that is immune to eavesdropping. A simple way is to encrypt the shared secret key using the recipient's public key. PGP does this, and older SSL/TLS did this.

A problem with transmitting the shared random secret key encrypted with the recipient's public key is that if you get your hands on the recipient's private key, maybe years later when they no longer use this keypair, you can decrypt previously recorded ciphertexts. So a junked hard drive with the private key for a long ago expired TLS server certificate would allow e.g. the NSA to decrypt years of old traffic.

Newer protocols demand use of better scheme: Diffie Hellman to establish an anonymous shared secret, and digital signatures to prove other party is who they say they are.

In modern protocols, RSA is only used for signing and verifying signatures.

Note: You may have read an explanation of RSA signatures as a kind of encryption. It is a very bad explanation, don't use it.

Note that textbook RSA is insecure and must not be used. You must use secure padding schemes for RSA encryption and for RSA signatures. The padding schemes for the two use cases have different goals and are different. Mixing them up is insecure.

Note that old TLS used pkcs#1v1.5, it's now considered insecure, use RSASSA-PSS instead.

As you've noticed implementing RSA securely is difficult, modern recommendation is to use better cryptographic primitives, like those in libsodium (or better yet, libsodium itself).

Community
  • 1
Z.T.
  • 7,963
  • 1
  • 22
  • 36
0

PRNG is the key here (compared to CSPRNG or True RNG). It's a psudorandom number generator; it has to use an algorithm to determine the prime given for RNG regardless of min entropy pool threshold. If the algorithm has known weaknesses or a possible method to reverse engineer the method for RNG, it makes the entropy pool source moot and allows easy methods to determine the primes generated from kernel entropy.

A PSRNG has to be able to generate random numbers even in the event of an entropy pool is below min entropy thresholds (classic /dev/(u)random argument) so being able to create an event of known primes or easily guessed primes, is easier than most people think when A) using a an algorithm with backdoors. DUAL_EC_DRBG was considered a great RNG due to the validating factors required to make PRNG crypto secure, but the source algorithm was compromised. While not required to be used, it was an attractive RNG due to it's use of EC and requirements for DoD applications. The thought was if it's good enough for DoD, then it's good enough for me. So the NSA got away with a mob rules mentality even though they compromised only 1 of 4 recommended RNGs.

The realized backdoor was specifically why NIST removed support for that as a method for generating RNG from SP800-90A. That was the quickest up for draft and revised NIST doc I've seen in a long time. If you haven't read the whole thing, it's quite interesting.

Here's an interesting article though on this subject if you haven't already read it. http://blog.cryptographyengineering.com/2015/01/hopefully-last-post-ill-ever-write-on.html