Is it safe to use RSA as a proof-of-work system? Suppose I devised the following challenge-response proof-of-work system:

A server generates a 2048-bit RSA modulus, and uses the "public" exponent (usually 65537) to sign a random nonce a fixed number of times, say, 256.

The server then sends the signed nonce to the client, along with the "private" exponent (which is much larger) and modulus, asking it to un-sign it using the private key 256 times, sending the answer back for the server to verify. Because the private operation takes about 300 times longer at 2048 bits, the client will take longer to un-sign the key than the server took to sign it.

Is this usable/secure? Or does the generation of the modulus outweigh any gains in the difference in signing time? If so, how could I make it usable, if at all?
Is this usable? Or does the generation of the modulus outweigh any
  gains in the difference in signing time?


No, it does not work. The generation cost itself isn't too important, because signing any one nonce doesn't help the client sign any other nonce, so you can just use a single key all the time (if you had to create a new keypair for every puzzle, this would be very impractical and nobody would use it).

But the problem is that the advantage of the server on the client is asymptotically more or less zero, so this is quite useless as a proof of work scheme. See D.W.'s answer for one way of breaking the scheme.

Another way similar to D.W.'s is to realize that your scheme requires the client to compute, given a random  nonce $a$ and a work factor $k$, modulus $n$ and private exponent $d$:

$$\text{proof} = ((a^d)^d)^{\cdots ~ k ~ \text{times}} ~ \text{mod} ~ n$$

And this is equal to:

$$\text{proof} = a^{d^k} ~ \text{mod} ~ n$$

But because the client knows $d$ (you gave it to him!) he can factorize $n$ in constant time and compute $\varphi{(n)} = (p - 1)(q - 1)$, which gives him the ability to reduce the inner exponent:

$$\text{proof} = a^{d^k ~ \text{mod} ~ \varphi{(n)} } ~ \text{mod} ~ n$$

The client can calculate this in $\log{k}$ modular multiplications or squarings by $d$, and $\log{n}$ (on average) modular multiplications or squarings by $a$. But the server has to do pretty much the same amount of work - the only difference is it saves some time because $e$ is smaller than $d$. The gain is minimal and very difficult to control, since there's a point where you just can't make $e$ any smaller and need to increase $n$ to compensate.

In conclusion, this is not a good proof-of-work scheme, as it provides basically no control over the work factor desired and the server will need to work about just as much as the client for realistic values of $n$ and $k$.




  If so, how could I make it usable, if at all?


However, it's possible to take your scheme a step further to make it cleaner (and not depend on RSA). The idea is to choose a "difficulty factor" $t$, a random number $a$, a large $n = pq$, and ask the client to compute:

$$\text{proof} = a^{2^t} ~ \text{mod} ~ n$$

The client will require $t$ squarings to achieve this (there is no known way to do better, and it cannot be parallelized to any significant degree), while the server, knowing the factorization of $n$ (since it generated it) can just compute:

$$e = 2^t ~ \text{mod} ~ \varphi{(n)}$$

And hence, from Euler's Theorem:

$$\text{proof} = a^e ~ \text{mod} ~ n$$

Which the server can then compute in logarithmic time. In effect, the server only needs $O(\log{nt})$ time, but the client needs $O(t)$ time. By making $t$ arbitrarily large, you can fine-tune the amount of work you want the client to do, linearly, but the work stays logarithmic for the server, which is practical.

The generation cost is also irrelevant, because the server can generate it once and reuse it all the time with different values of $a$ (that's not always true, but in this case it is - the attacker can't use the results of a previous proof of work to quickly solve another assuming $a$ is random and $n$ is large).

Note your scheme doesn't care if the client can factorize $n$ since you are basically giving away $d$, but in this scheme it is imperative that $n$ be large enough so that factorization is not possible. But this is easy to address, just create a 2048-bit modulus (or 4096-bit if you are paranoid) and be done with it.



For more details and supporting theory on this method, see:

Time-lock puzzles and timed-release Crypto, Ron Rivest, Adi Shamir, David Wagner.

Puzzle description for the MIT time capsule.