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.
Maxima
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.
(%i1) p:next_prime(random(10^80));
(%i2) factor(p-1);
After a few tries, I found
p = 182842970179003336959233156794188485625560973915508949565601
89183057229685434897
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:
primroot(p):=block(
[f:ifactors(p-1),n,i:1],
if not(primep(p)) then error("Your number is not prime"),
n:length(f),
do (
i:i+1,
if not member(1,makelist(power_mod(i,(p-1)/f[j][1],p),j,1,n)) then
return(i)
)
);
So:
(%i3) a:primroot(p);
(%o3) 5
(%i4) g:power_mod(a,(p-1)/q,p);
The private/public key pairs:
(%i5) A:random(q-1);
(%i6) B:power_mod(g,A,p);
Now we can choose a random message a sign it (for ease we won’t show the outputs, which are just long numbers):
(%i7) m:random(p);
(%i8) k:random(q-1);
(%i9) r:mod(power_mod(g,k,p),q);
(%i10) s:mod(inv_mod(k,q)*(m+A*r),q);
Now to verify the signature:
(%i11) x:mod(inv_mod(s,q)*m,q);
(%i12) y:mod(inv_mod(s,q)*r,q);
(%i13) v:mod(mod(power_mod(g,x,p)*power_mod(B,y,p),p),q);
(%i14) is(v=r)
(%o14) true
Sage
As with Maxima, we start by finding and . We simply repeat
sage: p=next_prime(randint(1,10^80))
sage: factor(p-1)
until we find values we want. I found
p =
530156743088749972013047250493987281452419479410412138
17513510820559804089810293
q= 2199623526308059394919085303004156101
Then
sage: a=Mod(primitive_root(p),p)
returns 5. The extra Mod( ,p) ensures that the type of is an element of the
ring of integers modulo 
:
sage: parent(a)
Ring of integers modulo 530156743088749972013047250493987281
45241947941041213817513510820559804089810293
Now we can calculate the other values we need:
sage: g=a^((p-1)/q)
sage: g
530156743088749972013047250493987281211397896967807817
18309906946321326881261201
and the private/public key pairs:
sage: A=randint(1,q-1);A
617088481431564693290032924639855166L,
sage: B=g^A;B
1052251014343945276262934677066619589736007844895332445
1397254657133312260200438
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 :
sage: m=randint(1,p)
and sign it (as with Maxima we won’t show any of the values):
sage: k=randint(1,q-1)
sage: r=mod(g^k,q)
sage: s=(m+A*r)/k
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:
sage: x=m/s
sage: y=r/s
sage: v=mod(g^x*B^y,q)
sage: v==r
True
Neat.
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:
Maxima: y:mod(inv_mod(s,q)*r,q);
Sage: y=r/s
Maxima: v:mod(mod(power_mod(g,x,p)*power_mod(B,y,p),p),q);
Sage: v=mod(g^x*B^y,q)
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:
(%i1) modulus:97;
(%i2) a:rat(5);
(%i3) a^75;
(%o3) -34
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:
(%i1) p:1031;
(%o1) 1031
(%i2) q:103;
(%o2) 103
(%i3) modulus:p;
(%o3) 1031
(%i4) a:rat(14);
(%o4) 14
(%i5) g:a^((p-1)/q);
(%o5) 320
(%i6) A:rat(70);
(%o6) 70
(%i7) B:g^A;
(%o8) 48
Now to sign a message 
using the “random” value 
:
(%i9) m:500;
(%o9) 500
(%i10) k:25;
(%o10) 25
(%i11) r:mod(g^k,q);
(%o11) 95
At this stage we are going to start performing operations modulo , so we change the modulus:
(%i12) modulus:q;
(%o12) 103
(%i13) s:(m+A*r)/k;
(%o13) -23
We have thus created the signature (with balanced modulo values); now for the verification:
(%i14) x:m/s;
(%o14) 32
(%i15) y:r/s;
(%o15) -31
To compute the final value we’ll change the modulus once more:
(%i16) modulus:p;
(%o16) 1031
(%i17) v:mod(g^x*B^y,q);
(%o17) 95
(%i18) is(v=r);
(%o18) true
and we’re done, all with very simple commands.
, and so we only have to find an approximation for positive 
.![\displaystyle{\Phi(z)\approx\left\{\begin{array}{ll}\displaystyle{z\left(\frac{9-z^2}{24}\right)+\frac{1}{2}}&\mbox{if }0\le z\le 1\\[5mm] \displaystyle{\frac{(z-3)^3}{48}+1}&\mbox{if }z\ge 1\end{array}\right.}](http://s0.wp.com/latex.php?latex=%5Cdisplaystyle%7B%5CPhi%28z%29%5Capprox%5Cleft%5C%7B%5Cbegin%7Barray%7D%7Bll%7D%5Cdisplaystyle%7Bz%5Cleft%28%5Cfrac%7B9-z%5E2%7D%7B24%7D%5Cright%29%2B%5Cfrac%7B1%7D%7B2%7D%7D%26%5Cmbox%7Bif+%7D0%5Cle+z%5Cle+1%5C%5C%5B5mm%5D++%5Cdisplaystyle%7B%5Cfrac%7B%28z-3%29%5E3%7D%7B48%7D%2B1%7D%26%5Cmbox%7Bif+%7Dz%5Cge+1%5Cend%7Barray%7D%5Cright.%7D&bg=ffffff&fg=333333&s=0 "\displaystyle{\Phi(z)\approx\left\{\begin{array}{ll}\displaystyle{z\left(\frac{9-z^2}{24}\right)+\frac{1}{2}}&\mbox{if }0\le z\le 1\\[5mm] \displaystyle{\frac{(z-3)^3}{48}+1}&\mbox{if }z\ge 1\end{array}\right.}")
. This piecewise polynomial function provides a nice quick-and-dirty approximation to the normal CDF.
, where all the 
values are distinct, is given by
and is equal to one if 
.
.
is one. This means that in particular
contain an 
term and therefore produce zero for 
in the Lagrangian polynomial can be written as
.
and 
. First, Maxima:
![\displaystyle{{\rm Define}\quad q(x)=\prod_{i=1}^n(x-xs[i])}](http://s0.wp.com/latex.php?latex=%5Cdisplaystyle%7B%7B%5Crm+Define%7D%5Cquad+q%28x%29%3D%5Cprod_%7Bi%3D1%7D%5En%28x-xs%5Bi%5D%29%7D&bg=ffffff&fg=333333&s=0 "\displaystyle{{\rm Define}\quad q(x)=\prod_{i=1}^n(x-xs[i])}")
![\displaystyle{qs:={\rm seq}\left(\left.\frac{d}{dx}(q(x))\right|x=xs[i],i,1,n\right)}](http://s0.wp.com/latex.php?latex=%5Cdisplaystyle%7Bqs%3A%3D%7B%5Crm+seq%7D%5Cleft%28%5Cleft.%5Cfrac%7Bd%7D%7Bdx%7D%28q%28x%29%29%5Cright%7Cx%3Dxs%5Bi%5D%2Ci%2C1%2Cn%5Cright%29%7D&bg=ffffff&fg=333333&s=0 "\displaystyle{qs:={\rm seq}\left(\left.\frac{d}{dx}(q(x))\right|x=xs[i],i,1,n\right)}")
![\displaystyle{{\rm Define }\quad p(x)=\sum_{i=1}^n\left(\frac{q(x)}{(x-xs[i]) \cdot qs[i]}ys[i]\right)}](http://s0.wp.com/latex.php?latex=%5Cdisplaystyle%7B%7B%5Crm+Define+%7D%5Cquad+p%28x%29%3D%5Csum_%7Bi%3D1%7D%5En%5Cleft%28%5Cfrac%7Bq%28x%29%7D%7B%28x-xs%5Bi%5D%29+%5Ccdot+qs%5Bi%5D%7Dys%5Bi%5D%5Cright%29%7D&bg=ffffff&fg=333333&s=0 "\displaystyle{{\rm Define }\quad p(x)=\sum_{i=1}^n\left(\frac{q(x)}{(x-xs[i]) \cdot qs[i]}ys[i]\right)}")
.
.
by 
these are defined as
:
.
.![[1,7]](http://s0.wp.com/latex.php?latex=%5B1%2C7%5D&bg=ffffff&fg=333333&s=0 "[1,7]")
:
.
.
is
is the fourth order Newton-Cotes rule, and 
is the Simpson rule over 
. Start with:
.
for 
for 
for 
define the sequences 
by 
and for all 
.
, and denoted
.
.
for 
but to keep the symbols down I won’t use that here.) Finally, and this is the basis for the iteration:
.
