[SOLVED] CS scheme database algorithm COMP6451 T1 2021 Assignment 1 (version 2) Total Marks: 30

COMP6451 T1 2021 Assignment 1 (version 2) Total Marks: 30
(Each question is worth 5 marks) Due: 23:59 Tuesday March 9, 2021
c R. van der Meyden, UNSW
(All rights reserved distribution to 3rd parties and/or placement on non-UNSW websites prohibited.)
Submissions: Submit your solutions as a pdf or text file via the course moodle page. Your submission must be your individual work UNSW rules concerning this will apply (see the Course Outline). Turnitin will be used to perform similarity checks. In general, these are short answer questions aim to keep your answers brief but precise. Answer all parts, and show your working.
Question 1 (Money, debt, and a reason some people worry about fiat money and prefer Bitcoin):
In Australia, the Reserve Bank of Australia (RBA) is responsible for creating fiat money, in a number of forms that include coins and (plastic) notes. Similar organisations play this role in money other countries, e.g., the Federal Reserve in the USA. However, private banks (e.g., in Australia, the Commonwealth Bank, ANZ, Westpac and NAB) also play a role in the creation of fiat money. This works as follows.
For the purposes of the exercise, we assume that there are just two private banks, creatively called bank A and bank B. Suppose an initial state where just one rich person (Uncle Scrooge) has all the money (coins and notes) that has been issued by the RBA: $1 billion. There are other rich
1

people, of course, but they are holding their wealth in forms other than money: gold mines, development sites, buildings, houses, etc. The two banks have also just opened for business, so they dont have any money yet, but as we will see, they are in a nice profitable line of business. Everyone else has to survive by working for a rich person, or by borrowing from a bank.
Luckily, bank A soon has plenty of money to lend: Scrooge has everything he needs already, and is afraid of robbers, so he deposits his money in bank A. The bank credits Scrooges account for $1B, and everyone else has $0 in their account at their chosen bank. From from the banks perspective, the $1B coins and notes now in its vaults is an asset, but it is balanced by a liability: in effect, the bank owes Scrooge this money, and he can request a withdrawal of his money any time he likes. Using the equation
Equity (net worth) = Assets Liabilities
we see that bank As equity is $1B $1B = 0. The bank didnt get rich all of a sudden because of Scrooges deposit!
In practice, rich people prefer to collect interest on their deposits, and dont spend much, so they tend to leave their money in the bank, and with- draw only small amounts. The bank exploits this fact to start making profits by lending some of the deposits out, and collecting interest as a result as the money is paid back. (Some of that covers interest due to be paid to Scrooge, but the bank charges borrowers a higher interest rate than they pay to Scrooge, so they make a nice profit along the way.)
The RBA regulates banks based on this behaviour. It would be a disaster if the bank had lent out all of Scrooges money and then Scrooge came to make a withdrawal because he wants to buy a maxi-yacht. The bank wouldnt have the cash, and go out of business from this default on its obligations. So the RBA requires that banks hold enough cash in reserve in their vaults so that they can pay out the expected amount of withdrawal requests. Suppose that this reseverve ratio is r (0, 1): if a bank has $X cash it is permitted to lend out up to $(1r)X, but must keep at least $rX in its vaults to cover potential withdrawals.
Lets say that bank A lends out the $(1 r) 1B to Alice for her gold mining project, and Alice uses it to buy a gold mine and equipment from Bob, who deposits this money in bank B. How much money is there now in the economy? One way to answer this is to ask how much money people have in their bank accounts. Well, Scrooge has $1B in his account at bank A,
2

and Bob has (1r)$1B in his at bank B, so there is now (1+(1r))$1B total in peoples bank accounts. (Of course, some of them have to pay it back over time, but for the moment, this is money that could potentially be spent on goods and services.) The total amount of notes and coins in the economy is still the same. Bank A has $r 1B worth, and $(1 r) 1B has just been transferred to bank B, for a total of $1B.
(a) Of course, the story does not end here. Bank B would like to make some money by collecting interest from loans as well, so it lends out some of the cash it now has in its vaults to Carol for her project to build student apartment towers. If it follows the RBAs rules about keeping money in reserve, what is the maximum it can lend to Carol?
(b) Carol takes her maximum size loan and uses the money to buy a de- velopment site from Arthur, who deposits the money in bank A. What is the total amount of deposits now in the banking system?
(c) After receiving Arthurs deposit, how much money is bank A able to issue in new loans? (Dont count the loan already made to Alice!)
(d) Suppose this story is continued ad infinitum, with a bank making max- imum size loans at each step, and the money lent being deposited in the other bank. How much money in total is in peoples accounts in the limit? Express this as simply as you can, and explain your answer. (Hint: there is an equation somewhere in the slides for weeks 1-2 that helps with this question.)
(e) Suppose this story has been proceeding for a few years. What would happen if there was suddenly a pandemic, and Scrooge and the other rich people who had sold their gold mines and development sites and houses etc., started to worry that there would be mass unemployment and many of the people who had borrowed money would not be able to repay their loans? What might this have to do with the following diagram from the RBA?
3

