The next two use python. The starting templates with makefile are found in the class folder of the course repository. The python code follows the class text proofs of security, the adversary game and the reduction from pseudorandomness to the unbreakability of a cipher, by doing the mathematical construction in code. I hope this make the rather complicated construction more understandable.
In the last project, you will also be introduced to the LFSR, and their use as a PRG. Although there are strong PRG's based on LFSR, see Trivium, three of the ones I present are easily broken, and these make a good exercise finding the weakness. The fourth, I'm not so sure about. It is based on a typically considered extension to LFSR's, and I leave it to you to explore for a weakness.
The probability distribution is P(C|M=m) for a shift cipher on the with keys 0 through 25 and messages m a single letter, "a" through "z". Hence the distribution is a bar chart of 26 value, for each of the ciphertext c, of the probability (over the probability space of key choice) that m enciphers to c. We will assume the message texts are chosen uniformly at random.
In the spirit of the indistinguishability game, give a method for predicting which of m0 or m1 was enciphered given c, and calculate the advantage.
The code template is given in [repo]/class/proj2/adv-indistin.py; comments indicate where you are to complete the code. Copy to your [repo]/[user]/proj2 along with the Makefile, complete and submit. A fully correct solution completes part (a) of the exercise by both calculating the theoretic advantage of the method given, and comparing with the experimental result; also by completely part (b) and finding a stronger method, with greater advantage, showing that in the code, and running for an experimental result.
Note that this is 2.6 code; please make changes after copying to you folder if you are using 3.0.
The adversary_advantage function repeatedly runs adversary_sample to get the probability that the adversary wins the indistinguishability game, i.e. that the adversary can distinguish whether it was message 0 or message 1 that was encrypted. The adversary provides the messages by the return value of adversary_challenge and the logic to decide based on the ciphertext is in adversary_decision. The cipher logic needs to be completed; the key generator is complete.
The code template is given in [repo]/class/proj2/prg-distingu.py; comments indicate where you are to complete the code. Copy to your [repo]/[user]/proj2 along with the Makefile, complete and submit. A fully correct solution should show advantage when the A generator is run against a truly random generator; and likewise for the B generator.
Note that this is 2.6 code; please make changes after copying to you folder if you are using 3.0.
The function adversary_sample is a presented with a generator of pseudorandom bits and returns true or false based on advice from a further function adversary_decision, which is the decision of an adversary playing the indistinguishability game for a vernon cipher. The connection between the pseudorandom bits and the vernon cipher, is that the vernon cipher enciphers using the given pseudorandom generator. In particular, a "true" (by our low standards) random string is provided to the vernon cipher, for which the adversary must have no advantage; then a string generated by a Linear Feedback Shift Register (LFSR) are given, and your programming of the decision function should be able to have an advantage in the indistinguishability game.
The code for the generators is supplied. We will talk in class about the LFSR's and their possible weaknesses for random bit generation. There are four generators provided. The first task is to work against the generator "A". The second task is a challenge problem to work against generator "B". The B generator combines short generators S and T by stepping one or the other depending on the next bit drawn from generator A.
author: burton rosenberg
created: 4 feb 2018
update: 5 feb 2018