ESIGN (an abbreviation for Efficient digital SIGNature) is another digital signature scheme whose security relies on the difficulty of factoring integers. It is a signature scheme with appendix and requires a one-way hash function h: {0,1}* —» Z„.

11.112 Algorithm Key generation for ESIGN

SUMMARY: each entity creates a public key and corresponding private key.

Each entity A should do the following:

  • 1. Select random primes p and q such that p > q and p, q are roughly of the same bitlength.
  • 2. Compute n = p2q.
  • 3. Select a positive integer к > 4.
  • 4. A’s public key is (n, k); A’s private key is (p, q).
  • 11.113 Algorithm ESIGN signature generation and verification

SUMMARY: the signing algorithm computes an integer s such that sk mod n lies in a certain interval determined by the message. Verification demonstrates that sk mod n does indeed lie hi the specified interval.

  • 1. Signature generation. To sign a message m which is a bitstring of arbitrary length, entity A should do the following:
    • (a) Compute v = h(m).
    • (b) Select a random secret integer x, 0 < x < pq.
    • (c) Compute w = [((v — xk) mod n)/(pq)] and у = w (kxk~1)~1 mod p.
    • (d) Compute s = x + ypq mod n.
    • (e) A’s signature for m is s.
  • 2. Verification. To verify A’s signature s on m, В should do the following:
    • (a) Obtain A’s authentic public key (n, k).
    • (b) Compute и = sk mod n and г = h(m).
    • (c) If г < и < z + 2 Г§'s nl, accept the signature; else reject it.

Proof that signatureverificationworks. Note that sk = {x+ypq)k = J2i=o С1)хк~г {уряУ = xk + kypqxk~1 (mod n). But kxk_1 у = w (mod p) and, thus, kx*~ly = w + Ip for

some l € Z. Hence, sk = xk + pq(w + Ip) = xk + pqw = xk + pq )modl> =

xk + pq (mod n), where e = (xk — h(m)) mod pq. Therefore, sk =

xk + h(m) — xk + e = h(m) + e (mod гг). Since 0 < e < pq, it follows that h(m) < sk mod n < h(m) + pq < h(m) + 2 Гз nl, as required.

11.114 Example (ESIGN for artificially small parameters) In Algorithm 11.113, take messages to be integers m, 0 < m < n, and the hash function h to be h(m) = m.

Key generation. A selects prunes p = 17389 and q = 15401, к = 4, and computes n=p2q = 4656913120721. A’s public key is (n = 4656913120721, A: = 4); A’s private key is (p = 17389, q = 15401).

Signature generation. To sign the message m = 3111527988477, A computes v = h(m) = 3111527988477, and selects x = 14222 such that 0 < x < pq. A then computes w = [((u-arfc) mod n)/(pq) = [2848181921806/2678079891 = [10635.164141 = Ю636 and у = ■w(kxk~1)~1 modp = 10636(4 x 142223)-1 mod 17389 = 9567. Finally, A computes the signature s = x + ypq mod n = 2562119044985.

Signature verification. В obtains A’s public key (n = 4656913120721, к = 4), and computes и = sk mod n = 3111751837675. Since 3111527988477 < 3111751837675 < 3111527988477 + 229, В accepts the signature (here, [| lg nl = 29). □

  • 11.115 Note {security of ESIGN)
  • (i) The modulus n = p2q in Algorithm 11.113 differs from an RSA modulus by having a repeated factor of p. It is unknown whether or not moduli of this form are easier to factor than integers which are simply the product of two distinct primes.
  • (ii) Given a valid signature s for a message in, an adversary could forge a signature for a message ml if h(m') is such that h{m!) < и < h(m') + 2^1snl (where и = sk mod n). If an m! with this property is found, then s will be a signature for it. This will occur if h(m) and h(m') agree in the high-order (lg n)/3 bits. Assuming that h behaves like a random function, one would expect to try 2(lg n^3 different values of m' before observing this.
  • (iii) Another possible approach to forging is to find a pair of messages m and ml such that h(m) and h(m') agree in the high-order (lgn)/3 bits. By the birthday paradox (Fact 2.27(h)), one can expect to find such a pair in 0(2^ n)/6) trials. If an adversary is able to get the legitimate signer to sign m, the same signature will be a signature for in'.
  • (iv) For the size of the integer n necessary to make the factorization of n infeasible, (ii) and (iii) above are extremely unlikely possibilities.
  • 11.116 Note (performance characteristics of ESIGN signatures) Signature generation in Algorithm 11.113 is very efficient. For small values of к (e.g., к = 4), the most computationally intensive part is the modular inverse required in step lc. Depending on the implementation, this corresponds to a small number of modular multiplications with modulus p. For к = 4 and a 768-bit modulus n, ESIGN signature generation may be between one and two orders of magnitude (10 to 100 times) faster than RSA signature generation with an equivalent modulus size. Signature verification is also very efficient and is comparable to RSA with a small public exponent.
< Prev   CONTENTS   Source   Next >