Question 2: (Public Key Encryption) Both RSA and Elliptic Curve encryption require us to compute exponentials in some group G. Let be the operation in this group, and write 1 for the unit of the group. For m an element of the group, and e a natural number, the most obvious way to computeme =mmm(ecopiesofm)isthefollowing:
r = 1;
for i = 1..e do r := r*m
return r
(a) When e is a number of 2048 bits, as is typical with RSA keys, what is the maximum number of group operations () required by this algo- rithm?
A more efficient way to compute me is the following
1. Write e in binary, as bk, . . . , b0, where b0 is the least significant bit. 2. Let p be an array of group elements of length k + 1;
4

3. p[0]:=m;
4. fori=0..k1dop[i+1]:=p[i]p[i]; 5. r:=1;
6. fori=0..kdo{ifbi thenr:=rp[i]}
7. return r
Explain how this algorithm works as follows:
(b) Give the loop invariant for the loop in step 4, in the form of a general statement about p[0]p[i] that holds while the loop is running. Explain why the body of the loop maintains this invariant.
(c) Give the loop invariant for the loop in step 6, in the form of a general statement about p, r, i and the bj that holds while the loop is running. Explain why the body of the loop maintains this invariant.
(d) Use the answer to (c) to show that the algorithm returns the correct answer me.
(e) What is the maximum number of group operations performed by this algorithm when e is a number of 2048 bits?
Question 3 (Hash Functions): Suppose that we have a list of files f1, f2, . . . , fn that have been timestamped using the Haber and Stornetta scheme discussed
in lectures. That is, for a cryptographic hash function h, and a value v0 from the previous period, we compute a sequence of values
w1 = h(f1) w2 = h(f2) .
wn = h(fn)
v1 = h(v0||w1) v2 = h(v1||w2)
vn = h(vn1||wn)
Assume that only the values v0 and vn have been published in the paper, on days d0,d1, respectively. The number of files included in any period may be arbitrary, it is not required to be equal to n. To prove existence of a file fi in the interval [d0,dn], we can present the following information: the file fi, the index i, and the sequence of hash values w1, . . . , wn.
5

