Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Information Systems Security

Problem-set #1

What to submit?

Prepare a report answering each question in the problem-set. For the question that involves a little programming (Problem 1) you should experiment with your program and include in your reports a brief discussion with your observations and some screenshots. You should submit your working Python code for the first question in the form of .py files.

        Please, try not to submit lengthy reports. Excluding any screenshots and your Python scripts the entire problem-set fits in no more than 3 pages.

Problem 1 (20 points)

Devise a way to encode Latin characters such as “aAbBcC” and symbols such as “.,!?/” into binary sequences. Then write a Python program that does the following:

1. Write a function which given a binary sequence it outputs the number of 0s and the number of 1s.

2. Ask the user to specify the security parameter n, which is the length of a binary sequence to be encrypted using One Time Pad.

3. Flip n unbiased and independent bits. Research the libraries in Python of how to do this properly and how to use the system’s provided randomness. If in doubt then post questions on Canvas and the instructor will guide you (but you should still do this step correctly on your own).

4. Ask the user to give a string as input and translate this string into a binary sequence by concatenating the binary sequences by encoding the user’s string character-by character. If the encoded string as a binary sequence has length bigger than n then ask the user to provide a new, smaller string until she enters a string which fits in n bits.

5. Print the binary sequence corresponding to the string the user gave you.

6. Print the number of 0s and 1s in the above binary sequence. For this you should use the function you wrote.

7. Encrypt the message using OTP.

8. Print the encrypted binary sequence.

9. Print the number of 0s and 1s in the above binary sequence. For this you should use the function you wrote.

10. Print the characters corresponding to the encrypted message. For this you have to decode using your character encoding scheme.

11. Decrypt the message using OTP.

12. Print the binary sequence corresponding to the decrypted message.

13. Print the number of 0s and 1s in the above binary sequence. For this you should use the function you wrote.

14. Print the characters corresponding to the decrypted message. For this you have to decode using your character encoding scheme.

        Experiment with your program for a few strings (at least 3) and take screenshots that you should include in your report.

        What do you observe in the above experiments you did?

        Also, answer the following questions.

        Is it true that if the sequence is distributed uniformly random then the number of 0s is almost equal to the number of 1s?

        Is it true that if the number of 0s and the number of 1s is almost equal then the binary string is uniformly distributed?

        Read the following document and write your thoughts within no more than 200 words in relation to your above experiment.

        https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-22r1a.pdf

Problem 2 (20 points)

This exercise involves a (i) definitional part and (ii) a cryptographic construction argument part.

        First, you should define in a reasonable way what is a two-message perfect encryption. Include a definition using a security experiment as a game between a challenger and an adversary. Then, prove that a cryptographic protocol, which is similar to a “two-time pad” (i.e. same as one-time pad but for two messages – using the same key for each message) fails to satisfy the security in your definition.

        The take away message is that it is a bad idea to use a key twice without any modification. Explain at a high-level/intuitive level under which conditions is a bad idea to use a key twice.

Problem 3 (20 points)

Let us denote by Zk the set Zk = {0, 1, . . . , k − 1}. The only operation among elements of Zk is “addition modulo k”. For example, if x = k − 2 and y = k − 1 then x + y(mod k) = k − 3. There is no operation of subtraction, but it is easy to see that every element has an inverse. The inverse of 4 is denoted by (−4) and is defined to be the Zk element to which if we add 4 modulo k then we get 0. Since, 4 + (k − 4)(mod k) = 0 we have that (−4) = k − 4. Note also that the inverse of any element in Zk is unique.

        For example, Z4 = {0, 1, 2, 3} and (−0) = 0, (−1) = 3, (−2) = 2, (−3) = 1.

        Consider the definition of perfectly secret encryption and suppose that we want to transmit messages that are integers between 0 and 2ⁿ − 1, for some fixed arbitrary n (observe that such each such integer uniquely corresponds to its binary encoding, which is just an n-bit long message). The keys are also numbers between 0 and 2ⁿ − 1. We generate a new key for each message to be encrypted.

● Key(r): outputs a uniformly random integer from Z2n using the uniform random bits in r.

● Enc(m, k): outputs ciphertext c = m + k(mod 2ⁿ) (Message m ∈ Z2n.)

● Dec(c, k): outputs c + (−k)(mod 2ⁿ) where all operations and inverses are over Z2n.

recall that (−k) is not any kind of negative integer, there is no such element in the group. For example, for n = 3 then 2n = 8 and (−3) = 5 since 3 + 5( mod 8) = 0.

        Is the above protocol correct? Is the above protocol a perfectly secret encryption scheme? Justify your answers as formally as possible (ideally you should give a proof, but you can argue intuitively and rigorously enough and still get full marks).

Problem 4 (20 points)

Consider the following variant of the protocol in Problem 3.

        Instead of doing operations over Z2n we do operations over the integers as usual. This means that e.g. 3 − 10 = −7.

● Key(r): outputs a uniformly random integer from {0, . . . , 2ⁿ − 1} using the uniform random bits in r.

● Enc(m, k): outputs ciphertext c = m + k. (Message m ∈ Z2n.)

● Dec(c, k): outputs c − k, where the subtraction here is the usual integer subtraction.

Show that the above protocol is correct.

Show that the above protocol is not a perfectly secure encryption scheme.

Problem 5 (20 points)

Answer the following question by writing an essay of no more than 1000 words. You should include examples and write your thoughts on the question. In Cryptography we strive to achieve as good encryption as possible. One Time Pad achieves perfect secrecy (for our definition of perfect secrecy). Since, this is the case why do we care to give definitions and constructions that achieve less-than-perfect secrecy/security? Also, all these constructions have security which is based on so-called computational assumptions. What is a computational assumption? Why do we need anything like an “assumption” when we are talking about a mathematically rigorous topic?