Introduction to Cryptography with Open-Source Software

160 Cryptography with Open-Source Software

sage: p = 1031

sage: q = 103

sage: a = mod(14,p)

sage: g = a^((p-1)/q); g

320

sage: A = 70

sage: B = g^A; B

48

Now create the message and sign it:

sage: m = 500

sage: k = 25

sage: r = mod(g^k,q); r

95

sage: s = (m+A*r)/k; s

80

Now the signatur e is easily verified:

sage: x = m/s; x

32

sage: y = r/s; y

72

sage: v = mod(g^x*B^y,q)

95

sage: v==r

True

Choosing values for use in t he DSS

To be s e c ure, the primes p and q need to be large. It is too inefficient

to choose a large prime p first, and then try to factor p − 1 in the hopes of

obtaining a large enough factor q. It is better to first choose a prime q, and

then use a random multiplier ...