Description
1 Introduction
Payments are made in bitcoins (BTC’s), which are digital coins issued and transferred by the
Bitcoin network. The data of all these transactions, after being validated with a proof-of-work
system, is collected into what is called the blockchain. You have learned how transactions
are formed in the Bitcoin blockchain and how each block is added, i.e., how a hash-chain is
formed through the proof-of-work (PW) mining process.
In this project, you will implement the Digital Signature Standard (DSS) as a signature
scheme to sign each transaction in the Bitcoin network, and produce a hash-chain of length 3,
i.e., a blockchain with length 3, as shown in Figure 1, with a simplified network structure and
each block only consists of one transaction (so there is no need of Merkle tree authentication
root here). The parameters will have real world security strength, i.e., 112-bit security.
Figure 1: A block chain of length 3, where inputi
, i = 1, 2, 3 is omitted.
The parameters amt0, amt1, and amt2 are three integer numbers with unit BTC, i.e.,
amt0 = 5 (BT Cs), amt1 = 4 (BT Cs), amt2 = 3 (BT Cs).
You use 1 byte to represent one of those integers, i.e. (in hexadecimal) 05, 04, 03, respectively.
In this project, you will act as both a user to send a payment and a miner to validate
the transaction. You will act as the only miner in the system to validate the transaction,
compute the proof-of-work for each transaction (nobody will compete with you to complete
the computation) to link the blocks.
@G. Gong, ECE 458 Computer Security, Spring 2020, Project 1 2
2 Crypto primitives
2.1 Digital Signature Algorithm (DSA)
In the lecture, we call it DSS. In this project, we adopt the specification of NIST FIPS 186-
4. https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf. NIST FIPS 186-4
uses a different sign in the signing equation. Below we list both formats:
h(m) = xr + ks mod q in Lecture Notes
h(m) = −xr + ks mod q in NIST FIPS 186-2 (2001), 186-4 (2013, EC-DSA added)
186-5 (2019 draft, SHA3 added)
The verification is shown below
u = h(m)s
−1 mod q, v = −rs−1 mod q, w = g
uy
v
in Lecture Notes
u = h(m)s
−1 mod q, v = rs−1 mod q, w = g
uy
v
in NIST FIPS 186-*
For doing this project, you are requested to use the NIST format. In this way, you can check
your results with the result computed from using some exiting library.
To work with DSA we first need to generate a set of domain parameters (will be given in
ext subsection) satisfying the three criteria listed in Table 1.
Table 1: Parameter selection criteria
A1. p: a prime number lying between 1024 and 2048 bits
A2. q: a 224-bit prime factor of p − 1
A3. g: an element g ∈ Fp with order q
2.2 A hash function
. The hash function you will use in the project is SHA3-224, for which c code and python code
are provided. You can use any available code or library. Here is an online hash calculator that
you can play around https://www.pelock.com/products/hash-calculator. an example
computation of SHA3-224 is as follow, the input is a hexadecimal string.
1 sha3_224 (” 38363138363536383336 “) =
2 0000000089 cdf55ab2f8463c7438d555f8fd2c91c87ede3235c9bd18
Encoding convention for this project is the same as specified in NIST FIPS 186-4.
@G. Gong, ECE 458 Computer Security, Spring 2020, Project 1 3
1. Bit string concatenation:
(a) mi = pki
||pki+1||amti
, i = 1, 2, 3, in this project, the bit length of mi will always
be 2048+2048+8= 4104. If len(pki) < 2048, we use m1 as an example to explain
how to pad 0 bits as follows. We denote `i = 2048 − len(pki), i = 1, 2.
m1 = 00…0
| {z }
`1
||pk1|| 00…0
| {z }
`2
||pk2||amt1 (1)
where pk1 and pk2 are in their bit stream representations with the order from the
most significant bit to the least significant bit.
(b) The bit length of h(∗)||mi
||noncei will always be 224+4104+128=4456. If len(noncei) <
128, pad 0 bits as follows:
h(∗)||mi
|| 00…0
| {z }
t
||noncei
, t = 128 − len(noncei (2)
2. Input to SHA3-224: a bit string whose length is a multiple of 8.
3. Convert the output of SHA3-224 to an integer in digital signature algorithm:
h(mi) = b0, b1, · · · , b222, b223(a bit string)
↔ b02
223 + b12
222 + · · · + b2222 + b223 (an integer)
2.3 Pseudo-random number generator (PRNG)
PRNG is implemented by SHA3-224 with an input message i for the ith signature and the
224 bits of the output of SHA3-224 is the random number k for ith signature.
3 DSA domain parameters
Each of you will use the same domain parameters p, q, g but has different private keys ski
and public keys pki
. You select your parameters with the file that matches your first two
letters of your last name on LEARN.
1 “””
2 System parameters
3 “””
4
5 ## length of p: 2048 bit
6 p =16158504202402426253991131950366800551482053399193655122805051657629
7 7060402526413293692294259272190069564737424769039787887283726796625612
8 6774959275647858465318737966807007747164023305326786794089976226985553
@G. Gong, ECE 458 Computer Security, Spring 2020, Project 1 4
9 8496229272646267260199331950754561826958115323964167572312112683234368
10 7455831898884993636928081952280556386163355423282412423160031884910769
11 5302897851906422234787872466832362119565128334137884512840126331307093
12 2229612943555693076384094095923209888318983438374236756194589851339672
13 8731943262465539550908053983915501927699944385942431782427666188838032
14 56121122147083299821412091095166213991439958926015606973543
15
16 ## length of q: 224 bit
17 q =13479974306915323548855049186344013292925286365246579443817723220231
18 ## length of g: 2047 bit
19 g =98916631017490605961105256488004423122620476217000087103322908033544
20 1973441523940037409297250576036855503397888372709087879878652786910610
21 2125568674515087767296064898813563305491697474743999164538645162593480
22 3406145834202726976694594399560579577756646531379694852178900779667311
23 4553543597150973233536157598924038645446910353512441488171918287556367
24 8656993578542852492841425689150799337502572709476677921927236216347614
25 5807006574858890795533331544043409550469603768594139262836640434472848
26 0845324408489345349308782555446303365930909965625721154544418491662738
27 796491732039598162639642305389549083822675597763407558360
28
29 ## example of a pair of the private key and the public key for DSA
30 sk_1 =4050777245973485311760368668656517802787805309904944692699511940135
31
32 pk_1 = g ^{ sk_1 } mod { p
}=1602175082181297643947092821250273528422133421443323377108675447423
33 18255511299805366795742263285911192679118307884925841986500361434441100
34 49849021458480928298981254134927677928033548780921767079997422494663801
35 22958704373828713961238634927205688436040181615346434066145640437267510
36 14926808031856592320428795028208256067820208456746195546492229507891358
37 08614480632650318245694448282178469818893229711922449656252675115615920
38 78504705919526372841040647701262413546516077248429016726112320130810521
39 65630976628284374853659058165666337986840722891495356351469207703296283
40 38074406853929851014602301029167732940451529239202171
4 Your tasks
Your tasks are to compute Sigi and PWi for i = 1, 2, as shown in Figure 1 where Sigi serves as
Transaction i (=T xi) and PWi
is the Proof-of-Work (PW) for Transaction i. In this project,
we omit the competing processing in the Bitcoin blockchain (i.e., you are the only miner in the
system). Also each block only contains one transaction. Your tasks are specified as follows.
(a) (2 marks) Check that the system parameters p, q and g satisfy the three criteria in Table
1. You need to provide the factorization of p − 1, and explain your verification process.
Explain why we only pick sk1 as a number less than 224 bits. Compute pki
, i = 1, 2, 3.
@G. Gong, ECE 458 Computer Security, Spring 2020, Project 1 5
(b) (3 marks) Sign and validate transactions by DSA (i.e., DSS, the signing equation defined
in NIST FIPS 186-4): implement a DSA module which enables the user can sign the
transactions and a miner can verify the signed transaction. (Note that since we set all
inputs being zero, so mi = T xi
, i = 1, 2, 3.)
(1) User 1: sign his transaction: Sigsk1
(m1) = (r1, s1), i.e., compute the signature over
m1, k1, r1 = (g
k1 mod p) mod q, k
−1
1 mod q and s1 = k
−1
1
(h(m1) + xr mod q.
(2) A miner: verify Sigsk1
(m1), i.e., compute the values of u, v, w and verify whether
w = r.
(3) User 2: sign his transaction m2 = T x2 using the key pair (sk2, pk2), i.e., executing
the same steps as User 1.
(c) (3 marks) Proof-of-Work (PW): Implement a module for a miner to compute a PW where
SHA3-224 is used as a hash function h in PW1 and PW2 computations.
(1) Find pre-images of h such that
PW1 = h(h(amt0)||m1||nonce1) = 00 · · · 0
| {z }
k
∗ ∗ · · · ∗
| {z }
224−k
PW2 = h(h(m1)||m2||nonce2) = 00 · · · 0
| {z }
k
∗ ∗ · · · ∗
| {z }
224−k
where ∗ means any value and noncei
, i = 1, 2 are any 128-bit numbers. Here you
use k = 32. You should vary a nonce in order to obtain a 32-consecutive leading
zeros of SHA3-224 hash value. Your results on hash values PW1 and PW2 should be
represented as hexadecimal numbers. (You need to establish c/c++ environment if
you wish your computation can done shortly. Otherwise, you may need a few hours
to have it done.)
(2) Determine the average number of trials which you need to get one PW in (1).
(3) (Optional) If you do this reasonably, i.e., you have a proper analysis for that, you will
get one bonus mark. Increase the value of k until you cannot finish the computation.
You may define a bound as the limit of your computation, say the program does not
get a solution within 8-10 hours for computation, and you need to provide progressive
computational complexities, i.e., for k = 32, 33, · · · , T where T is the limit of your
computation with estimated complexity.
(d) (2 marks) Security analysis: Discuss why PW can prevent double spending in the Bitcoin
network and identify two possible attacks on PW.
@G. Gong, ECE 458 Computer Security, Spring 2020, Project 1 6
5 What do you need to submit?
1. Complete the ECE 458 Project 1 Skeleton solution file.py,
name it as yourfirstname-lastname.py.
2. You need to submit a course project report which explains each step of your implementation of DSS in detail, and answers to those questions which are not included in
yourfirstname-lastname.py, specifically,(c)-(2), (c)-(3)(Optional) and (d). For finding pre-image for a fixed hash format, you need to estimate its time complexity (i.e., how
many exhaustive search for varying nonce in order to get such a hash value). Generally
the report should be 4∼7 pages.
3. Submit a single zip file that contains above two files to the Dropbox on Learn. The name
of your zip file should be yourfirstname-lastname.zip. You also need to submit your
report to Crowdmark.
Some Remarks
• If you want to have some practice for big integer computations in order to compute
public-keys and performing DSA, you may use the BigInteger class1
in java.math package
to do all the big integer operations involving in DSA. For simple computation, you may
simply call any crypto library.
• For computing SHA3-224, you may use the c code and python code provided to you
including test vectors or you can use any package as you wish. If you use Python/Java
packages, you have to be careful regarding the encoding format, since the encoding
specified in this project is bit string (provided code takes bit string as inputs), while
hash function packages usually take character strings as input, then you should encode
the input to utf-8 format before hash it. If you want find out the nonce in an efficient
manner, it is recommend to use the c code. Otherwise, you may take few hours in
Python/Java.
• Note that SHA3-224 has an input 1152-bit string for each absorbing process. But the
code provided you or any other crypto library will automatically do the padding.
6 What to do next?
You may work along or team with one person. Even you are in a group of two, you still need
to submit a separate report, which will be marked individually (it should be in the standard
way that two reports are not similar).
1
see http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigInteger.html
@G. Gong, ECE 458 Computer Security, Spring 2020, Project 1 7
7 Due Date
The report is due at
June 26, 11:59am ET, 2020.
You need to submit i) Project Report, ii) Code, and upload them to the Crowdmark.
Notes.
(1) Note that you earn 10 marks based on how well you answer the questions and the correctness of the computation, and how good of your solutions in terms of complexity for
solving that.
(2) If there are any questions or something is confusing, please ask me. I reserve the right to
provide updates and clarifications as needed.