 Tech Note #35: How Encryption and Digital Signatures Work
©
1999 Bionic Buffalo Corporation; All Rights Reserved.
19 May 1999
http://www.tatanka.com
Page
5 of 10
Of course, someone may develop a new way to solve the equation, which does not require so
much computation. However, mathematicians have been trying (for other reasons) to solve this
equation for a long time, and many believe there is no shortcut to a solution.
As with other public key cryptosystems, the key length of RSA is variable. By choosing a longer
key, more computation is required to solve the equation, and hence the message is more secure.
DSA: An Example of a Digital Signature Mechanism
One of the most common digital signature mechanisms, the Digital Signature Algorithm (DSA)
is the basis of the Digital Signature Standard (DSS), a U.S. Government document. As with
other digital signature algorithms, DSA lets one person with a secret key “sign” a document, so
that others with a matching public key can verify it must have been signed only by the holder of
the secret key.
Digital signatures depend on hash functions, which are one-way computations done on a
message. They are called “one-way” because there is no known way (without infeasible
amounts of computation) to find a message with a given hash value. In other words, a hash value
can be determined for a given message, but it is not known to be possible to construct any
message with a given hash value. Hash functions are similar to the scrambling operations used
in symmetric key encryption, except that there is no decryption key: the operation is
irreversible. The result has a fixed length, which is 160 bits in the case of the Secure Hash
Algorithm (SHA) used by DSA.
In practice, digital signatures are used to sign the hash values of messages, not the messages
themselves. Thus it is possible to sign a message’s hash value, without even knowing the
content of the message. This makes it possible to have digital notaries, who can verify a
document existed (and was signed), without the notary knowing anything about what was in the
document.
The private key in DSA is a number X. It is known only to the signer.
The public key in DSA consists of four numbers:

P is a prime number, between 512 and 1024 bits long

Q is a 160-bit prime factor of P -1.

G = h
(P - 1)/Q
, where H < P -1 and G mod Q > 1.

Y = G
X
mod P, which is a 160-bit number.
A signature on a document’s hash value H consists of two numbers R and S:

R = (G
K
mod P ) mod Q, where K is a randomly-chosen number < Q.