ECDSA

Lesson 2 covered the mathematical equations used in ECDSA and there is no need for learners to remember these equations.

Consider an elliptic curve E with the above properties, and we have two parties, Alice and Bob, wherein Alice wants to sign a message 'mm' and send it to Bob.

With no surprise, the protocol Alice and Bob agree to use is ECDSA.

Step 1 - Generating Private/Public Key Pair

Alice generates private and public key pairs.

  1. For this, Alice chooses a random integer dd where 0<d<q0 < d < q (q is the order of the group)(q \ is \ the \ order \ of \ the \ group). The randomly chosen integer becomes the private key for Alice.

  2. Alice computes dGd * G, and this value is the public key for Alice, denoted as AA. Alice shares this public key with Bob. (Recall this computation is done using scalar multiplication, and it is a point on an elliptic curve, so it has an xx and yy co-ordinate)

The keys are now

Kpub=A=dGK _{pub} = A = d * G Kpr=dK _{pr} = d

Notice that Bob knows the domain parameters (p,a,b,q,G)(p, a, b, q, G), and the public key (AA) is shared with Bob.

Step 2 - Signing

Alice uses a private key to compute the signature for the message 'mm':

1. Alice chooses a random ephemeral key KEPHK_{EPH} such that 0<KEPH<q0 < K_{EPH} < q (notice this is like choosing a private key in step 1)

2. Alice computes R=KEPHGR = K_{EPH} * G (notice this is like computing public key in step 1)

3. Let r=xR mod qr = x _R \ mod \ q, i.e., the xx-coordinate of point RR on the elliptic curve

a. If r=0r = 0, then they need to return to step 1 and start again. (This is because if r=0r = 0, the value of 'ss' calculated in step 5 will be independent of private key 'dd', which would imply signing without using the private key. It will defeat the purpose of digital signatures).

4. Compute the hash of message 'mm' by using the hash function 'hh,' i.e., h(m)h(m). There are two reasons for performing the hash of the message. The first reason is to manage the arbitrary length of the message and make its length at least as long as qq. Secondly, it makes the signing more secure by preventing a specific attack.

5. Compute s(h(m)+dr)KEPH1 mod qs ≡ ( h(m) + d * r ) {K_{EPH} }^{-1} \ mod \ q

The signature consists of a pair of integers (r,sr, s)

Note: The value for rr and ss needs to be between 1 and qq. i.e.

1r<q1≤ r < q 1s<q1 ≤ s < q rr and ss require to be in the range of (1,,q1)(1,…,q-1), which is the reason for applying mod qmod \ q in steps 3 and 5.

Step 3 - Verification

For verification, Bob has values (m,(r,s))(m, (r, s) ), i.e., the message mm and the signature (r,s)(r, s ) computed during signing. Bob needs to perform three additional calculations (Step 1-3) before he can verify the signature (Step 4,5)

1. Calculate value us1 mod qu ≡ s^{-1} \ mod \ q

2. Using uu, calculate v1uh(m) mod qv_1 ≡ u * h(m) \ mod \ q

3. Using uu again, calculate v2ur mod qv_2 ≡ u * r \ mod \ q

4. Compute P=v1G+v2AP = v_1 * G + v_2 * A (GG is the generator, and AA is the public key for Alice). Again, as this is a point on the curve, it has an xx and yy co-ordinate, i.e., P=(xP,yP)P = (x_P, y_P)

5. The verification, denoted as verKpubverK _{pub} for (m,(r,s))(m, (r, s) ), is as follows:

a. if xPr mod qx_P ≡ r \ mod \ q, it implies the signature is valid

b. if xP≢ r mod qx_P ≢ \ r \ mod \ q, it indicates the signature is invalid

Last updated

Was this helpful?