The verfication is done with your public key.

Basicly its a o = m^d (mod N)

where o is the signature, m is the message and d is the private key

Because RSA has some vulnerabilites, the message gets hashed first.

To check the signature you calulate o^e = m (mod N)

where e is the public key to the former used private key.

If the hashes match the message wasnt changed durring transport.

This works because ed = 1 (mod phi(N))

while e and N again are part of the public key

and d is the private key

If you want more details, read the rfc 3447, its explained for RSA, but the principle is still the same

Link:

http://tools.ietf.org/html/rfc3447#page-27Edit: phi(x) is eulers phi function (

http://en.wikipedia.org/wiki/Euler%27s_totient_function )