2. DSA and ECDSA Notations

In this section, we succinctly describe DSA and ECDSA and define our notations. The complete specifications for DSA and ECDSA can be found in [FIPS-186-4] and [X9.62], respectively.

2.1. Key Parameters

DSA and ECDSA work over a large group of prime size, in which the group operation is easy to compute, but the discrete logarithm is computationally infeasible with existing and foreseeable technology. The definition of the group is called the "key parameters". Key parameters may be shared between different key pairs with no ill effect on security; this is the usual case with ECDSA in particular.

DSA uses the following key parameters:

p
a large prime number (at least 1024 bits)

q
a sufficiently large prime number (at least 160 bits) that is also a divisor of p-1

g
a generator for the multiplicative subgroup of order q of integers modulo p

The group on which DSA will be computed consists of the values 'g^j mod p', where '^' denotes exponentiation and j ranges from 0 to q-1 (inclusive). The size of the group is q.

ECDSA uses the following key parameters:

E
an elliptic curve, defined over a given finite field

q
a sufficiently large prime number (at least 160 bits) that is a divisor of the curve order

G
a point of E, of order q

The group on which ECDSA will be computed consists of the curve points jG (multiplication of point G by integer j) where j ranges from 0 to q-1. G is such that qG = 0 (the "point at infinity" on the curve E). The size of the group is q. Note that these notations slightly differ from those described in [X9.62]; we use them in order to match those used for DSA.

2.2. Key Pairs

A DSA or ECDSA private key is an integer x taken modulo q. The relevant standards prescribe that x shall not be 0; hence, x is an integer in the range [1, q-1].

A DSA or ECDSA public key is computed from the private key x and the key parameters:

• For DSA, the public key is the integer: y = g^x mod p

• For ECDSA, the public key is the curve point: U = xG

2.3. Integer Conversions

Let qlen be the binary length of q. qlen is the smallest integer such that q is less than 2^qlen. This is the size of the binary representation of q without a sign bit (note that q, being a big prime, is odd, thus avoiding any ambiguity about the length of any integer equal to a power of 2). We define five conversion functions, which work on strings of bits, octets, and integers modulo q. qlen is the main parameter for these conversions.

In the following subsections, we use two other lengths, called blen
and rlen.  rlen is equal to qlen, rounded up to the next multiple of
8 (if qlen is already a multiple of 8, then rlen equals qlen;
otherwise, rlen is slightly larger, up to qlen+7).  Note that rlen is
unrelated to the value r, the first half of a generated signature.
blen is the length (in bits) of an input sequence of bits and may
vary between calls.  blen may be smaller than, equal to, or larger
than qlen.

2.3.1. Bits and Octets

Formally, all operations are defined on sequences of bits. A sequence is ordered; the first bit is said to be leftmost, while the last bit is rightmost.

On most software systems, bits are grouped into octets (sequences of eight bits). Binary data, e.g., the output of a hash function, is available as a sequence of octets. Whenever applicable, we consider that bits within an octet are ordered from most significant to least significant: the first (leftmost) bit within an octet has numerical value 128, while the last (rightmost) has numerical value 1.

2.3.2. Bit String to Integer

The bits2int transform takes as input a sequence of blen bits and outputs a non-negative integer that is less than 2^qlen. It consists of the following steps:

1. The sequence is first truncated or expanded to length qlen:

• if qlen < blen, then the qlen leftmost bits are kept, and subsequent bits are discarded;

• otherwise, qlen-blen bits (of value zero) are added to the left of the sequence (i.e., before the input bits in the sequence order).

2. The resulting sequence is then converted to an integer value using the big-endian convention: if input bits are called b_0 (leftmost) to b_(qlen-1) (rightmost), then the resulting value is:

b_0*2^(qlen-1) + b_1*2^(qlen-2) + ... + b_(qlen-1)*2^0

The bits2int transform can also be described in the following way: the input bit sequence (of length blen) is transformed into an integer using the big-endian convention. Then, if blen is greater than qlen, the resulting integer is divided by two to the power blen-qlen (Euclidian division: the remainder is discarded); in many software implementations of arithmetics on big integers, that division is equivalent to a "right shift" by blen-qlen bits.

