[Solved] CPSC 418 -Assignment 1

Written Problems forPassword length and entropy (20 marks)ASCII, short for American Standard Code for Information Interchange, is a method for encoding any character into a string of 7 bits. For example, the ASCII codes for A, a, and ? are 1000001, 1100001, and 0111111, respectively1. ASCII has long been superseded by the much more modern and extensive UTF-8 encoding method; ASCII codes constitute a very small subset of UTF-8 codes.A password can only contain printable characters that appear on a standard US English keyboard. These include 26 upper case letters, 26 lower case letters, 10 numerical digits and the 32 special characters `’.,;:[email protected]#$%^&*_-+=(){}[]<>/|. Not all ASCII codes correspond to printable characters.a. (2 marks) What is the total number of ASCII encodings of 8-character strings?b. What is the number of passwords of length 8 consisting of(i) (2 marks) any printable characters?(ii) (2 marks) lower case letters only?c. Approximately what percentage of 8-character ASCII encodings are passwords consisting of(i) (2 marks) any printable characters?(ii) (2 marks) lower case letters only?d. Assuming that each character in a password is chosen equally likely, what is the entropy of the space of passwords consisting of(i) (2 marks) 8 printable characters?(ii) (2 marks) 8 lower case letters?e. Suppose we want a password space with entropy 128, i.e. a total of 2128 passwords assuming that all passwords are equally likely.2 What is the minimum password length, i.e. the minimum number of characters in a password, to achieve this entropy, assuming that passwords consist of(i) (3 marks) any printable characters?(ii) (3 marks) lower case letters only?1Source: https://www.ascii-code.com.2For modern cryptosystems, 2128 is a typical key space size. Of course the assumption that all passwords are equally likely is a stretch: most of us use only a small handful of our favourite passwords.

Problem 2 One-time pad without the all-zeros key (6 marks)Recall that in the one-time pad, plaintexts, ciphertexts and keys are n-bit blocks for somen E N. For any key K, plaintext block M and ciphertext block C, the encryption of M withkey K is EK(M) = M K and decryption of C with key K is DK(C) = C K, wheredenotes bitwise x-or (or equivalently, bitwise addition modulo 2). Assume as always that keys are chosen with equal likelihood.When using the one-time pad with the key K = 0n consisting of n zeros, we have EK(M) = M K = M for every paintext M, i.e. M is left unencrypted. It has been suggested to improve the security of the one-time pad by only encrypting with non-zero keys, i.e. removing 0n from the key space.a. (4 marks) Use either the definition of perfect secrecy,p(M) = p(M|C) for all plaintexts M and ciphertexts C with p(C) > 0 or its equivalent characterizationp(C) = p(C|M) for all plaintexts M with p(M) > 0 and ciphertexts C with p(C) > 0to formally prove that this modification of the one-time pad does not provide perfect secrecy. Specifically, you will need to give a counterexample, i.e. exhibit a pair (M, C) that violates the definition or the above characterization of perfect secrecy. Answers that argue informally or do not use this characterization will receive very little if any credit.b. (2 marks) Explain (informally) why allowing K = 0n does not weaken the security of the one-time pad, even though using that key does not hide the plaintext when encrypting.(Note: the assertion that choosing K = 0n happens so rarely that we dont have to worry about it is not a valid answer and will not receive any credit.)Problem 3 Weak collisions (16 marks)The cryptographic relevance of this problem will become evident