Rest WebService with signed requests

I'm currently implementing a rest web service with Spring+Java+Tomcat and a cmd client to access it. The most important requirement is to restrict the usage to authenticated users - encryption isn't that important.

Because I can't guarantee that the service is accessed via TLS, I can't use Basic Authentication with username and password.

My idea is to do the following:

1. Get a nonce from the web service - that's changed after each request


2. Calculate a signature with DSA of (request + nonce)


3. Add signature to HTTP header and check it in the web service

How I would create the signature:

// To generate the keys
KeyPairGenerator keyGen = KeyPairGenerator.getInstance("DSA", "SUN");
SecureRandom random = SecureRandom.getInstance("SHA1PRNG", "SUN");
keyGen.initialize(1024, random);
KeyPair pair = keyGen.generateKeyPair();

// Per request
Signature dsa = Signature.getInstance("SHA1withDSA", "SUN");
dsa.initSign(pair.getPrivate);
dsa.update(...)
byte[] signature = dsa.sign();

To check the signature:

Signature sig = Signature.getInstance("SHA1withDSA", "SUN");
sig.initVerify(pubKey);
sig.update(...)
boolean ok = sig.verify(sigToVerify);

I hear so much about don't implement your own security, which is why I would like to know whether other people see something I don't.

Does someone see a major problem with this approach?

Thanks.