2.3.3. Integer to Octet String

An integer value x less than q (and, in particular, a value that has been taken modulo q) can be converted into a sequence of rlen bits, where rlen = 8*ceil(qlen/8). This is the sequence of bits obtained by big-endian encoding. In other words, the sequence bits x_i (for i ranging from 0 to rlen-1) are such that:

x = x_0*2^(rlen-1) + x_1*2^(rlen-2) + ... + x_(rlen-1)

We call this transform int2octets. Since rlen is a multiple of 8 (the smallest multiple of 8 that is not smaller than qlen), then the resulting sequence of bits is also a sequence of octets, hence the name.

2.3.4. Bit String to Octet String

The bits2octets transform takes as input a sequence of blen bits and outputs a sequence of rlen bits. It consists of the following steps:

1. The input sequence b is converted into an integer value z1 through the bits2int transform:

z1 = bits2int(b)

2. z1 is reduced modulo q, yielding z2 (an integer between 0 and q-1, inclusive):

z2 = z1 mod q

Note that since z1 is less than 2^qlen, that modular reduction can be implemented with a simple conditional subtraction: z2 = z1-q if that value is non-negative; otherwise, z2 = z1.

3. z2 is transformed into a sequence of octets (a sequence of rlen bits) by applying int2octets.

2.3.5. Usage

It is worth noting that int2octets is not the reverse of bits2int, even for input sequences of length qlen: int2octets will add some bits on the left, while bits2int will discard some bits on the right. int2octets is the reverse of bits2int only when qlen is a multiple of 8 and bit sequences already have length qlen.

bits2int is used during signature generation and verification in standard DSA and ECDSA to transform a hash value (computed over the input message) into an integer modulo q. That is, the integer obtained through bits2int is further reduced modulo q; since that integer is less than 2^qlen, that reduction can be performed with at most one subtraction.

int2octets is defined under the name "Integer-to-OctetString" in Section 2.3.7 of SEC 1 [SEC1]. It is used in the specification of the encoding of an ECDSA private key (x) within an ASN.1-based structure.

bits2octets is not used in standard DSA or ECDSA. We will use it in the specification of deterministic (EC)DSA.

2.4. Signature Generation

Signature generation uses a cryptographic hash function H and an input message m. The message is first processed by H, yielding the value H(m), which is a sequence of bits of length hlen. Normally, H is chosen such that its output length hlen is roughly equal to qlen, since the overall security of the signature scheme will depend on the smallest of hlen and qlen; however, the relevant standards support all combinations of hlen and qlen.

The following steps are then applied:

1. H(m) is transformed into an integer modulo q using the bits2int transform and an extra modular reduction:

h = bits2int(H(m)) mod q

As was noted in the description of bits2octets, the extra modular reduction is no more than a conditional subtraction.

2. A random value modulo q, dubbed k, is generated. That value shall not be 0; hence, it lies in the [1, q-1] range. Most of the remainder of this document will revolve around the process used to generate k. In plain DSA or ECDSA, k should be selected through a random selection that chooses a value among the q-1 possible values with uniform probability.

3. A value r (modulo q) is computed from k and the key parameters:

• For DSA:

r = g^k mod p mod q

(The exponentiation is performed modulo p, yielding a number between 0 and p-1, which is then further reduced modulo q.)

• For ECDSA: the point kG is computed; its X coordinate (a member of the field over which E is defined) is converted to an integer, which is reduced modulo q, yielding r.

If r turns out to be zero, a new k should be selected and r computed again (this is an utterly improbable occurrence).

4. The value s (modulo q) is computed:

s = (h+x*r)/k mod q
The pair (r, s) is the signature.  How a signature is to be
encoded is not covered by the DSA and ECDSA standards themselves;
a common way is to use a DER-encoded ASN.1 structure (a SEQUENCE
of two INTEGERs, for r and s, in that order).