cryptographic distinguisher.

进行中 已发布的 Oct 20, 2015 货到付款
进行中

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!!!!

C++编程 计算机安全 密码学

项目ID: #8728461

关于项目

3个方案 远程项目 活跃的Oct 20, 2015

授予:

InkCoder

Hi!, I specialize in cryptography and i think i can help you out here. Already many algorithms exist which can be used for creating a distinguisher for LFSR generated random sequences. If you are okay with the bidd 更多

$7 USD / 小时
(2条评论)
1.1

有3名威客正在参与此工作的竞标,均价$38/小时

ahmsak

A proposal has not yet been provided

$100 USD / 小时
(24条评论)
4.8
Gabry97

I really love programming and I would like to become a C++ programmer, so it would be a good start! I wish I can solve your problem.

$6 USD / 小时
(0条评论)
0.0