nettle: DSA
1
1 6.7.2 DSA
1 ---------
1
1 The DSA digital signature algorithm is more complex than RSA. It was
1 specified during the early 1990s, and in 1994 NIST published FIPS 186
1 which is the authoritative specification. Sometimes DSA is referred to
1 using the acronym DSS, for Digital Signature Standard. The most recent
1 revision of the specification, FIPS186-3, was issued in 2009, and it
1 adds support for larger hash functions than sha1.
1
1 For DSA, the underlying mathematical problem is the computation of
1 discrete logarithms. The public key consists of a large prime ‘p’, a
1 small prime ‘q’ which is a factor of ‘p-1’, a number ‘g’ which generates
1 a subgroup of order ‘q’ modulo ‘p’, and an element ‘y’ in that subgroup.
1
1 In the original DSA, the size of ‘q’ is fixed to 160 bits, to match
1 with the SHA1 hash algorithm. The size of ‘p’ is in principle
1 unlimited, but the standard specifies only nine specific sizes: ‘512 +
1 l*64’, where ‘l’ is between 0 and 8. Thus, the maximum size of ‘p’ is
1 1024 bits, and sizes less than 1024 bits are considered obsolete and not
1 secure.
1
1 The subgroup requirement means that if you compute
1
1 g^t mod p
1
1 for all possible integers ‘t’, you will get precisely ‘q’ distinct
1 values.
1
1 The private key is a secret exponent ‘x’, such that
1
1 g^x = y mod p
1
1 In mathematical speak, ‘x’ is the “discrete logarithm” of ‘y’ mod
1 ‘p’, with respect to the generator ‘g’. The size of ‘x’ will also be
1 about the same size as ‘q’. The security of the DSA algorithm relies on
1 the difficulty of the discrete logarithm problem. Current algorithms to
1 compute discrete logarithms in this setting, and hence crack DSA, are of
1 two types. The first type works directly in the (multiplicative) group
1 of integers mod ‘p’. The best known algorithm of this type is the
1 Number Field Sieve, and it’s complexity is similar to the complexity of
1 factoring numbers of the same size as ‘p’. The other type works in the
1 smaller ‘q’-sized subgroup generated by ‘g’, which has a more difficult
1 group structure. One good algorithm is Pollard-rho, which has
1 complexity ‘sqrt(q)’.
1
1 The important point is that security depends on the size of _both_
1 ‘p’ and ‘q’, and they should be chosen so that the difficulty of both
1 discrete logarithm methods are comparable. Today, the security margin
1 of the original DSA may be uncomfortably small. Using a ‘p’ of 1024
1 bits implies that cracking using the number field sieve is expected to
1 take about the same time as factoring a 1024-bit RSA modulo, and using a
1 ‘q’ of size 160 bits implies that cracking using Pollard-rho will take
1 roughly ‘2^80’ group operations. With the size of ‘q’ fixed, tied to
1 the SHA1 digest size, it may be tempting to increase the size of ‘p’ to,
1 say, 4096 bits. This will provide excellent resistance against attacks
1 like the number field sieve which works in the large group. But it will
1 do very little to defend against Pollard-rho attacking the small
1 subgroup; the attacker is slowed down at most by a single factor of 10
1 due to the more expensive group operation. And the attacker will surely
1 choose the latter attack.
1
1 The signature generation algorithm is randomized; in order to create
11 a DSA signature, you need a good source for random numbers (⇒
Randomness). Let us describe the common case of a 160-bit ‘q’.
1
1 To create a signature, one starts with the hash digest of the
1 message, ‘h’, which is a 160 bit number, and a random number ‘k, 0<k<q’,
1 also 160 bits. Next, one computes
1
1 r = (g^k mod p) mod q
1 s = k^-1 (h + x r) mod q
1
1 The signature is the pair ‘(r, s)’, two 160 bit numbers. Note the
1 two different mod operations when computing ‘r’, and the use of the
1 secret exponent ‘x’.
1
1 To verify a signature, one first checks that ‘0 < r,s < q’, and then
1 one computes backwards,
1
1 w = s^-1 mod q
1 v = (g^(w h) y^(w r) mod p) mod q
1
1 The signature is valid if ‘v = r’. This works out because ‘w = s^-1
1 mod q = k (h + x r)^-1 mod q’, so that
1
1 g^(w h) y^(w r) = g^(w h) (g^x)^(w r) = g^(w (h + x r)) = g^k
1
1 When reducing mod ‘q’ this yields ‘r’. Note that when verifying a
1 signature, we don’t know either ‘k’ or ‘x’: those numbers are secret.
1
1 If you can choose between RSA and DSA, which one is best? Both are
1 believed to be secure. DSA gained popularity in the late 1990s, as a
1 patent free alternative to RSA. Now that the RSA patents have expired,
1 there’s no compelling reason to want to use DSA. Today, the original
1 DSA key size does not provide a large security margin, and it should
1 probably be phased out together with RSA keys of 1024 bits. Using the
1 revised DSA algorithm with a larger hash function, in particular,
1 SHA256, a 256-bit ‘q’, and ‘p’ of size 2048 bits or more, should provide
1 for a more comfortable security margin, but these variants are not yet
1 in wide use.
1
1 DSA signatures are smaller than RSA signatures, which is important
1 for some specialized applications.
1
1 From a practical point of view, DSA’s need for a good randomness
1 source is a serious disadvantage. If you ever use the same ‘k’ (and
1 ‘r’) for two different message, you leak your private key.
1
1 6.7.2.1 Nettle’s DSA support
1 ............................
1
1 Like for RSA, Nettle represents DSA keys using two structures,
1 containing values of type ‘mpz_t’. For information on how to customize
1 allocation, see ⇒GMP Allocation (gmp)Custom Allocation. Nettle’s
1 DSA interface is defined in ‘<nettle/dsa.h>’.
1
1 A DSA group is represented using the following struct.
1
1 -- Context struct: dsa_params p q g
1 Parameters of the DSA group.
1
1 -- Function: void dsa_params_init (struct dsa_params *PARAMS)
1 Calls ‘mpz_init’ on all numbers in the struct.
1
1 -- Function: void dsa_params_clear (struct dsa_params *PARAMSparams)
1 Calls ‘mpz_clear’ on all numbers in the struct.
1
1 -- Function: int dsa_generate_params (struct dsa_params *PARAMS, void
1 *RANDOM_CTX, nettle_random_func *RANDOM, void *PROGRESS_CTX,
1 nettle_progress_func *PROGRESS, unsigned P_BITS, unsigned
1 Q_BITS)
1 Generates paramaters of a new group. The PARAMS struct should be
1 initialized before you call this function.
1
1 RANDOM_CTX and RANDOM is a randomness generator.
1 ‘random(random_ctx, length, dst)’ should generate ‘length’ random
11 octets and store them at ‘dst’. For advice, see ⇒
Randomness.
1
1 PROGRESS and PROGRESS_CTX can be used to get callbacks during the
1 key generation process, in order to uphold an illusion of progress.
1 PROGRESS can be NULL, in that case there are no callbacks.
1
1 P_BITS and Q_BITS are the desired sizes of ‘p’ and ‘q’. To
1 generate keys that conform to the original DSA standard, you must
1 use ‘q_bits = 160’ and select P_BITS of the form ‘p_bits = 512 +
1 l*64’, for ‘0 <= l <= 8’, where the smaller sizes are no longer
1 recommended, so you should most likely stick to ‘p_bits = 1024’.
1 Non-standard sizes are possible, in particular ‘p_bits’ larger than
1 1024, although DSA implementations can not in general be expected
1 to support such keys. Also note that using very large P_BITS, with
1 Q_BITS fixed at 160, doesn’t make much sense, because the security
1 is also limited by the size of the smaller prime. To generate DSA
1 keys for use with SHA256, use ‘q_bits = 256’ and, e.g., ‘p_bits =
1 2048’.
1
1 Returns one on success, and zero on failure. The function will
1 fail if Q_BITS is too small, or too close to P_BITS.
1
1 Signatures are represented using the structure below.
1
1 -- Context struct: dsa_signature r s
1
1 -- Function: void dsa_signature_init (struct dsa_signature *SIGNATURE)
1 -- Function: void dsa_signature_clear (struct dsa_signature *SIGNATURE)
1 You must call ‘dsa_signature_init’ before creating or using a
1 signature, and call ‘dsa_signature_clear’ when you are finished
1 with it.
1
1 Keys are represented as bignums, of type ‘mpz_t’. A public keys
1 represent a group element, and is of the same size as ‘p’, while a
1 private key is an exponent, of the same size as ‘q’.
1
1 -- Function: int dsa_sign (const struct dsa_params *PARAMS, const mpz_t
1 X, void *RANDOM_CTX, nettle_random_func *RANDOM, size_t
1 DIGEST_SIZE, const uint8_t *DIGEST, struct dsa_signature
1 *SIGNATURE)
1 Creates a signature from the given hash digest, using the private
1 key X. RANDOM_CTX and RANDOM is a randomness generator.
1 ‘random(random_ctx, length, dst)’ should generate ‘length’ random
11 octets and store them at ‘dst’. For advice, see ⇒
Randomness. Returns one on success, or zero on failure. Signing
1 can fail only if the key is invalid, so that inversion modulo ‘q’
1 fails.
1
1 -- Function: int dsa_verify (const struct dsa_params *PARAMS, const
1 mpz_t Y, size_t DIGEST_SIZE, const uint8_t *DIGEST, const
1 struct dsa_signature *SIGNATURE)
1 Verifies a signature, using the public key y. Returns 1 if the
1 signature is valid, otherwise 0.
1
1 To generate a keypair, first generate a DSA group using
1 ‘dsa_generate_params’. A keypair in this group is then created using
1
1 -- Function: void dsa_generate_keypair (const struct dsa_params
1 *PARAMS, mpz_t PUB, mpz_t KEY, void *RANDOM_CTX,
1 nettle_random_func *RANDOM)
1 Generates a new keypair, using the group PARAMS. The public key is
1 stored in PUB, and the private key in KEY. Both variables must be
1 initialized using ‘mpz_init’ before this call.
1
1 RANDOM_CTX and RANDOM is a randomness generator.
1 ‘random(random_ctx, length, dst)’ should generate ‘length’ random
11 octets and store them at ‘dst’. For advice, see ⇒
Randomness.
1
1 6.7.2.2 Old, deprecated, DSA interface
1 ......................................
1
1 Versions before nettle-3.0 used a different interface for DSA
1 signatures, where the group parameters and the public key was packed
1 together as ‘struct dsa_public_key’. Most of this interface is kept for
1 backwards compatibility, and declared in ‘nettle/dsa-compat.h’. Below
1 is the old documentation. The old and new interface use distinct names
1 and don’t confict, with one exception: The key generation function. The
1 ‘nettle/dsa-compat.h’ redefines ‘dsa_generate_keypair’ as an alias for
1 ‘dsa_compat_generate_keypair’, compatible with the old interface and
1 documented below.
1
1 The old DSA functions are very similar to the corresponding RSA
1 functions, but there are a few differences pointed out below. For a
1 start, there are no functions corresponding to ‘rsa_public_key_prepare’
1 and ‘rsa_private_key_prepare’.
1
1 -- Context struct: dsa_public_key p q g y
1 The public parameters described above.
1
1 -- Context struct: dsa_private_key x
1 The private key ‘x’.
1
1 Before use, these structs must be initialized by calling one of
1
1 -- Function: void dsa_public_key_init (struct dsa_public_key *PUB)
1 -- Function: void dsa_private_key_init (struct dsa_private_key *KEY)
1 Calls ‘mpz_init’ on all numbers in the key struct.
1
1 When finished with them, the space for the numbers must be
1 deallocated by calling one of
1
1 -- Function: void dsa_public_key_clear (struct dsa_public_key *PUB)
1 -- Function: void dsa_private_key_clear (struct dsa_private_key *KEY)
1 Calls ‘mpz_clear’ on all numbers in the key struct.
1
1 Signatures are represented using ‘struct dsa_signature’, described
1 earlier.
1
1 For signing, you need to provide both the public and the private key
1 (unlike RSA, where the private key struct includes all information
1 needed for signing), and a source for random numbers. Signatures can
1 use the SHA1 or the SHA256 hash function, although the implementation of
1 DSA with SHA256 should be considered somewhat experimental due to lack
1 of official test vectors and interoperability testing.
1
1 -- Function: int dsa_sha1_sign (const struct dsa_public_key *PUB, const
1 struct dsa_private_key *KEY, void *RANDOM_CTX,
1 nettle_random_func RANDOM, struct sha1_ctx *HASH, struct
1 dsa_signature *SIGNATURE)
1 -- Function: int dsa_sha1_sign_digest (const struct dsa_public_key
1 *PUB, const struct dsa_private_key *KEY, void *RANDOM_CTX,
1 nettle_random_func RANDOM, const uint8_t *DIGEST, struct
1 dsa_signature *SIGNATURE)
1 -- Function: int dsa_sha256_sign (const struct dsa_public_key *PUB,
1 const struct dsa_private_key *KEY, void *RANDOM_CTX,
1 nettle_random_func RANDOM, struct sha256_ctx *HASH, struct
1 dsa_signature *SIGNATURE)
1 -- Function: int dsa_sha256_sign_digest (const struct dsa_public_key
1 *PUB, const struct dsa_private_key *KEY, void *RANDOM_CTX,
1 nettle_random_func RANDOM, const uint8_t *DIGEST, struct
1 dsa_signature *SIGNATURE)
1 Creates a signature from the given hash context or digest.
1 RANDOM_CTX and RANDOM is a randomness generator.
1 ‘random(random_ctx, length, dst)’ should generate ‘length’ random
11 octets and store them at ‘dst’. For advice, see ⇒
Randomness. Returns one on success, or zero on failure. Signing
1 fails if the key size and the hash size don’t match.
1
1 Verifying signatures is a little easier, since no randomness
1 generator is needed. The functions are
1
1 -- Function: int dsa_sha1_verify (const struct dsa_public_key *KEY,
1 struct sha1_ctx *HASH, const struct dsa_signature *SIGNATURE)
1 -- Function: int dsa_sha1_verify_digest (const struct dsa_public_key
1 *KEY, const uint8_t *DIGEST, const struct dsa_signature
1 *SIGNATURE)
1 -- Function: int dsa_sha256_verify (const struct dsa_public_key *KEY,
1 struct sha256_ctx *HASH, const struct dsa_signature
1 *SIGNATURE)
1 -- Function: int dsa_sha256_verify_digest (const struct dsa_public_key
1 *KEY, const uint8_t *DIGEST, const struct dsa_signature
1 *SIGNATURE)
1 Verifies a signature. Returns 1 if the signature is valid,
1 otherwise 0.
1
1 Key generation uses mostly the same parameters as the corresponding
1 RSA function.
1
1 -- Function: int dsa_compat_generate_keypair (struct dsa_public_key
1 *PUB, struct dsa_private_key *KEY, void *RANDOM_CTX,
1 nettle_random_func RANDOM, void *PROGRESS_CTX,
1 nettle_progress_func PROGRESS, unsigned P_BITS, unsigned
1 Q_BITS)
1 PUB and KEY is where the resulting key pair is stored. The structs
1 should be initialized before you call this function.
1
1 RANDOM_CTX and RANDOM is a randomness generator.
1 ‘random(random_ctx, length, dst)’ should generate ‘length’ random
11 octets and store them at ‘dst’. For advice, see ⇒
Randomness.
1
1 PROGRESS and PROGRESS_CTX can be used to get callbacks during the
1 key generation process, in order to uphold an illusion of progress.
1 PROGRESS can be NULL, in that case there are no callbacks.
1
1 P_BITS and Q_BITS are the desired sizes of ‘p’ and ‘q’. See
1 ‘dsa_generate_keypair’ for details.
1