RSA Public Key Encryption

Flaw: Direct Factoring

The core operation in RSA key generation is:
   p = random_prime(bits/2)
   q = random_prime(bits/2)
   n = p*q       # public modulus
   e = 65537
   d = modular_inverse(e,(p-1)*(q-1)) # private key

Because the public modulus is just the product of two primes, and you can recompute the private key via the modular inverse, factoring is one obvious attack on RSA. Based on brute force factoring, trying all divisors up to sqrt(n), you might expect factoring an n-bit product to take 2^n/2 time, so 200 bit products would be fine.

However, factoring algorithms exist which are much faster than brute force, such as elliptic curve factoring (coming in about a month!). For example, GMP-ECM can factor a 128-bit product in about 1 second:

  $ echo 308419861048375364105417853828868357721 | ecm 1000000
GMP-ECM 6.4.4 [configured with GMP 5.1.3, --enable-asm-redc] [ECM]
Input number is 308419861048375364105417853828868357721 (39 digits)
Using B1=1000000, B2=1045563762, polynomial Dickson(6), sigma=116281483
Step 1 took 815ms
********** Factor found in step 1: 16951655882749288739
Found probable prime factor of 20 digits: 16951655882749288739
Probable prime cofactor 18194084588646957139 has 20 digits

Factoring a 180 bit product takes about 2 minutes:

 $ echo 1177700523080677245883300985764599032955400633132267477 | ecm 100000000
GMP-ECM 6.4.4 [configured with GMP 5.1.3, --enable-asm-redc] [ECM]
Input number is 1177700523080677245883300985764599032955400633132267477 (55 digits)
Using B1=100000000, B2=776268975310, polynomial Dickson(30), sigma=4175794950
Step 1 took 89854ms
Step 2 took 44118ms
********** Factor found in step 2: 1207946822204051595384881203
Found probable prime factor of 28 digits: 1207946822204051595384881203
Probable prime cofactor 974960570641523643171225559 has 27 digits

Factoring a 200-bit product takes about half an hour on my laptop.

NIST recommends much longer key sizes for RSA:

Symmetric Key	RSA Key	ECC Key
80 bits	1024 bits	160 bits
112 bits	2048 bits	224 bits
128 bits	3072 bits	256 bits
192 bits	7680 bits	384 bits
256 bits	15360 bits	512 bits

Progress in algorithms for factoring are the primary determinant of security of RSA going forward.

Flaw: Prime Generation

The prime numbers p and q need to be truly unpredictable, not just random looking. This means calling a deterministic random number generator like "rand" is completely insufficient--consider there are only 4 billion possible values that can be passed to srand().

Back in 1996, this was a known flaw in the then wildly popular web browser Netscape, which based the key on the current time in seconds (predictable on NTP, and published in HTTP headers too). In 2008, Debian's version of openssl was found to have a similar flaw, basing the key only on the process ID (only 2^16 options, and predictable on servers). Ironically, openssl used a good cryptographic randomness source, but a Debian audit determined the code that applied that randomness also read from uninitialized memory (bad in theory, OK for random number generation) and commented out the whole thing.

The fix: make sure your implementation is using a good cryptographic random number source, not pseudorandom numbers.

Folks that compute gcd on the products of lots of published keys keep finding common factors, which are due to re-used primes, mostly on embedded hardware such as routers or VPN hardware.

Flaw: Side Channel (Timing, Heat, etc) Attacks

Each operation used in RSA encryption is a slow multi-precision operation, so it's easier to measure the time taken to do each sub-multiplication in an exponentiation (compared to, for example, the sub-clockcycle time to do the carry bits in a normal addition). This is bad, because tons of operations have data-dependent timing--for example, decrypting data (m=c^d mod n) means looking at each bit of your private key, and choosing to include a multiple of c. This sort of attack can be extremely high precision when coming from a different VM on the same cloud server.

Possible fixes:

Use a fixed amount of time and energy: start a timer, do the encryption, then do similar but useless work until the timer expires. *Then* send the result on.
Use an algorithm that does the same amount of work for any input, such as Montgomery multiplication.

Flaw: Message Enumeration

Recall that:
To encrypt a message m into ciphertext c, use the public key e: c = m^e mod n
To decrypt ciphertext c back into the message m, use your private key d: m=c^d mod n

Theoretically, you need the private key to decrypt the message. However, anybody can check if a possible message m encrypts to the intercepted ciphertext c, because anybody can encrypt a message for you. In other words, public key "encryption" works more like a hash function, where anybody can check if the hashes match.

Secret key ciphers don't have this flaw, because you need the key to encrypt.

The fix is to pad each message with random data--the exact analog of using a salted hash for passwords. 256 bits is enough to make an attacker's search space entirely infeasible. Some follow this with a weak encryption scheme, like the hash-based one round Feistel used in OAEP, to ensure that a partial break won't reveal anything valuable (it also messes up multiplicative structure, below).

Flaw: Multiplicative Structure

Since RSA is based on simple exponentiation, encrypting (or decrypting) the product of two messages gives the product of the two ciphertexts:
c = m^e mod n
c' = m'^e mod n
c * c' = m^e * m'^e= (m * m')^e mod n

There are enough ways to exploit this that you should never encrypt or sign a raw message, only a carefully packaged message.

For encryption, see the previous fix OAEP.

For signing, several options exist, but the most popular signing scheme is the hash based RSASSA-PKCS1-v1.5. This boils down to signing a binary value consisting of:

The constant 16 bits 0x0001
Padding bytes of value 0xff (to get up to size n)
Spacer byte of value 0x00
A binary hash algorithm identifier (DER)
And then the binary hash (of your choice).

Flaw: Malware Certificates

Some machines come with adware or malware that installs its own unrestricted HTTPS root certificate, which it uses to man-in-the-middle web traffic for the purpose of installing ads. For example, Lenovo recently stopped shipping with the Superfish adware/malware, which had a single(!) hardcoded private key, recently pulled out of the executable with "strings", and a password of komodia.