Secure RESTful API Access

I recently implemented a RESTful API interface. The interface works well, but what worries me is that is anyone can have access to the APIs. So I started to look for a way to secure my API access. After googling "secure API access", I found some very useful posts, but the one I liked the most is "Designing Secure REST (web) API without OAuth", which partially based on the RFC2104 HMAC document. The reason that I love it the most is that this approach doesn't require a two-stage authentication, where in the first stage, the client need to authenticate the server to get an access token, and in the second stage, the client transmit messages with the access token.

In order to secure the transmission, a common private key is always needed for both client and server, because anything transmitted over the Internet can not be treated as safe. So on the client side, it will looks like this:

Client:
    - Private
        - a private key (never transmitted)
    - Public
        - client identity (IP address and/or MAC address)
        - timestamp (generated when make the request in UTC)
        - actual array of parameters you want to transmit over the Internet
        - a hash (mentioned in the next paragraph)

To secure the transmission, according to HMAC, I have to generate a hash based on both private and public parameters on the client side with a black box function. The black box function is simply a way of secretly mixing these parameters together, during which you can do whatever crazy things you can imagine. After mixing, the result is passed to a hash function such as SHA1 (MD5 is considered to be broken), and transmit the hash with the public parameters.

So on the the server side, it will receive all the public parameters transmitted by the client. In order to validate the access, the server goes through the following steps:

 - if timestamp is expired (more than 1 minute old), reject the access
 - compute the hash using the same scheme in the client
     - grab client identity from http header
     - grab private key from local key store
     - compute the hash
 - if the computed hash doesn't match the transmitted hash, reject the access
 - everything checks out at this point, proceed the access