cryptographic distinguisher.
$2-8 USD/小时
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 ([url removed, login to view]:[url removed, login to view]). 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!!!!
项目ID: #8728461