Please see my thread Proper REST signatures for the entire walkthru for signature related issues, this is covered there.