(a) (2 marks) What computation should a verifier of the claim that the file existed in the interval perform? Assume that the verifier is able to look up the values v0 and vn in the newspaper.
(b) (3 marks) Suppose that Mallory has a file f that is not in the set {f1, . . . , fn}. In an attempt to cheat, and fraudulently convince the verifier that file f existed in period [d0,d1], Mallory needs to present data of the form f,i,w1,,wm for some m, which passes the test from part (a). Prove that it is difficult for Mallory to do this. Explain carefully what properties of the hash function you rely upon for the proof.
Question 4: (Signatures and Digital Notes) Alice has an account at Bobs bank. Alice would like to withdraw $10 from her account to use for her internet shopping. Alice would like to get Bob to sign a message m that says, intuitively, Bob will pay $10 to the first person to present this message. Of course, if Bob issues many such messages, then there is no way to tell them apart, and people might start presenting such messages to the bank multiple times, losing the bank a lot of money. To fix this, we can include a serial number N in the message, so that it says
This is note number N. Bob will pay $10 to the first person to present this message.
Let m(N) be the above message. The idea is that before Bob signs this message, and gives it to Alice, he will record N in his database of notes issued. If someone presents the message to Bob, he pays the $10, but updates the database to record that this note has already been presented, and is no longer valid.
This, however, presents a risk to Alices privacy. If she spends the note on goods being sold by Victor, the vendor of Very naughty products, and Victor then presents the note to the bank, then Bob will learn that Alice has shopped with Victor. (Victor, if he is wise, will rush the note to the bank, to make sure that Alice has not sent a copy to someone else already, and will not ship the goods to Alice before he has been paid by the bank.)
To get around this risk to her privacy, Alice invents a way to obtain a note signed by the bank, that contains a random serial number created by Alice, without Bob learning what the serial number is. (As above, Bob, will
6

keep a record of which serial numbers he has paid out, to prevent people
claiming payment twice on the same note.) Let KB = (e, n) be Bobs RSA
signature verification key, known to Alice, and let K1 = (d,n) be Bobs B
private signature key, known only to Bob. Bob signs a message m using the function SK1 (m) = (m, md mod n).
B
Suppose that messages are represented as a number mod n, where n is
the modulus in Bobs signature verification key. Alice generates a random
number r mod n, and a random serial number N, and asks Bob to sign the
message mr = re m(N) mod n. Note that Bob cannot tell what m(N)
is, since it has been mixed up with some random noise re. Bob signs this
message mr, and returns the result SK1 (mr) = (mr, (mr)d mod n) to Alice. B
(a) Show that Alice is now able to efficiently compute SK1(m(N)), even B
though she does not have Bobs signature key K1. This means that B
Alice then has the signed message that she wanted, without Bob learn- ing the number N that allows him to trace the note back to Alice. (It may be necessary to add some constraints to the definitions above. If so, say what these are.)
(b) Bob starts to get worried, and has second thoughts. He does not know what he is signing. For all he knows, Alice could be sending him the message Bob promises to pay Alice $1,000,000 to sign using the above technique. To protect himself from being cheated like this by Alice, he decides to audit Alice to keep her honest. Rather than signing every message sent to him by Alice, he requires Alice to send him multiple versions
r1em(N1) modn r2em(N2) modn
.
rkem(Nk) modn
where the ri are different random numbers, and the Ni are different
random serial numbers. Let the messages sent by Alice to Bob be
x1, . . . , xk. To make sure that Alice is not maliciously sending him
bad messages, Bob randomly selects just one of these messages xi for
signing. His idea is that he will force Alice to send him the values rj
for all j = i, so that he can compute the values re xj mod n, and j
check that it is equal to a message of the right form m(N). (Note that if xj = rje m(Nj) mod n, then re xj mod n = re rje m(Nj)
7
jj

mod n = m(Nj).) If one of these checks fails, he will refuse to sign, otherwise he will sign xi.
Assume that Alice behaves as follows:
First she flips a fair (1/2H+1/2T) coin to decide whether to cheat.
If she does not cheat, she sends Bob completely correct messages.
If she cheats, she uniformly at random picks i from {1,,k}, and sends Bob x1,xj where xj = rje m(Nj) mod n if j = i and xi = rie Bob will pay Alice $1M mod n.
When Bob requests the rj values, she sends him the correct rj values that she used to construct the xj.
In this case, what is the probability that Bob will catch Alice cheating, given that she cheats? Conversely, assuming that Bob knows this is how Alice behaves, if Alice passes Bobs audit, what probability should Bob assign to the proposition Alice has not cheated?
(c) Show that, in fact, there is a way for Alice to cheat, and always escape undetected, even when Bob audits her as in (b), because Alice is able to send Bob incorrect values rj, without Bob ever detecting that Alice has cheated.
(d) Extend the protocol by adding some additional information that Alice sends to Bob before Bobs audit, that enables Bob to make sure that Alice does not cheat when responding with the values rj that Bob requests. Explain why your solution prevents Alice from cheating with the rj.
(e) Your solution to (d) should also ensure that Bob cannot deduce Ni for the message xj = rie m(Ni) that he signs. Explain why this is the case.
Question 5 (Bitcoin Protocol: Suppose that all of Australias internet connections to the rest of the world break down, disconnecting Australia from the rest of the world for a period of one year. (For example, a major earthquake damages all the sea cables, and at the same time, a period of sun
8

storms destroys all communications satellites and blocks all radio communi- cations.) In no more than one page total, answer the following:
(a) (2 marks) What would be the effect on the Bitcoin ecosystem (i.e., users, miners, and exchanges) both inside and outside of Australia dur- ing the disconnection period?
(b) (2 marks) What would happen when Australia becomes reconnected to the rest of the world? In particular, what would be the negative impacts?
(c) (1 mark) What could be done to protect against the negative impacts from part (b)?
Question 6: Bitcoin Transactions: You are about to go on a holiday in the Sahara. It is so hot there that if you take your mobile phone or laptop, they will get cooked, and break down. There might also be some nasty robbers who could steal your belongings. So you also dont want to carry around your Bitcoin private keys written on pieces of paper. Youd like to be able to spend your Bitcoin on your trip, however, by using internet cafes at the local oases. So you wonder if you can set up a Bitcoin transaction whose output you can spend by means of a password mechanism, rather than a private key. (Youd much prefer to use that than a Bitcoin private key, since it is easier for you to remember!) For purposes of this exercise, we will counterfactually pretend that your zID counts as a good password. Suppose that you have been very careful to keep your zID secret from the world, and any UNSW staff who do know your zID are completely trustworthy, and would never do anything malicious. Well also pretend that the zID is long enough and random enough that a brute force guessing attack will take longer than your lifetime. (So answers to the questions below based on brute force attacks or UNSW insider attacks dont count as correct answers.)
(a) First, say what your UNSW zId is. Now write a Bitcoin unlocking script that allows an output to be spent by providing the numerical part of your zID (i.e., the part without the z). The script should check that the unlocking script of the input of the transaction that spends the output is equal to the numerical part of your zID (presented as a sequence of digits rather than as one single number).
9

(b) Would it then be safe for you to make your Bitcoin available for you to spend on holiday by creating a valid transaction that has as input some of your Bitcoin, and a single output with the unlocking script of part (a)? If so, explain why. If not, what could go wrong? Who would be able to spend your Bitcoin, how and when?
(c) You decide to add some extra protection. Rather than the unlocking script just checking that the input contains your zID, it should check that whatever is provided in the unlocking script has a SHA256 hash that is equal to the SHA256 hash of the numerical part of your zID. First, tell us what the SHA256 hash of the string consisting of the numerical part of your zID is. (You may find the Unix function shasum useful here.)
(d) Now give the unlocking script for the hash-based password unlocking script using your answer in part (c).
(e) Would it be safe for you to make your Bitcoin available for you to spend on holiday, using a transaction with the unlocking script of part (d)? If so, explain why. If not, what could go wrong? Who would be able to spend your Bitcoin, how and when?
10