Tech Note #35: How Encryption and Digital Signatures Work
19 May 1999
http://www.tatanka.com
Page
6 of 10

S = (K
-1
(H + XR)) mod Q
To verify the signature, a recipient must compute a value V from the known information:

W = S
-1
mod Q

U1 = HW mod Q

U2 = RW mod Q

V = ((G
U1
Y
U2
) mod P) mod Q
If V = R, then document was signed by the person with the public key (P, Q, G, Y).
The security of DSA is based on the computational infeasibility of finding a solution for the
equation S = (K
-1
(H + XR)) mod Q, when X is not known.
Comparing Different Cryptosystems
There are hundreds of different cryptosystems and signature systems available. They are
commonly compared with regard to security, computational effort, convenience,
implementation quality, political considerations, and commercial factors. This Tech Note will
not go into detailed comparisons, but will list some considerations that are important.
Security
The first consideration in evaluating cryptosystems is security: how easy is it to read an
encrypted message, or forge a digital signature?
Unfortunately, the answer cannot usually be given with certainty. It is rarely possible to
prove that a certain amount of computation is needed to break a code. Advances in
mathematics, and the presence of secret or hidden mechanisms in an algorithm are the
most common reasons given for not being sure how secure a given system might be.
Almost all experts believe the strongest recommendation for the cryptographic strength
of a system is its ability to withstand sustained, public scrutiny. The mechanisms
believed to be the strongest are those, which have been public for the longest time,
allowing cryptographers the opportunity to try and break them.
Don’t trust a secret or proprietary system: if it hasn’t withstood public study and
criticism, it hasn’t passed the most reliable test for security.
The mere fact that a system is in wide use does not mean it is considered secure. DES
has already been broken, and DSA is considered by many to be nearly broken, in spite
of the fact that these two systems are currently very popular.