cryptographic distinguisher.

Make your own cryptographic distinguisher. Many definitions of security in cryptography involve the concept of a distinguisher. One such definition relates to _pseudorandomness_. Let G be a function which takes an n-bit binary string s and returns an l-bit binary string G(s), where l>n. We think of s as being the seed, G as being a random number generator, and G(s) being the output. The seed s is truly random, but the output G(s) is at best _pseudorandom_. Roughly, G is a pseudorandom number generator (PRNG) if there is no way to differentiate the output of G from a truly random l-bit binary string. Really there is no such thing as a particular output being random or not random. Rather we have to tell whether the distribution that G(s) gives rise to on the set of l-bit binary strings is distinguishable from the uniform distribution on l-bit binary strings with reasonable computational resources. A PRNG _distinguisher_ D is defined as follows: A truly random seed s is selected from the set of n-bit strings. A truly random string r is selected from the set of l-bit binary strings. We define a variable w, and flip a coin. If the outcome is heads, we set w=G(s). If the outcome is tails, we set w=r. Note that w is an l-bit binary string in either case. The distinguisher D is an algorithm that takes w as input. D does not know what w really is. But D must make a decision as to whether w=G(s) or w=r. The output of D is the decision it makes. We say that G is a PRNG if there is no efficient algorithm D that is a distinguisher for G which has better than a 50% chance of predicting whether w=G(s) or w=r. We give an example of all this in class -- refer to your notes for a concrete example. ASSIGNMENT: Read the Wikipedia article on Linear Feedback Shift Registers (LFSRs). There is a figure in this article which shows a particular 4-bit LFSR ([login to view URL]:[login to view URL]). We will be using this particular LFSR in this assignment. For definiteness, let us refer to this LFSR as Max. Define G(s) as follows. The seed s is a starting state for Max. This is a truly random 4-bit value. We produce G(s) by letting Max generate 64 bits of output. Thus l=64 and n=4 in this case. Your job is to show that G is not a PRNG by exhibiting a D which distinguishes G from the true uniform distribution on 64-bit strings. You must discover some property that the outputs of G have that true random 64-bit strings are very unlikely to have. You should start by coding up Max and producing some sample data. Can you see a pattern in Max's outputs that true random strings shouldn't have? This is the basis for how your D will work. Once you have designed your D, you should implement it and see how well it works. Please hand in: 1. Your code for Max 2. Your code for D 3. A mathematical argument that quantifies how likely D is to give the correct output 4. Empirical data that shows that D is correct with something close to this frequency. You can do (4) by writing code which produces w as described in the definition for distinguishers, gives it to D, and records whether D was right or wrong. Remember that D must succeed better than 50% of the time to be a real distinguisher. C++ ONLY!!!!