Go up to the CCC HW page (md) | view tabbed version
In this homework you will implement the ECDSA algorithm.
The sizes of the numbers we are using will be small – all 1,000 (base 10) or less. While we are not particularly interested in efficiency, your program does have to run in a reasonable amount of time (say, a second or less). In particular, your elliptic curve multiplication must be a logarithmic time algorithm (relative to k), not a linear time algorithm.
In this homework, it is critical to carefully test each stage of the assignment. Each part requires that the previous part works properly – and, if it does not, then it will be exceedingly difficult to debug your program. If you get stuck, the best way to figure out where the bug is is to print out the values at each step, and verify them by hand or via online calculators (linked to below). A full work-up of a sample calculation is provided later in this document.
You will need to be familiar with the Encryption slide set, specifically the three sections that deal with the content in this assignment: elliptic curves, finite fields, and ECDSA. What this assignment is asking for will make no sense if you are not familiar with that material.
Any changes to this page will be put here for easy reference. Typo fixes and minor clarifications are not listed here. So far there aren’t any significant changes to report.
The recommended language to write this in is Python. If you want to use a different language, please speak to me first. The intent is for you to write all this code yourself – you can NOT use any libraries that do field arithmetic, elliptic curve arithmetic, etc. This includes any hashing functions (such as hashlib in Python); note that you never have to take a hash in this assignment. We expect you to only need the most common standard libraries as a result.
We realize that the default random number generators in most (all?) programming languages are not cryptographically secure random number generators, but that’s fine for this assignment.
We are going to call your program by calling an ecdsa.sh shell script. Any parameters passed to the shell script will be passed as-is to your program. This is what your ecdsa.sh script should look like if you are using Python:
#!/bin/bash
python3 ecdsa.py $@If you are using Java, it would look like this:
#!/bin/bash
java ECDSA $@Be sure to call python3, not python in your shell script! Otherwise it will not work.
Of course, you should change the second line to match the file/class names that you choose.
You will also have to submit a Makefile that will be used to compile your program, if needed. For languages that do not need compilation (such as Python), just put in a single echo statement so that make still runs properly. This is the same as in the last assignment (md).
The first step is to ensure that you have all the finite field arithmetic functions that are necessary. Some of these are easy – addition and multiplication, for example. Others are a bit more challenging, such as division. You will likely want to reference the finite field section of the lecture slides. In addition to the four standard arithmetic operations, you will likely also need exponentiation, obtaining the additive inverse, and obtaining the multiplicative inverse. Some functions will likely use others – division of a by x is just multiplying a by the multiplicative inverse of x, for example.
For ease of the development of later steps, the field size should be a parameter to the functions.
Test these well to ensure that they work! You can test your operations by using the arithmetic identities: if x is the multiplicative inverse of y, then x * y = 1, for example.
There are three elliptic curve point operations that will be needed:
Some references from the lecture slides:
You can test your functions by using two websites: one that does elliptic curve addition in a field and one that does elliptic curve multiplication in a field. The curve we are using is secp256k1, which sets a = 0 and b = 7. For testing purposes, we recommend setting the prime modulus p to 43; this will give an curve order (o) value of 31. Other valid field sizes (aka p values) are listed in the “Testing” section of this assignment.
There are some corner cases to test as well. Given P = (x,y), it’s reflection is P′ = (x,−y). Within the field Zp, that reflection is P′ = (x,p−y). Adding a point and its reflection together gets O (or 0), the point at infinity, which is also the identity element. Your code should be able to compute P ⊕ P′ = O, for however you represent O. It should also be able to compute O + P = P. You can see that here in the slides.
One the previous two steps are completed (and tested!), you can proceed to generate the signature and then validate it; this is discussed in the ECDSA section of the encryption slide set.
We recommend reading through the next section of this assignment, on input and output, before starting to work on this section.
Your program will need to be able to perform three primary functions, listed below. We will only be using the secp256k1 curve, so you can always assume that a = 0 and b = 7.
Your program will take in a number of command line parameters. You can always assume that the number and format of command line parameters will be correct, as specified below – you do not need to error check the parameters (neither the number nor the format). You may also assume that any points provided (such as G or Q) will always lie on the curve. Your program will only use the secp256k1 curve for all execution runs, so you can globally set a = 0 and b = 7; these two values will not be passed to the program.
Each execution run of the program will take in a string as the first command-line parameter; this is the so-called mode. After the mode will be a series of command-line parameters, all of which will be integers. Other than the userid mode, the first four integer parameters will always be, in this order: the prime modulus p, the curve order o, and the x and y coordinates for the base point G. All numerical values provided will be non-negative integers not greater than 1,000. All numbers provided as input parameters, or output by the program, are base-10 numbers. And both p and o will always be prime numbers when we test your code.
The four required modes of the program are:
userid will just print your userid. All lower-case, no quotes, and no extra spaces. There will not be any other command-line parameters. Below is an execution run. Needless to say, it should print out your userid, not ‘mst3k’.
$ ./ecdsa.sh userid
mst3k
$genkey will generate a (random) primary key d such that 1 ≤ d ≤ o − 1, and use that to compute the public key, point Q. The numerical command-line parameters are just the four described above (p, o, Gx, Gy). The output should be three integers, one on each line: d, Qx, and Qy. You can verify here that the values returned are correct (specifically that Q = d ⊗ G). Below is a sample execution run, which uses p = 43, o = 31, and G = (25,25). Since this output is based on a random number that is generated (specifically, d), one would expect that your output would be different on each execution run. The result of the execution run shown below is that the private key is d = 16 and the public key is Q = (37,36). A full work-up of this computation is in the next section.
$ ./ecdsa.sh genkey 43 31 25 25
16
37
36
$sign will sign a message. In addition to the four standard numerical parameters (p, o, Gx, and Gy), there will be two more provided: d and h. The first these, d is the private key, and was part of the output from the genkey mode, above. The second one, h, is meant to represent the hash of the message that is being signed – it will be an integer in the range 1 ≤ h ≤ o − 1. To simplify this assignment, we are not providing the message m that you are to take the hash of – we are just providing the hash value itself as a base-10 integer. Note that Q is not needed for signing, and is thus not provided. To be clear, the six numerical parameters are, in order: (p, o, Gx, Gy, d, h). The output should be two integers, one on each line: the r and s values of the signature. Note that the randomly generated – and secret – value k is not part of the output, as would be expected with a typical ECDSA implementation. And if r or s are zero, your program should re-generate k and try again – there should be no difference in the output. Below is a sample execution run, which uses p = 43, o = 31, G = (25,25), d = 16, and h = 30 (the public key, Q = (37,36), is not part of the parameter list). Since this output is based on a random number that is generated (specifically, k), one would expect that your output would be different on each execution run. The result of the execution run below is that the signature is (r,s) = (12,24). A full work-up of this computation is in the next section.
$ ./ecdsa.sh sign 43 31 25 25 16 30
12
24
$verify will verify a message. In addition to the four standard numerical parameters (p, o, Gx, and Gy), there will be five more parameters provided. The next two are the public key: Qx and Qy (the verifier does not know the private key!). Following that are the two parts of the signature, r and s. Lastly will be the (computed) hash of the message that is being verified. To be clear, the nine numerical parameters are, in order: (p, o, Gx, Gy, Qx, Qy, r, s, h). The output should just be ‘True’ if the signature matches, and ‘False’ if it does not – case matters here! Below are two sample execution runs, which set p = 43, o = 31, G = (25,25), Q = (37,36), (r,s) = (12,24), and (h = 30 or h = 29). This output is not based on a random number, so your program should have the same output for these two execution runs. A full work-up of this computation is in the next section.
$ ./ecdsa.sh verify 43 31 25 25 37 36 12 24 30
True
$ ./ecdsa.sh verify 43 31 25 25 37 36 12 24 29
False
$Note: please do not print out any other output for those modes, else your program will be marked incorrect by the auto-grader! You are welcome to add additional modes that you use for debugging, or that perform those functions with verbose output. But the four required modes – userid, genkey, sign, and verify – must only produce the output shown above.
Your code may occasionally incorrectly verify a invalid signature! The computation of s is computed mod o, which – in this example – is only 31. This means about 1 in 31 random but invalid signatures would be expected to verify as true. (In reality, with secp256k1, o ≈ 1.16 * 1077, the chance of an invalid signature returning true is quite small). If you do get an invalid signature (or two or three) to return true, just try some other values.
To help you understand the previous example, below is the complete formulaic work-up of the values that were computed above in the three execution runs. All elliptic point computations can be verified here for addition and here for multiplication; verification links are them are also provided below. Note that some of the values used (specifically d and k) are randomly generated, so we would expect them to be different in your execution runs.
To ensure clarity about the operations, the + symbol is only used for scalar addition (meaning between two numbers) and the * symbol is only used for scalar multiplication (meaning between two numbers). Addition of two elliptic points uses the ⊕ symbol, and multiplication of an elliptic point by a scalar uses the ⊗ symbol.
We know that the prime modulus p = 43, the order o = 31, and the base point G = (25,25), as these were given in the first four numeric command-line parameters. These are consistent for all the execution runs.
Elliptic point addition: There are formulas presented in the slides to add two points, both on secp256k1, within a field. Given two points P1 = (x1,y1) and P2 = (x2,y2), the sum of those two points is: x3 = m2 − x1 − x2 and y3 = m(x1−x3) − y1. In Z43 we’ll pick two arbitrary points to add: (29,31) and (37,36). Formally, we want to compute P3 = P1 ⊕ P2 = (29,31) ⊕ (37,36). As we are not counting points on a curve, but instead just using curve formulas, this is all mod’ed by 43 (NOT o = 31).
First we determine the slope. The formula is m = (y2−y1)/(x2−x1) = (36−31)/(37−29) = 5/8. The division 5 ÷ 8 in Z43 is 6 (confirmation: 6 * 8 mod 43 = 5). Thus, we know the slope: m = 6. To determine the points, we use the formulas presented in the slides: x3 = m2 − x1 − x2 = 62 − 29 − 37 = 13 and y3 = m(x1−x3) − y1 = 6 * (29−13) − 31 = 22, both in Z43. (I’ve removed all the “mod p” parts for clarity.) Thus, (29,31) ⊕ (37,36) = (13,22), and this computation can be verified here.
Elliptic point multiplication: There is an example in the next section (“Testing”) that shows elliptic point multiplication, and shows how to avoid cases that will generate the point at infinity as the answer.
Key generation: The random value for the private key is d = 16. Computing d ⊗ G = 16 ⊗ (25,25) = (37,36) (verification).
Signing: The secret k value, which was not shown, was k = 17. We compute R = k ⊗ G = 17 ⊗ (25,25) = (12,12) (verification). The x-value of this, 12, is the first part of the signature, and is referred to as lower-case r. We next have to compute k−1. Because k is counting the number of points, the inverse is computed in Z31, NOT in Z43. Thus, in Z31, 17−1 = 11 (verification; also that 11 * 17 mod 31 = 1). We know via the command-line parameters that h = 30 and d = 16, and we have just computed r = 12. We can then compute s, which also is computed in Z31, NOT Z43: s = k−1(h+r∗d) mod o = 11 * (30+12*16) mod 31 = 24. Thus, the signature is (r,s) = (12,24).
Verification: We are given the values for Q = (37,36) and the signature (r,s) = (12,24). We are given two different hash values, each on its own execution run: the correct hash value of h = 30 and an incorrect hash value of h = 29. As s was computed in Z31 (NOT Z43), we also compute it’s inverse in Z31: s−1 = 24−1 = 22 in Z31; (verification; also that 22 * 24 mod 31 = 1).
To verify the correct signature (where h = 30), we need to compute R = s−1 * h ⊗ G ⊕ s−1 * r ⊗ Q = 660 ⊗ G ⊕ 264 ⊗ Q (this is an equivalent form of the formula used to sign the signature, as shown in the slides starting here). We can mod those two scalars (660 and 264), but that mod is also in Z31, and yields R = 9 ⊗ G ⊕ 16 ⊗ Q = 9 ⊗ (25,25) ⊕ 16 ⊗ (37,36) = (2,31) ⊕ (29,31) = (12,12); (verifications 1, 2, and 3). Because the x-value of this computed point (i.e., 12) equals the provided r value in the signature, the signature is valid.
The second execution run had the incorrect hash (h = 29). The process is the same as the above – we compute R = s−1 * h ⊗ G ⊕ s−1 * r ⊗ Q. As h is different the coefficient in front of G changes: R = 638 ⊗ G ⊕ 264 ⊗ Q = 18 ⊗ G ⊕ 16 ⊗ Q = (7,36) ⊕ (29,31) = (21,18); (verifications 1, 2, and 3). As the x-value of that computed R, specifically the value 21, does not equal the r = 12 provided with the signature, the signature is not valid.
One type of test that we are going to perform is whether your program can verify a signature that your code signs; another is whether it can indicate as invalid a signature that you did not sign. We will be trying different prime field sizes; all of the ones listed below also have a prime order size. Here are a few examples you can use.
You are certainly welcome to come up with your own examples to test it with as well – just make sure BOTH p and o are prime.
Note that if you enter the curve of a = 0 and b = 7 into this site, and enter a different p value, it will tell you the order below the boxes (“The curve has … points”). You can pick any valid point on that curve as G; we just arbitrarily picked one for the examples above.
Let’s imagine that you wanted to compute 1000 ⊗ (12,31) in Z43. We can see that the answer is (20,3) (verification). But to compute it ourselves, first you we compute the powers of 2 that add to 1,000: 1000 = 512 + 256 + 128 + 64 + 32 + 8.
Next, we determine (12,31) times the various powers of two by repeatedly adding it to itself:
Note that a lot of the points repeat because it’s a small field (p = 43) with a small order (o = 31), and the order size is one less than a power of 2.
Next we add up the necessary values. Recall that elliptic curve addition is commutative (you can add the points in any order and get the same result). Let’s assume we add them left-to-right
This mataches what the EC multiplication website states as the answer.
You have to submit three files:
ecdsa.sh, the shell script that will be called to run your program. See above for the format.make, which will be called on submission. For languages that do not need compilation (such as Python), just put in a single echo statement so that make still runs properly.ecdsa.py or ECDSA.java