FINAL CSC 507.122 CSC 609.122 Out: Friday, May 4, 11:59 AM Due: Tuesday, May 8, noon PROBLEM 1: PSEUDO-RANDOM NUMBERS Please complete Exercise 8.5 from the textbook. PROBLEM 2: PSEUDO-RANDOM NUMBERS Please complete Exercise 8.9 from the textbook. PROBLEM 3: BPLIPCOIN Bitcoin is an electronic money system that came out of nowhere, created by Satoshi Nakamoto, who probably doesn't exist, to become the must successful electronic money scheme so far. It depends on the hashing problem that I gave in the midterm: Given a message m to sign, find a random r such that HASH(m,r) has a special form. You make the special form "rare", and because the hash is cryptographically strong, all one can do is throw random r's at it until one stumbles upon the desired result. It also depends up a chain of "blocks of transactions", that are chained together by including the hash of last one in the hashing of the new one. Each transaction transfers bitcoins. Bitcoin owners are the same as public-keys of a public key encryption system. The owner of public key P_a can sign with its private key a transaction: give C of my bitcoints to the owner of public-key P_b, and state the new balances of P_a and P_b. Some clients in the bitcoin system will confirm this transaction by looking at the history (yes the entire history) to confirm that the new balances are correct, and then find an R that hash-seals the new block as the new head of the chain of blocks. Because it takes a great deal of computation to find that R, only a few clients will engage in the role of confirming transactions, and it will take about 10 minutes before a transaction is confirmed. In that time period no client will act on P_a's and P_b's new balance. This give time to detect double-spending and hidden transactions. Clients that invest resource to confirm transactions are rewarded by a small payment, in bitcoins of course, for every transaction they are the first to confirm. There is only one chain, and one head of the chain at any moment. If two continuations of the chain are present, the one with the oldest time stamp wins. And that winner is the one that gets the freshly minted bit-coin. THE BLIPCOIN GAME: To get the hang of bitcoin, we will play an easy version of the bitcoin game called the blipcoin game. The idea is the pass the blipcoin around the class. Each transaction has a fee, which is the solution to a hashing problem. The solution becomes the new indicator of the blipcoin. It is as if the serial number of a dollar got updated on each transaction, and each transaction can be accounted for by a hashing equation solely involving the serial numbers. The next parallel is the public statement of the hash chain. We will do this with a bulletin board, aka, twitter. Twitter with hashtag "#blipcoin" your proof of the solution to the hashing problem. Makesure you solve for the next blipcoin given the most recent solution. The genesis blipcoin is "myfirstblipcoin0". My first exchange (to me) I twit: echo myfirstblipcoin0:blipcoin98426725 | md5sum 1809eb7498c696a4c61bebcf04000000 - #blipcoin ** REMEMBER TO SEARCH TWITTER FOR HASHTAG #blibcoin, SO YOU KNOW THE LATEST BLIPCOIN TO WORK ON. DEFINE: A _blipcoin_ is a 16 character string from the set [A-Za-z0-9]. Also, the i-th blipcoin c_i is related to the (i-1)-th blipcoin by MD5( c_{i-1} || ":" || c_i || "\n") having the last 6 digits zero. ***but see note of fewer zero digits*** CODE: On linux bash shell it is defined: a=myfirstblipcoin0; b=anotherblipcoin1 ; c=`echo $a:$b | md5sum` ; echo ${c:0:15} given that a=myfirstblipcoin0; b=anotherblipcoin1 ; c=`echo $a:$b | md5sum` ; echo ${c:28:4} is the string "000000". ***but see note of fewer zero digits*** TWITTER: echo myfirstblipcoin0:blipcoin98426725 | md5sum 1809eb7498c696a4c61bebcf04000000 - #blipcoin where you change myfirstblipcoin0 to the previous blipcoin and blipcoin98426725 to your newly minted blipcoin. DEBASING THE CURRENCY: If you can't get 6 zero digits (I couldn't until I did "use MD5;" in my perl code, and used hd5_hex($a) to hash string $a) then use fewer. We will see it in the twitter posting. In the parlance of the history of money, this is called debasing the currency. It's a time honored technique by which governments (kings and queens) to make ends meet when they just don't have enough gold (or silver) to mint truely correct coins. ERRATA: OK, I sort of messed this up, but nevermind. I defined the "next blipcoin" variously as the random amount you need to get the appropriate hash, or the first digits of the hash once you got it. The code calcuated the latter, while the definition refered to the former. Either way full credit. PROBLEM 4: GALOIS FIELDS So far we have seen how Z_p, p a prime, is a field (i.e., operations for plus, minus, times and divide, with rules exactly as for the real numbers). Z_p is not the only finite number system that is a field. We show how to construct Z_{p^i}, i a positive integer. That is, for fields with the number of elements the power of a prime, not just a prime. These are called GALIOS FIELDS. Galois fields for Z_{p^i} starts with Z_p. Then you make polynomials with coefficients in Z_p, and all that Z_p[x], where the "box around the x" means polynomials in x. Then pick one polynomial in Z_p[x], say g, and take all polynomials remainder this polyonmial. Call that Z_p[x]/g. If g does not factor, i.e. it is "prime", then Z_p[x]/g is a field, and it will look like polynomials of a limited degress with coefficients in Z_p. This i just like how Z_p "rolls up" from Z, but picking a "prime" and making the remainder of an integer when divided by p the new idea of a number. You will work through an example for Z_27. 27 = 3^3, a prime power. I need an irreducible polynomial with coefficients in Z_3 with degree 3. Here is one: 1 + 2x + x^3 That cannot be factored. Why? Because if it could be factored, a factor has to be of the form (x-a). If 1+2x+x^3 = (x-a) g(x), then for x=a 1+2x+x^3=0. But I check for all possible a's, x=0, x=1 and x=2, and 1+2x+x^3 does not equal zero for any of these. Hence my Galois field of 27 elements is: Z_3[x]/(1+2x+x^3). The elements are (a + b x + c x^2) where a,b and c are from {0,1,2}. Adding is just like adding polynomials, except reduce the coefficients mod 3. Example: (2+2x+x^2) + (1+2x+x^3) = (2+1) + (2+2)x + x^2 + x^3 = x + x^2 + x^3 Question: Please make a multiplication table for all 27 elements. Question: Please make a list showing the inverse of each element. Question: Find all squares, and give all square roots for each square. Question: Solve the equation: (1+x+x^2) * R + (2+x) = (1+2x^2) for R. PROBLEM 5: SECRET SHARING: The method for Shamir (t,w) secret sharing is in your book, and you are to complete Execise 13.1. I will introduce the method and the solution here, and you can also read about it on the book. Motivation - Although a single person might not be trusted, perhaps a coalition of enough people can. Idea - A secret will be "split" into w parts by a formula, and each of w people will receive one part. Any t people from among the w, t<=w, can combine their parts to reconstruct the secret. But if fewer than t try to combine their parts, they cannot reconstruct the secret. Split Method - The Shamir scheme works by polynomials. Let p be a large prime. Let s be the secret, a number in Z_p. Do: * Choose a_1, a_2, .. a_{t-1} numbers in Z_p * Form the polynomial: f(x) = s + a_1 * x + a_2 * x^2 + ... + a_{t-1} * x^{t-1} * Chose x_1, x_2, ..., x_w distinct non-zero numbers in Z_p * Set y_i = f(x_i), and give the person i the pair (x_i,y_i) * Throw away the a_i's. The secret is now shared. Reconstruction Method - To reconstruct the secret, t players provide their (x_i,y_i). A polynomial f' of degree t-1 is calculated so that y_i = f'(x_i). It must be f' = f. Then s = f'(0). ** Your task is to write the code that creates the polynomial f' from the given (x_i, y_i). How to do that: LEGRANGE INTERPOLATION Step 1: Consider the set {x_1, x_2, ... x_w} and a x_i from among them. Create a function L_i(x) such that L_i(x_j) = 0 if i!=j and L_i(x_i) =1. (To be continued, see below.) Step 2: Now you have the L_i, then f'(x) = y_1 * L_i(x) + y_2 * L_2(x) + ... + y_w * L_w(x) This function obviously has f'(x_i) = y_i. Step 1 continued: so how do we make L_i(x)? Like this: L_i(x) = K * (x-x_1) * (x-x_2) * ... * (x-x_{i-1}) * (x-x_{i+1}) * ... * (x-x_w) That is, (x - x_j) multiplied together for all j not equal to i, and then figure out what K should be to make the mess equal 1 when x_i is plugged in. (This formula is also give on page 404, Theorem 10.3, except that they show how to get K little by little, by dividing by (x_i-x_j) for every (x-x_j) you multiply by. It works out the same.) ** Remember you are working Mod P, P a prime! Now complete Exercise 8.5 from the textbook. PROBLEM 5: ENCRYPTION AND COMPRESSION It is said that a proper encryption will turn a file into a file which cannot be furhter encrypted. Task 1: Demonstrate this. Find some files that compresses well (recomended to use gzip); then encrypt (recommended to use openssl enc) with a simple password; compress the now-encrypted file. Use different sorts of files under different encryptions. Say 4 file types and 4 different encryptions. Task 2: Write conclusions. Task 3: Explain. Here is my closing conundrum for you: Compresion squeezes down a file by extracting in information and reducing the file to just that information. How can it be that by adding the tiny additional amount of information of the password to a file that in now has so much information to be incompressible? Where did all that new information come from which is blocking the compression from squeezing down the file?