CIS 798. Digital Signature Standard.

Types of digital signatures that we won't discuss:

Fail-stop digital signature. A digital signature system has this property if a signer can prove that a message which was signed with his or her key, based on a fraudulent attack, is a fake.
Proxy digital signature. A digital signature system has this property if a signer can give his authority to sign a message to someone else, without revealing his digital signature to the ultimate receiver of the message (signed by a proxy).
Designated-confirmer digital signatures. These are protocols that allow a signer to designate a confirmer, possible herself, whose cooperation is necessary for the verification of digital signatures. This prevents the exact copying of digital signatures.

Digital signature scheme: A digital signature scheme consists of a finite set P of plain-texts, a finite set S of signatures, and a finite key-space K such that, for each k in K, we have a signing algorithm Sign_k: P --> S and a verification algorithm Verify_k: P x S --> bool such that Verify_k(M,S) = true "iff" S = Sign_k(M). The algorithms Sign_k and Verify_k should be efficiently derivable, given k, and should have reasonable performance. Needless to say, given M, an opponent should have no chance of producing some S with S = Sign_k(M), unless the opponent knows the key k.

Digital signature standard:

Generation of system parameters: The standard requires
- a prime number p with L significant bits, where L is any multiple of 64 in the range 512 <= L <= 1024;
- a prime number q with 160 significant bits such that q divides p-1;
- g = h^(p-1)/q mod p, where 2 <= h <= p - 2 and g <= 2;
- randomly generated numbers x and k satisfying 1 <= x <= q - 1 and 1 <= k <= q - 1;
- and y = g^x mod p.
Generation of a digital signature: Given a message M, the prover computes the pair of numbers (r,s) as a digital signature of M:
r = (g^k mod p) mod q
s = (k^-1 (hash(M) + xr)) mod q.
Recall that hash(M) produces a 160-bit string, so in our present context hash(M) denotes the integer whose binary representation equals that 160-bit string. Note that an implementation will have to conduct such a conversion before computing s.
Digital signature verification: A verifier is well advised to obtain all the public information, the two primes p and q, the base g, and the prover's public signature key y, in an authenticated manner. Thereafter, assume that the verifier received M' and the pair (r',s'), the putative signature of the original M. If r' and s' are positive and less than q, the verification algorithm is invoked. Otherwise, the signature is rejected immediately. For the actual verification, the verifier computes
w = (s')^-1 mod q
u1 = hash(M') w mod q
u2 = r'w mod q
v = (g^u1 y^u2 mod p) mod q.
If v=r', then the verifier accepts that message M was signed by the prover. Otherwise, the signature is rejected.

Generation of the primes p and q:

    DSS_Prime_Generation(int l,int lseed) \{
    
    // generates two prime numbers p and q for the DSS
    // input: an integer l between 0 and 8
    //        an integer lseed, the length of the seed
    // output: a 160-bit prime q
    //         a prime p with 512 + 64*l bits such that q divides p - 1
    //         the value of an internal counter
    //         the value of the successful seed

	int L = 512 + 64 * l;
	int n = L - 1 div 160;
	int b = L - 1 mod 160;
	bool q_not_prime = true;

   loc: while q_not_Prime \{

          BigInteger seed = Random(1,2**lseed - 1) XOR 2**(lseed - 1); 
	  BigInteger u = hash(seed) XOR hash(seed + 1\mod 2**lseed);
	  BigInteger q = u OR 2**159 OR 1;
	  q_not_prime = Miller-Rabin(q,80);

        \}

        int counter = 0;
	int offset =  2;

	while counter <= 4096 \{

	  for (int k = 0; k <= n; ++k) v[k] = hash(seed + offset + k mod 2**lseed);
	  BigInteger w = v[0];
	  for (int k = 1; k < n; ++k) w = w + v[k] * 2**(k*160);
	  w = w + (v[n] mod 2**b) * 2**(2*160);
	  BigInteger x = w + 2**(L - 1);
	  BigInteger c = x mod 2*q;
	  BigInteger p = x - (c - 1);

	  if p >= 2**(L-1) && Miller-Rabin(p,80) return (q,p,counter,seed);
	  counter = counter + 1;
          offset = offset + n + 1;
	  goto loc;

Verifying authentic generation of p and q: Write and implement an algorithm DSS_Proper_Primes?(q,p,counter,seed)} which returns a boolean; it simulates the computation that happens in the call DSS_Prime_Generation(l,lseed), but for the length lseed of the given value of the seed, and returns true if, and only if, the simulation computes the same values as the input values for counter, p, and q.

An attack with a morale (exercise 7, page 147): Explain how you could compute the secret digital signature key x, if you could observe the communication of two runs of this protocols, provided that the prover used the same random number k for signing two different messages M1 and M2. Let r1, r2, s1, and s2 be defined as in DSS above, for messages M1 and M2 respectively.

Argue that r_1 equals r_2.
Show: If s1 - s2 is different from 0 mod q, then
k = (s1 - s2)^-1 (hash(M1) - hash(M2)) mod q.
Prove that, in the DSS system, we have
x = (s k - hash(M)) r^-1 mod q
in general.
Use the previous items to explain your attack. Detail what you know and compute and in which order such knowledge arises.
What property of hash functions makes it very unlikely that s1 - s2 = 0 mod q?
Does this attack work if the two messages are identical?

Security: Above we saw that implementation flaws can corrupt the security of DSS. There are also two principal concerns. The index-calculus methods are techniques for computing the discrete logarithm in Z_{p. There are also methods for computing the discrete logarithm
of the subgroup of order q generated by g; these methods are of the order
sqrt(q).}

Performance: As for implementations, DSS is rather fast in its signature generation, but rather slow in its signature verification. With a digital signature scheme based on RSA, it is typically the other way around (e.g. for a small private-key exponent). This creates trade-offs, but there are often no optimal solutions. For example, smartcards may have to perform decryption and encryption as well.

DSS and elliptic curves: The digital signature in the DSS consists of the pair (r,s) which requires 320 bits for its representation. One may read the DSS protocol at a more abstract level, taking note that most of its basic steps make still sense if they are interpreted to apply in any finite field (F,+,0,*,1). In a field, all non-zero elements have a multiplicative inverse and the operations + and * satisfy laws we intuitively apply in the field of real numbers.

Let p >3 be a prime and a,b in {1,2,...,p-1} such that

(1) 4a³ + 27b² is different from 0 mod p.

An elliptic curve E(Z_p) over Z_p has the numbers a and b as implicit parameters; the set E(Z_p) consists of all pairs (x,y) which satisfy
(2) y² = x³ + ax + b mod p (0 <= x,y <= p-1)

together with an additional element, O, the ``point at infinity''.

Let p be 13, a be 4, and b be 12. Then the equation above is met, and the set E(Z₁₃), without O, consists of the pairs

(0, 5)   (0, 8)  (1, 2)  (1, 11)  (3, 5)  (3, 8)   (4, 1)   (4, 12)  (5, 1)
(5, 12)  (8, 6)  (8, 7)  (9, 6)   (9, 7)  (10, 5)  (10, 8)  (11, 3)  (11, 10)

Note the set E(Z₁₃) has 19 elements. In general, the number of elements will be of the "order" p. Compare that to the number of units for p, which is p-1. From the equation above, it follows that (x,-y) is an element on the curve whenever (x,y) is one. If such curves are defined over the real numbers, then two points on that curve determine a third one, the ``addition'' of the former two. This geometric operation can be transfered to the case E(Z_p) and the operation can be expressed in a completely algebraic fashion.

Group structure on elliptic curve:

O + O = O;
O + (x,y) = (x,y) + O = (x,y);
(x,y) + (x,-y) = O;
If (x1,y1) and (x2,y2) are elements on the curve with y1 different from y2 mod p, then define (x1,y1) + (x2,y2) to be (x3,y3), where
l = (y2 - y1)(x2-x1)^-1mod p, if (x1,y1) and (x2,y2) are different;
l = (3x1² + a)(2y1)^-1 mod p, otherwise.

x3 = l² - x1 - x2 mod p
y3 = l(x1 - x3) - y1 mod p.

If P = (x,y), then we write -P for the pair (x,-y). Generally, for r, we define

(3) r(x,y) = (x,y) + (x,y) + .... + (x,y) [r times]
Example: For p = 23, a = 1, and b = 1, we have points P = (3,10) and Q = (9,7). We compute P + Q as follows:
l = (7-10)(9-3)^-1 = -3*6^-1 = 11 mod 23
x3 = 11² - 3 - 9 = 6 - 3 - 9 = -6 = 13 mod 23
y3 = 11(3 - (-6)) - 10 = 11*9 - 10 = 89 = 20 mod 23.

Thus, P + Q = (17,20).
As for scalar multiplication, let R = (3,10). Then 2R = R + R. The latter computes to:
l = (3*3² + 1)*20^-1 = 5*20 = 6 mod 23
x3 = 6² - 6 = 7 mod 23
y3 = 6(3 - 7) - 10 = -24 - 10 = 12 mod 23.

Hence, 2R = (7,12).

ECDSA: In the elliptic curve digital signature algorithm (ECDSA), we modify the DSS only at some key places:

We replace Z_p with some elliptic curve E(Z_p) over Z_p such that the order of E(Z_p) has a ``large'' prime factor q, say 160-bits long.
We find a point G on that curve whose order is q (G was called g in the DSS).
The public signature x is computed as in DSS as a random value between 1 and q - 1, but now the secret signature Y, called y in the DSS, is defined as the scalar multiplication G with the scalar x:
Y = xG.
The computation of r is entirely different now, for r was computed in Z_p before:
- Compute the random k in the same manner as for the DSS.
- Let (x1,y1) be the point on the curve obtained by computing kG. If x1 mod q = 0, go to the previous item and re-compute k. Otherwise, r = x1 mod q.
The computation of s now proceeds exactly as for the DSS.
To verify a digital signature, the computations of w, u1, and u2 are as before, but we replace the exponentials with scalar multiplications in the elliptic curve:
(x0,y0) = u1G + u2Y
v = x0 mod q.

Note that + in this equation refers to the addition of points in the elliptic curve. The ``scalar multiplication'' |---> kG is of course just the exponentiation operation in the group determined by the elliptic curve. The security of the ECDSA therefore relies at the very least on the fact that it is hard to compute logarithms in this group. With a 160bit q, this algorithm may provide similar security as the DSS. The apparent win is that one can often choose a much smaller p to generate a subgroup of order q than in the case of the DSS. Also, scalar multiplication may be easier to implement than exponentiation before, if p is chosen appropriately.

Feel free to consult me during my Office Hours: W 2:00--3:00 P.M., U 10:30--11:30 A.M.

Michael Huth (huth@cis.ksu.edu)