The Digital Signature Algorithm in Maxima and Sage

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 p, a prime q which is a factor of p-1, a primitive root a of p, and a value g defined by

g=a^{(p-1)/q} bmod p.

For security, p is recommended to be at least 154 digits, and q at least 48 digits.

Alice, the sender, chooses as her private key any value A<q-1 and calculates

B=g^A bmod p

as her public key. This is secure, by the discrete logarithm problem. The public key consists of the values (p,q,g,B) and the private key is the value A.

Given a message m, a signature is computed as follows:

Alice chooses at random k for which 0<k<q-1. She then computes:

r = (g^kpmod{p})pmod{q}

s = k^{-1}(m+Ar)pmod{q}

and the two values (r,s) are the signature of the message m. We are assuming here that m<p; 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 p ).

To verify the signature, Bob (the receiver) calculates the following values:

x = s^{-1}mpmod{q},

y = s^{-1}rpmod{q},

v = (g^xB^ypmod{p})pmod{q}.

If v=r then he accepts the signature.

To see why this works, note that from the definition of s, we can write

m=(-Ar+ks)pmod{q}

and by multiplying through by s^{-1} we obtain:

s^{-1}m=(-Ars^{-1}+k)pmod{q}.

This last equation can be written

k= s^{-1}m+Ars^{-1}pmod{q}

= x+Aypmod{q}.

Now we have

r = (g^kpmod{p})pmod{q}

= (g^{x+Ay}pmod{p})pmod{q}

= (g^x(g^A)^ypmod{p})pmod{q}

= (g^xB^ypmod{p})pmod{q}

= v.

This algorithm has the advantage that its security is of order length of p, but the signature values are much smaller – the size of q.

Now let’s look at this algorithm in both Maxima and Sage.

Maxima

We start by creating p and q. We will need to factor p-1 both to find a value of q, and to find its primitive root. So we start by attempting to factor a few randomly chosen large primes, until we have a prime p for which p-1 can be factored, and which also has a reasonably large prime factor q.

We will use smaller values both of p and q 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

a^{(p-1)/t}  neq 1 bmod{p}

for all prime factors t of p-1. 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 p and q. 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 a is an element of the
ring of integers modulo p mathbb{Z}_p:

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 a is “element of mathbb{Z}_p“, so automatically are g and B, and powers are thus computed quickly, using the modular exponentiation algorithm.

Let’s choose a message, which will be any value less than p:

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 g is in the ring mathbb{Z}_p, we need to change r to be in the ring mathbb{Z}_q. This
will force s 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 p=1031, q=103, and the primitive root a=14 of p. First, the setup phase. Since everything here is done modulo p, 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 m=500 using the “random” value k=25:

(%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 q, 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.

4 thoughts on “The Digital Signature Algorithm in Maxima and Sage

  1. If you use the rational function package in Maxima, your programs will be shorter. Instead of
    power_mod(a,b,p)

    you could do this:

    modulus:p,
    a:rat(b),

    and then a^b will do the job. And inverse_mod would be 1/a or a^(-1).

    The representatives of the field used by this setup are balanced around zero — does that matter? E.g. mod 5 you have numbers -2 -1 0 1 2, not 0 1 2 3 4.

    Your blog was pointed out to me as an example of a Sage vs Maxima comparison, because it shows Sage commands to be easier to read.
    Maxima commands can be shortened using the rational function representation.

  2. This is very valuable information regarding digital signatures.This algorithm is very useful in digital signatures. Use of hashing function in this algorithm is really great to learn.

Leave a Reply

Your email address will not be published. Required fields are marked *