RSA requires two numbers which are big and random and prime. It is the primality that makes things tricky. Generating random primes is a lot harder than generating random numbers.
The other factor (no pun intended) that makes RSA keys large is that there are more efficient algorithms for factoring than there are for solving the elliptic curve discrete log problem, e.g. https://en.wikipedia.org/wiki/General_number_field_sieve If you crunch the numbers on this you will find that a 2000-bit RSA key has a security level of about 100 bits, i.e. it takes about 2^100 operations to factor a 2000-bit RSA key using GNFS.
Not disagreeing, but I think both randomness and primality testing both have the problem that it's so easy to do them poorly. Generating random primes of these sizes isn't all that difficult, and even proofs can be done in reasonable time frames (e.g. under 10 seconds for 1024-bit inputs). There are also a couple random proven prime algorithms which run pretty fast. Getting software to correctly implement everything .... that seems to be hard.
> Getting software to correctly implement everything .... that seems to be hard.
Exactly. Generating random primes is not terribly difficult in theory, but in practice it is very tricky, which makes it hard to answer the question: how do you know you can trust your keys? Sure, you can verify that your primes are prime, but how do you know how much entropy they have? The only way to figure that out is the audit the code. (And then you have the problem of making sure that the code you're running is the code you audited.)
Generating random numbers is also tricky, but a lot less so than generating random primes: take an entropy source and run it through a whitener, i.e. feed it to sha512. As long as you have a reliable estimate of the lower bound of the quality of your entropy source, you're good. A lot fewer moving parts.
The other factor (no pun intended) that makes RSA keys large is that there are more efficient algorithms for factoring than there are for solving the elliptic curve discrete log problem, e.g. https://en.wikipedia.org/wiki/General_number_field_sieve If you crunch the numbers on this you will find that a 2000-bit RSA key has a security level of about 100 bits, i.e. it takes about 2^100 operations to factor a 2000-bit RSA key using GNFS.