The Digital Signature Algorithm
| DSA is a NIST federal standard, used along with the Secure Hash Standard, to attach digital signatures to data. NIST published the first version of the DSA algorithm as part of the DSS (Digital Signature Standard, FIPS 186) in May 1994. DSA is based on the discrete logarithm problem, which is described in the next two sections. Recall from Chapter 4 that an asymmetric algorithm is always based on some one-way function. The one-way function upon which DSA is based is known as the discrete logarithm problem. The discrete logarithm problem involves an area of abstract algebra known as group theory. A group is actually a sophisticated and somewhat generalized concept that transcends familiar elementary school arithmetic. However, for our purposes, it is sufficient for us to understand the concept of group theory from an elementary point of view. Let's look briefly at what group theory is, and then move on to the discrete logarithm problem before we do any .NET DSA programming. Some Mathematical Background: Group TheoryIn a simplistic sense, a group can be thought of as a nonempty set that we call G, combined with a binary operation, that we conventionally call multiplication. By definition, a group G must satisfy the following four axioms:
The above axioms may strongly remind you of the elementary arithmetic of rational numbers , [13] and, indeed, the set of rational numbers taken together with multiplication does constitute a group according to the above definition. But notice that elementary integer arithmetic does not constitute a group, since the axiom regarding the existence of an inverse does not hold true. For example the inverse of the integer 3 is 1/3, which is not in the set of integers. The existence of the inverse is critical for constructing encryption algorithms, because decryption is the inverse of encryption. Without the existence of an inverse, you would be able to encrypt but not reliably decrypt, which of course would be entirely useless.
All is not lost for the integers, however! If you make a slight modification to the idea of an integer such that it is constrained to a finite range of values, and if you tweak the idea of multiplication such that resulting numbers beyond this finite range are wrapped around at the beginning of the range, then it is possible to construct a finite group of integers. This is known as modular arithmetic. The discrete logarithm problem involves a finite group on which we perform repeated multiplications using modular arithmetic. Specifically , we use a multiplicative group of the integers modulo a prime number. The reason for the modulus being a prime is simply to guarantee that a unique multiplicative inverse exists for each and every element in the group. If you choose a modulus that is not a prime, then there will be some elements that invert to the same number, resulting in a collision that must be avoided. The following shows the multiplication table for a modulus of 7, which happens to be prime. Note that every row after the first one is a permutation, meaning that no product is the same as any other product in the same row. This means that a unique multiplicative inverse exists for every number in the group. Of course, this is just an example and does not prove anything about the existence of the inverse for an arbitrary prime modulus. We will not provide the proof here, since that would require too much background material; however, if you are interested, many textbooks on abstract algebra or number theory provide a proof. All we are concerned with here is that if the modulus is prime, the multiplicative inverse does indeed exist for all elements in the group. This is important because this inverse must exist if we are going to try to use such a scheme as a cryptographic one-way function. Recall that although a one-way function is hard to invert, the inverse must actually exist for it to be useful to us. *0 1 2 3 4 5 6 (modulus is 7, which is a prime) -+-------------- 00 0 0 0 0 0 0 10 1 2 3 4 5 6 20 2 4 6 1 3 5 30 3 6 2 5 1 4 40 4 1 5 2 6 3 50 5 3 1 6 4 2 60 6 5 4 3 2 1 As a complementary example, consider the multiplication table for a modulus that is composite (i.e., not prime). Here we see the case where the modulus is 8, which of course is not a prime number. If you look at some of the rows in this table, you will see that some products are repeated within some rows. This indicates that multiplication does not have a unique inverse defined for some of these values and therefore cannot be used as the basis of an asymmetric algorithm. Bold text is used to show the numbers that are repeated in their row. These repeats indicate that the row is not a permutation, and therefore the inverse is not unique. *0 1 2 3 4 5 6 7 (modulus is 8, which is not a prime) -+--------------- 00 0 0 0 0 0 0 0 10 1 2 3 4 5 6 7 20 2 4 6 2 4 6 30 3 6 1 4 7 2 5 40 4 0 4 0 4 0 4 50 5 2 7 4 1 6 3 60 6 4 2 6 4 2 70 7 6 5 4 3 2 1 The Discrete Logarithm ProblemYou may recall from elementary mathematics that the repeated multiplication of a number on itself is called a power or an exponentiation, and the inverse operation is known as a logarithm or a log. For example, the following arithmetic expressions show the inverse relationship between power and logarithm operations. Consider the expressions 10 to the power of 2 is 100 and the logarithm to base 10 of 100 is 2 . In mathematical notation, we would write
You can probably already get a sense for the one-way nature that will emerge out of this scheme: Calculating a power is easy, since it is just a number of repeated multiplications, which is rather simple to compute. The calculation of logarithms is clearly the more complex direction to work in. It turns out that the ratio of difficulty between these two directions becomes even more pronounced when dealing with larger numbers. In the branch of mathematics known as complexity theory, we say that the work factor of the power operation is polynomial-time, and the work factor of the logarithm is exponentialtime. As the number of bits of the problem is scaled up, you always reach some point where the difficulty of an exponentialtime problem grows explosively relative to a polynomial-time problem. Voila! You have a one-way function. Let's discuss the problem algebraically in terms of an unknown quantity x . One would say, "Ten to the power of x equals 100. Find x ." In mathematical notation, the problem would be stated as
The solution for this problem would then be expressed as
Now let's look at these operations being performed on elements in a finite modular arithmetic group, denoted as Z p , [14] (containing the integers from 0 to p 1) with the implied modulo p arithmetic, where p is a prime number. Any element g chosen from Z p taken to the power x is represented using the traditional notation: g x , which means g is multiplied modulo p by itself x times. The number g is called a generator of the group, because all members of the group can be obtained by taking g to some appropriate power. The discrete logarithm problem is then, given the elements a and b in Z p , find an integer x such that a x = b . For example, let p = 19, a = 5, and b = 7, then find x given the following:
The solution for x would then be expressed as
The above equation expresses x as a modular logarithm. Although this example uses tiny numbers, in the case where the bit size is large, there is no known way to solve it in any fast and direct manner. The fastest known methods of solution all have work factors that grow exponentially as a function of the bit size of the problem. In the example above, you could just use a brute-force search, going through each of the possibilities for x , ranging from 0 to 18, and substituting each of these candidates back into the equation 5 x = 7(mod 19) to see if it becomes true. After going through this attack for a short while, you will discover the solution is 6, because indeed 5 6 = 7(mod 19). The brute-force attack in this example is not much work, since a modulus of 19 is very small, and therefore the number of candidates to test is tiny. After all, a modulus of 19 can be represented as a 5-bit number, but what if the modulus was hundreds of bits in size? Then, consider the fact that DSA allows key sizes ranging from 512 to 1024 bits. The work factor of such a brute-force attack doubles with each additional bit, providing us with a comfortable margin of safety. Although it has never yet been formally proven, the discrete logarithm problem appears to be an effective one-way function. Therefore, just as the prime-factoring problem is used in RSA, the discrete logarithm problem is used as the one-way function in DSA. This parallel is not quite complete, because, unlike RSA, which can be used for both privacy and digital signatures, DSA can be used only for digital signatures. Note that since the private key is known only to its owner, and the private key is used to digitally sign messages, signatures can be generated only by the owner of that private key. Since the corresponding public key is available to anyone who is interested, anyone can successfully verify the digital signature. The details of the DSA algorithm are a bit confusing, [15] but in essence the signature is computed by raising the original message, which is really just an arbitrary precision number, to a power that is kept secret. Verification is then the inverse operation, which calculates the modular logarithm from the signature, using a secret key that speeds the process. Since the sender then sends the original message along with the signature, the receiver has all the information to make the comparison, thus allowing the receiver to detect any message tampering that may have occurred.
Just as we saw in the case of RSA signing, when we want to sign a long message, it is inefficient and unnecessary to sign the entire message. Therefore, we first create a message hash (i.e., a digest), and sign this hash rather than the entire message. This is viable because it would be very difficult to forge the message such that the resulting hash would match the original message hash. How DSA WorksAn overview of the gory details of how DSA works is provided here. As you can see, there is a bit more to it than just the discrete logarithm problem discussed earlier. We won't go into an explanation of why each step is necessary or why they work the way they do. Instead, this description is intended only as an outline of the scheme, which can be used as a basis for an actual DSA implementation. From these details, you can see that the implementation of DSA is not trivial, and we are rather fortunate that cryptographic libraries, such as the .NET Framework, provide this implementation for us! GENERATING THE KEY
SIGNING THE MESSAGE
VERIFYING THE SIGNATURE
 |
EAN: 2147483647
Pages: 126