Proof of work to prevent DOS and DDOS attacks of web pages

If an attacker had to expend a bit of work to access a web page, then it would get prohibitively expensive to dos such a site. I suggested this at a lunch with programmers today, and one of them - Rene - suggested that one could use a TLS certificate with a short key, and the client would need to use javascript to brute force it to access the web site for which the certificate is required. One would need to have a stash of these certificates ready though. I wonder how computationally expensive they would be to manufacture.

I had thought more about just having some kind of mathematical trap door where it should be easy to check that work has been expended, such as giving the client a product of primes and it needs to tell which primes were used in order to access a page. This verification of work should be done very cheaply at the edge of your server's system.

Hashcash seems to have triggered ideas in the direction of proof of work to mitigate DOS attacks: (A paper in ps format).

I wonder if one could make an implementation such as any new visitor gets a cookie. The cookie is set to the product of a number of primes, and the browser sets another cookie for the same domain, with the answer. At the next request the cookies are read server-side and a new cookie is presented as challenge. The server keeps track of what challenges it has served out and invalidates any request giving the answer to an already solved challenge. All of this should be done as early as possible in the processing of a request.

Furthermore the system should only be enabled when a dos attack is detected.

The following page Final post on Javascript crypto | root labs rdist points out that an attacker may use something else than javascript on a normal computer to do an attack (faster languages, other hardware). He attributes this insight to the below paper I think, but it does not have the same author as given by the link:

Pricing via Processing or Combatting Junk Mail - Abstract

This paper also talks about favoring memory bound instead of CPU bound problems to thwart custom hardware I suppose, as is also the idea behind scrypt (given the right parameters, which apparently was not the case for Litecoin et al).