Fastest algorithm for message authentication? I'm searching for the fastest way to verify that a message was sent by the correct user.


The first solution I know of is to use HMAC. But in order to verify, I'll have to produce another signature and compare it with the original. In my case, this does not seem to be the best choice, because the time needed to verify is practically equal to the time needed to produce the signature.
To use a classic cryptographic signature (RSA or AES) over a MD hash.     I didn't find benchmarks/times for verifying a signature (but just for producing the signature). Surely, to produce a signature is slow, but to verify?  
Finally, is there any algorithm that use a statistical  method for granting authentication (most of the messages are valid)? 


After comparing benchmarks, it seems there is a third way which is a lot faster (10 times more): to use the GMAC/VMAC algorithms. 

I'm developing in Java, but a C/C++ library would also be OK.

Specifically, my questions are:


Can you confirm that the best solution is GMAC/VMAC for this scope? 
If yes, does anyone have an example for how to write the code for generating/verifying a byte array in Java (perhaps with the Bouncy Castle library).
eventually is there any algorythm that use a statistical method for
  granting authentication (the most of the messages are granted valid) ?


This would be a non-cryptographic way of doing it and would likely allow malicious users / attackers to fake authentication.


  to use a classic cryptographic signature (RSA or AES) over a MD hash.
  i dint find benchmarks/times for veryfying a signature (but just for
  producing the signature) . Surelly to produce a signature is slow, but
  to verify?


RSA and Rabin-Williams signatures are highly asymmetric in speed. Signature generation is slow, but verification is comparatively fast. However, RSA, ECDSA, RW and thelike are still very slow compared to symmetric methods.

Note that AES is not an asymmetric algorithm and thus does not fall into this category.


  first solution I knows it to use HMAC. For veryfing the data i have to
  produce the signature and comparing it with the original. It seams not
  the best in my case because the time for verifying is equal pratically
  to the time for producing the signature.


HMAC is a way construct a Message Authentication Code from a hash function. There are other MACs as well, which usually are faster (because hash functions are slow), which include GMAC, VMAC and CMAC (/OMAC).

The standard recommendation would be to use HMAC with a decently fast hash function. If that doesn't cut it, and you need more speed, you probably want CMAC with AES (assuming you have hardware acceleration for AES). If even that doesn't cut it, you are probably in a hardware deployment scenario and won't use Java anyways.

Note that HMAC and CMAC don't require a nonce for proper security, which makes them a nice choice most of the time. Other algorithms like GMAC and VMAC do require a nonce and there usually will be severe security implications (like a leak of the key), if the nonce is ever re-used.


  if yes in question 1, it would be usefull to see a example how do
  write the code for generating/verifying a byte array in java(probably
  the most idoneus is bouncy castle library). I thank you if you can
  show a short example for using it.


You will have to ask this question on a more programming focused site such as StackOverflow. Maybe also have a look at this previous Q&amp;A there.