xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

扫码添加客服微信

扫描添加客服微信

程序代写案例-COMP6451 T1-Assignment 1

时间：2021-03-03

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 don’t 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 Scrooge’s account for $1B, and everyone else has $0 in

their account at their chosen bank. From from the bank’s 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 A’s equity is $1B - $1B = 0. The bank didn’t get rich all

of a sudden because of Scrooge’s deposit!

In practice, rich people prefer to collect interest on their deposits, and

don’t 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 Scrooge’s money and then Scrooge came to

make a withdrawal because he wants to buy a maxi-yacht. The bank wouldn’t

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 $(1− r) ·X, but must keep at least $r ·X in its vaults to

cover potential withdrawals.

Let’s 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 (1− r) · $1B in his at bank B, so there is now (1 + (1− r)) · $1B

total in people’s 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 RBA’s 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 Arthur’s deposit, how much money is bank A able to

issue in new loans? (Don’t 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 people’s 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

compute me = m ∗m ∗ ... ∗m (e copies of m) is the following:

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. for i = 0..k − 1 do p[i + 1] := p[i] ∗ p[i];

5. r := 1 ;

6. for i = 0..k do { if bi then r := r ∗ p[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) v1 = h(v0||w1)

w2 = h(f2) v2 = h(v1||w2)

...

wn = h(fn) vn = h(vn−1||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, w′1, . . . , w

′

m 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

Bob’s 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 Alice’s 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 Bob’s RSA

signature verification key, known to Alice, and let K−1B = (d, n) be Bob’s

private signature key, known only to Bob. Bob signs a message m using the

function SK−1B

(m) = (m,md mod n).

Suppose that messages are represented as a number mod n, where n is

the modulus in Bob’s 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 = r

e × 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 SK−1B

(mr) = (mr, (mr)

d mod n) to Alice.

(a) Show that Alice is now able to efficiently compute SK−1B

(m(N)), even

though she does not have Bob’s signature key K−1B . This means that

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

re1 ×m(N1) mod n

re2 ×m(N2) mod n

...

rek ×m(Nk) mod n

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 6= i, so that he can compute the values r−ej × xj mod n, and

check that it is equal to a message of the right form m(N). (Note that

if xj = r

e

j ×m(Nj) mod n, then r−ej × xj mod n = r−ej × rej ×m(Nj)

7

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 = r

e

j ×m(Nj) mod n if j 6= i

and xi = r

e

i × “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 Bob’s 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 Bob’s 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 = r

e

i × m(Ni) that he signs. Explain why this is the

case.

Question 5 (Bitcoin Protocol: Suppose that all of Australia’s 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 don’t want to carry

around your Bitcoin private keys written on pieces of paper. You’d 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. (You’d 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. We’ll 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 don’t 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

学霸联盟

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 don’t 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 Scrooge’s account for $1B, and everyone else has $0 in

their account at their chosen bank. From from the bank’s 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 A’s equity is $1B - $1B = 0. The bank didn’t get rich all

of a sudden because of Scrooge’s deposit!

In practice, rich people prefer to collect interest on their deposits, and

don’t 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 Scrooge’s money and then Scrooge came to

make a withdrawal because he wants to buy a maxi-yacht. The bank wouldn’t

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 $(1− r) ·X, but must keep at least $r ·X in its vaults to

cover potential withdrawals.

Let’s 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 (1− r) · $1B in his at bank B, so there is now (1 + (1− r)) · $1B

total in people’s 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 RBA’s 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 Arthur’s deposit, how much money is bank A able to

issue in new loans? (Don’t 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 people’s 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

compute me = m ∗m ∗ ... ∗m (e copies of m) is the following:

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. for i = 0..k − 1 do p[i + 1] := p[i] ∗ p[i];

5. r := 1 ;

6. for i = 0..k do { if bi then r := r ∗ p[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) v1 = h(v0||w1)

w2 = h(f2) v2 = h(v1||w2)

...

wn = h(fn) vn = h(vn−1||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, w′1, . . . , w

′

m 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

Bob’s 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 Alice’s 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 Bob’s RSA

signature verification key, known to Alice, and let K−1B = (d, n) be Bob’s

private signature key, known only to Bob. Bob signs a message m using the

function SK−1B

(m) = (m,md mod n).

Suppose that messages are represented as a number mod n, where n is

the modulus in Bob’s 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 = r

e × 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 SK−1B

(mr) = (mr, (mr)

d mod n) to Alice.

(a) Show that Alice is now able to efficiently compute SK−1B

(m(N)), even

though she does not have Bob’s signature key K−1B . This means that

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

re1 ×m(N1) mod n

re2 ×m(N2) mod n

...

rek ×m(Nk) mod n

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 6= i, so that he can compute the values r−ej × xj mod n, and

check that it is equal to a message of the right form m(N). (Note that

if xj = r

e

j ×m(Nj) mod n, then r−ej × xj mod n = r−ej × rej ×m(Nj)

7

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 = r

e

j ×m(Nj) mod n if j 6= i

and xi = r

e

i × “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 Bob’s 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 Bob’s 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 = r

e

i × m(Ni) that he signs. Explain why this is the

case.

Question 5 (Bitcoin Protocol: Suppose that all of Australia’s 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 don’t want to carry

around your Bitcoin private keys written on pieces of paper. You’d 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. (You’d 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. We’ll 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 don’t 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

学霸联盟

- 留学生代写
- Python代写
- Java代写
- c/c++代写
- 数据库代写
- 算法代写
- 机器学习代写
- 数据挖掘代写
- 数据分析代写
- Android代写
- html代写
- 计算机网络代写
- 操作系统代写
- 计算机体系结构代写
- R代写
- 数学代写
- 金融作业代写
- 微观经济学代写
- 会计代写
- 统计代写
- 生物代写
- 物理代写
- 机械代写
- Assignment代写
- sql数据库代写
- analysis代写
- Haskell代写
- Linux代写
- Shell代写
- Diode Ideality Factor代写
- 宏观经济学代写
- 经济代写
- 计量经济代写
- math代写
- 金融统计代写
- 经济统计代写
- 概率论代写
- 代数代写
- 工程作业代写
- Databases代写
- 逻辑代写
- JavaScript代写
- Matlab代写
- Unity代写
- BigDate大数据代写
- 汇编代写
- stat代写
- scala代写
- OpenGL代写
- CS代写
- 程序代写
- 简答代写
- Excel代写
- Logisim代写
- 代码代写
- 手写题代写
- 电子工程代写
- 判断代写
- 论文代写
- stata代写
- witness代写
- statscloud代写
- 证明代写
- 非欧几何代写
- 理论代写
- http代写
- MySQL代写
- PHP代写
- 计算代写
- 考试代写
- 博弈论代写
- 英语代写
- essay代写
- 不限代写
- lingo代写
- 线性代数代写
- 文本处理代写
- 商科代写
- visual studio代写
- 光谱分析代写
- report代写
- GCP代写
- 无代写
- 电力系统代写
- refinitiv eikon代写
- 运筹学代写
- simulink代写
- 单片机代写
- GAMS代写
- 人力资源代写
- 报告代写
- SQLAlchemy代写
- Stufio代写
- sklearn代写
- 计算机架构代写
- 贝叶斯代写
- 以太坊代写
- 计算证明代写
- prolog代写
- 交互设计代写
- mips代写
- css代写
- 云计算代写
- dafny代写
- quiz考试代写
- js代写
- 密码学代写
- ml代写
- 水利工程基础代写
- 经济管理代写
- Rmarkdown代写
- 电路代写
- 质量管理画图代写
- sas代写
- 金融数学代写
- processing代写
- 预测分析代写
- 机械力学代写
- vhdl代写
- solidworks代写
- 不涉及代写
- 计算分析代写
- Netlogo代写
- openbugs代写
- 土木代写
- 国际金融专题代写
- 离散数学代写
- openssl代写
- 化学材料代写
- eview代写
- nlp代写
- Assembly language代写
- gproms代写
- studio代写
- robot analyse代写
- pytorch代写
- 证明题代写
- latex代写
- coq代写
- 市场营销论文代写
- 人力资论文代写
- weka代写
- 英文代写
- Minitab代写
- 航空代写
- webots代写
- Advanced Management Accounting代写
- Lunix代写
- 云基础代写
- 有限状态过程代写
- aws代写
- AI代写
- 图灵机代写
- Sociology代写
- 分析代写
- 经济开发代写
- Data代写
- jupyter代写
- 通信考试代写
- 网络安全代写
- 固体力学代写
- spss代写
- 无编程代写
- react代写
- Ocaml代写
- 期货期权代写
- Scheme代写
- 数学统计代写
- 信息安全代写
- Bloomberg代写
- 残疾与创新设计代写
- 历史代写
- 理论题代写
- cpu代写
- 计量代写
- Xpress-IVE代写
- 微积分代写
- 材料学代写
- 代写
- 会计信息系统代写
- 凸优化代写
- 投资代写
- F#代写
- C#代写
- arm代写
- 伪代码代写
- 白话代写
- IC集成电路代写
- reasoning代写
- agents代写
- 精算代写
- opencl代写
- Perl代写
- 图像处理代写
- 工程电磁场代写
- 时间序列代写
- 数据结构算法代写
- 网络基础代写
- 画图代写
- Marie代写
- ASP代写
- EViews代写
- Interval Temporal Logic代写
- ccgarch代写
- rmgarch代写
- jmp代写
- 选择填空代写
- mathematics代写
- winbugs代写
- maya代写
- Directx代写
- PPT代写
- 可视化代写
- 工程材料代写
- 环境代写
- abaqus代写
- 投资组合代写
- 选择题代写
- openmp.c代写
- cuda.cu代写
- 传感器基础代写
- 区块链比特币代写
- 土壤固结代写
- 电气代写
- 电子设计代写
- 主观题代写
- 金融微积代写
- ajax代写
- Risk theory代写
- tcp代写
- tableau代写
- mylab代写
- research paper代写
- 手写代写
- 管理代写
- paper代写
- 毕设代写
- 衍生品代写
- 学术论文代写
- 计算画图代写
- SPIM汇编代写
- 演讲稿代写
- 金融实证代写
- 环境化学代写
- 通信代写
- 股权市场代写
- 计算机逻辑代写
- Microsoft Visio代写
- 业务流程管理代写
- Spark代写
- USYD代写
- 数值分析代写
- 有限元代写
- 抽代代写
- 不限定代写
- IOS代写
- scikit-learn代写
- ts angular代写
- sml代写
- 管理决策分析代写
- vba代写
- 墨大代写
- erlang代写
- Azure代写
- 粒子物理代写
- 编译器代写
- socket代写
- 商业分析代写
- 财务报表分析代写
- Machine Learning代写
- 国际贸易代写
- code代写
- 流体力学代写
- 辅导代写
- 设计代写
- marketing代写
- web代写
- 计算机代写
- verilog代写
- 心理学代写
- 线性回归代写
- 高级数据分析代写
- clingo代写
- Mplab代写
- coventorware代写
- creo代写
- nosql代写
- 供应链代写
- uml代写
- 数字业务技术代写
- 数字业务管理代写
- 结构分析代写
- tf-idf代写
- 地理代写
- financial modeling代写
- quantlib代写
- 电力电子元件代写
- atenda 2D代写
- 宏观代写
- 媒体代写
- 政治代写
- 化学代写
- 随机过程代写
- self attension算法代写
- arm assembly代写
- wireshark代写
- openCV代写
- Uncertainty Quantificatio代写
- prolong代写
- IPYthon代写
- Digital system design 代写
- julia代写
- Advanced Geotechnical Engineering代写
- 回答问题代写
- junit代写
- solidty代写
- maple代写
- 光电技术代写
- 网页代写
- 网络分析代写
- ENVI代写
- gimp代写
- sfml代写
- 社会学代写
- simulationX solidwork代写
- unity 3D代写
- ansys代写
- react native代写
- Alloy代写
- Applied Matrix代写
- JMP PRO代写
- 微观代写
- 人类健康代写
- 市场代写
- proposal代写
- 软件代写
- 信息检索代写
- 商法代写
- 信号代写
- pycharm代写
- 金融风险管理代写
- 数据可视化代写
- fashion代写
- 加拿大代写
- 经济学代写
- Behavioural Finance代写
- cytoscape代写
- 推荐代写
- 金融经济代写
- optimization代写
- alteryxy代写
- tabluea代写
- sas viya代写
- ads代写
- 实时系统代写
- 药剂学代写
- os代写
- Mathematica代写
- Xcode代写
- Swift代写
- rattle代写
- 人工智能代写
- 流体代写
- 结构力学代写
- Communications代写
- 动物学代写
- 问答代写
- MiKTEX代写
- 图论代写
- 数据科学代写
- 计算机安全代写
- 日本历史代写
- gis代写
- rs代写
- 语言代写
- 电学代写
- flutter代写
- drat代写
- 澳洲代写
- 医药代写
- ox代写
- 营销代写
- pddl代写
- 工程项目代写
- archi代写
- Propositional Logic代写
- 国际财务管理代写
- 高宏代写
- 模型代写
- 润色代写
- 营养学论文代写
- 热力学代写
- Acct代写
- Data Synthesis代写