The Digital Signature Algorithm, also known as the Digital Signature Standard is, as it name implies, a standard for digital signatures. Most digital signature algorithms work by reversing a public key cryptosystem: a message is signed with the sender’s private key, and the signature is verified using the sender’s public key. The DSA is based on the El Gamal scheme, with a few extras thrown in for extra security, and to make the signatures smaller.
It is set up with four values: a large prime , a prime which is a factor of , a primitive root of , and a value defined by
For security, is recommended to be at least 154 digits, and at least 48 digits.
Alice, the sender, chooses as her private key any value and calculates
as her public key. This is secure, by the discrete logarithm problem. The public key consists of the values and the private key is the value .
Given a message , a signature is computed as follows:
Alice chooses at random for which . She then computes:
and the two values are the signature of the message . We are assuming here that ; as in general most messages will be much larger, it is customary to sign not the message itself, but a cryptographic hash of the message, which will be a string of some fixed length (and shorter than ).
To verify the signature, Bob (the receiver) calculates the following values:
If then he accepts the signature.
To see why this works, note that from the definition of , we can write
and by multiplying through by we obtain:
This last equation can be written
Now we have
This algorithm has the advantage that its security is of order length of , but the signature values are much smaller – the size of .
Now let’s look at this algorithm in both Maxima and Sage.
We start by creating and . We will need to factor both to find a value of , and to find its primitive root. So we start by attempting to factor a few randomly chosen large primes, until we have a prime for which can be factored, and which also has a reasonably large prime factor .
We will use smaller values both of and than the algorithm requires, just to show how it works.
After a few tries, I found
p = 182842970179003336959233156794188485625560973915508949565601
q = 525970797581619193760592144581011744537
Maxima doesn’t have a built-in command to find primitive roots, but one can easily be written, using the fact that a primitive root a is a number for which
for all prime factors of . Here is one such program:
if not(primep(p)) then error("Your number is not prime"),
if not member(1,makelist(power_mod(i,(p-1)/f[j],p),j,1,n)) then
The private/public key pairs:
Now we can choose a random message a sign it (for ease we won’t show the outputs, which are just long numbers):
Now to verify the signature:
As with Maxima, we start by finding and . We simply repeat
until we find values we want. I found
returns 5. The extra
Mod( ,p) ensures that the type of is an element of the
ring of integers modulo :
Ring of integers modulo 530156743088749972013047250493987281
Now we can calculate the other values we need:
and the private/public key pairs:
Note that because of Sage’s handling of types, we don’t have to fuss with “power_mod”; since the type of is “element of “, so automatically are and , and powers are thus computed quickly, using the modular exponentiation algorithm.
Let’s choose a message, which will be any value less than :
and sign it (as with Maxima we won’t show any of the values):
since is in the ring , we need to change to be in the ring . This
will force to be also in this ring, so there is no need for any explicit calls to number theoretic functions.
Now we can verify the signature:
Both Maxima and Sage provide all the necessary functionality to compute and verify a digital signature (well, nearly all; we had to write our own program for primitive roots in Maxima), but of the two, Sage certainly allows for easier commands, with its mathematical types. For example:
Addendum: the use of “modulus” in Maxima
Richard Fateman (see comments below) pointed out that my comparison above is in fact incorrect. Maxima allows for very neat commands by use of “modulus”, which if set to any prime number, will effect all subsequent rational expressions. For example:
We see that the output is given in “balanced” form, where the residues are balanced about zero. However,. in Maxima modulus is a global property – it applies to all rational expressions, whereas in Sage different variables can have different modular types. However, by a judicious change of modulus, we can simplify the Maxima commands considerably. To show how to do this, we will deal with some very small numbers, so as to be able to show the outputs. We will use , and the primitive root of . First, the setup phase. Since everything here is done modulo , we will use this as the modulus value:
Now to sign a message using the “random” value :
At this stage we are going to start performing operations modulo , so we change the modulus:
We have thus created the signature (with balanced modulo values); now for the verification:
To compute the final value we’ll change the modulus once more:
and we’re done, all with very simple commands.
Filed under: Computation, Cryptography, Maxima, Sage, Software | 4 Comments »