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.

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.

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.

To encrypt a message

To decrypt ciphertext

Theoretically, you need the private key to decrypt the message. However, anybody can check if a possible message

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).

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).