CSci 4554 Lab 5. Digital Cash

Due Monday, Dec 9 at 11:59pm (by e-mail)

40 points total

Description

This lab is done in groups of 2. The goal of the lab is to implement implement a zero-knowledge identity proof and digital cash. You will also get practice detecting dishonest participants.

All exchanges are done via google docs shared with the appropriate group and myself. No one else should be included.

Tasks for the lab:

Your task is to implement digital cash, as described in this overview. Different groups will be assigned different roles. The goal is to be able to distinguish a legitimate transaction from an attempt to cheat. The roles and tasks will be as follows:

• The bank (only one group): blind-sign customers' money while checking that the customers follow the protocol. When the money is deposited after the transaction, check for double-spending. If double-spending is detected, open up the two bills to find out who double-spent.
• Customers ("Alice" groups): generate money for digital signatures, unblind money, pay "Bob" (the merchant). Customers groups create 3 "customers" each (give them names, create accounts for them at the bank). Once all the customers get money, each customer must pay a merchant. Important: some of the "bills" paid to the mercants must be illegitimate copies of bills spent elsewhere, and some must be legitimate. Also, at least one bill must be fake, i.e. not signed properly by the bank.
• Merchants ("Bob" groups): accept money from customers, verify its legitimacy (find the fake bill(s)). Then deposit money to the bank.

More specifically:

1. The bank generates RSA modulus in which p, q are at least 100 bits (note that we will use it to encrypt the result of SHA-1 which is 160 bits). To follow the the suggested scheme, use e = 3. Note that 1/3 in the description refers to d (the inverse of e mod (p-1)(q-1)).
2. All parties need to use a seeded random number generator. Each group needs to pick a large (at least 5 digits) seed. This guarantees (hopefully) that all the seeds are different.
3. Account numbers for customers are 10-digit binary numbers. They are set by the bank.
4. The customer group creates digital cash (say, in $100 bills) for each customer as defined in the protocol. Assume k = 40. The parameters are as follows:
   • A randomly generated 10-digit binary serial number for the bill.
   • a_i are random 20-digit binary numbers
   • y_i is the SHA-1 of the following: XOR of a_i and the concatenation of the account number and the bill serial number. It needs to be stored as a hexadecimal string. Here are some helpful links: an example of a message digest, how to convert from a byte array to a string of hexadecimals.
   • x_i = SHA-1 (a_i) as a hexadecimal string.
5. Keep a_i, y_i, and x_i and the blinding factor for each element of each bill. Keep track of which elements have been opened by the bank and discarded.
6. After all a_i, x_i, and y_i are created, "Alice" (the customer) concatenates x_i and y_i and computes SHA-1 of the result (this is the g(x_i, y_i) part of the protocol). The concatenation is treated as a string. Then follow the example on how to pass it to SHA-1. The result of SHA-1 is represented as a BigInteger created by passing the result of SHA-1 (the byte array) to BigInteger constructor.
7. Then she generates a "blinding factor" r_i for each g(x_i, y_i) and sends all of them (blinded) to the bank for a blind signature. Recall that "Alice" needs to prepare the blinding factors so that she can easily compute a signature for the bill. Note that at least one of the customers is expected to be cheating at this point.
8. The bank send each customer ("Alice") a request to open randomly chosen 20 bills. The customer sends the blinding factor to unblind those. If the bank detects cheating, the customer repeats the procedure.
9. After the bank verifies the bills, it signs the product of the remaining k/2 numbers mod N (as an RSA signature).
10. The customer unblinds the signed cash by dividing it by the product of the unblinding factors of the 20 remaining elements.
11. The customer pays some of the merchants with the signed bills by sending the bill (the product) and its signature. The merchant verifies the bank signature (if it's not a proper signature, the transaction gets canceled). In the process he sends the customer a randomly chosen sequence of k/2 0s and 1s and the customer sends the corresponding elements:
    • a_i and y_i for 1
    • a_i xor < info> and x_1 for 0.
    Then for each i "Bob" can find x_i and y_i, compute SHA-1 of their concatenation, and verify the bank's signature on their product. "Alice" has to try to cheat at this point by providing a bill that hasn't been properly signed.
12. When the money is deposited (with the customer responses to 0/1 challenges), the bank checks the cash value and verifies that the cash has not been double-spent. If it has been, the bank uses the 0/1 challenges to find out who is the cheater. "Alice" group has to double-spend at least one bill, the bank has to detect it.

What to submit (by e-mail to me, CC your partner)

1. All your program code (well-documented) and instructions for running it.
2. All your computations with explanations.
3. Detailed explanations of what you were doing and why.

CSci 4554 course web site.