How to generate Signature for the AWS Import API request ?

Question

According to the AWS Import API docs the request looks like this:

POST / HTTP/1.1
content-type:application/x-www-form-urlencoded;charset=utf-8
host: https://importexport.amazonaws.com
content-length:356

Operation=CreateJob&Manifest=manifestVersion%3A%202.0%0Abucket%3A%20myBucket 
%0AaccessKeyId%3A%2013Q2729HYRYMYRB3FK02%0AreturnAddress%3A%0A%20%20%20%20name%3A%20 
Amazon.com%20ATTN%20Joe%20Random%20%0A%20%20%20%20street1%3A%201200%20AAAA%20Ave%20 
S.%0A%20%20%20%20city%3A%20Seattle%0A%20%20%20%20stateOrProvince%3A%20WA%0A%20%20%20%20 
postalCode%3A%2098114%0A%20%20%20%20phoneNumber%3A%20206-266-0000%0A%20%20%20%20 
country%3A%20USA&JobType=Import&AWSAccessKeyId=1111729HYRYMYRB3FK02& 
SignatureVersion=2&SignatureMethod=%2FVfkltRBOoSUi1sWxRzN8rw%3D

As you can see the last parameter in the body data is SignatureMethod. But it looks like Signature. I have found two available values for the SignatureMethod. They are HmacSHA1 and HmacSHA256.

I used the aws/s3 gem in order to generate the Signature query string and finally I've got the request looks like the previous one but with small change at the end.

POST / HTTP/1.1
content-type:application/x-www-form-urlencoded;charset=utf-8
host: https://importexport.amazonaws.com
content-length:356

Operation=CreateJob&Manifest=manifestVersion%3A%202.0%0Abucket%3A%20myBucket 
%0AaccessKeyId%3A%2013Q2729HYRYMYRB3FK02%0AreturnAddress%3A%0A%20%20%20%20name%3A%20 
Amazon.com%20ATTN%20Joe%20Random%20%0A%20%20%20%20street1%3A%201200%20AAAA%20Ave%20 
S.%0A%20%20%20%20city%3A%20Seattle%0A%20%20%20%20stateOrProvince%3A%20WA%0A%20%20%20%20 
postalCode%3A%2098114%0A%20%20%20%20phoneNumber%3A%20206-266-0000%0A%20%20%20%20 
country%3A%20USA&JobType=Import&AWSAccessKeyId=1111729HYRYMYRB3FK02& 
SignatureVersion=2&SignatureMethod=HmacSHA1&Expires=2010-09-16T00:50:54-07:00&Signature=%2FVfkltRBOoSUi1sWxRzN8rw%3D

But the response is still 403 Forbidden.

HTTP/1.1 403 Forbidden
x-amzn-RequestId: c0cb004b-c15e-11df-ad6c-5731ef5a3d54
Content-MD5: HvqVlJqxxJ5B5A73W4nUCg==
Content-Type: text/xml
Content-Length: 439
Date: Thu, 16 Sep 2010 06:50:55 GMT

<ErrorResponse xmlns="http://importexport.amazonaws.com/doc/2010-06-01/"&gt;
  <Error>
    <Type>Sender</Type>
    <Code>SignatureDoesNotMatch</Code>
    <Message>The request signature we calculated does not match the signature you provided. Check your AWS Secret Access Key and signing method. Consult the service documentation for details.</Message>
  </Error>
  <RequestId>c0cb004b-c15e-11df-ad6c-5731ef5a3d54</RequestId>
</ErrorResponse>

You could find the code I used to test this here http://gist.github.com/581726

Please advise me what's wrong and how to generate the signature correctly.