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.

Filed under: Computation, Cryptography, Maxima, Sage, Software | 4 Comments »