I need help on question 2, 4, and 5.
Spring 2020 CS134: Computer and Network Security Homework 1 Due: 04/27/20: 11:59pm Full Name: UCI ID Number: Sources: Guidelines: • Use any word processor (or hand-write and scan your answers). Upload your solutions in PDF to Gradescope. • No collaboration is allowed. The only people you may consult are the TA-s and the instructor. • Looking up, paraphrasing or copying answers from the Internet or other sources is not allowed; doing so is a violation of academic honesty. You must cite any sources you use, e.g., reference books, Wikipedia, etc. Warning: Any submissions not following the above guidelines will receive a score of zero. P1 P2 P3 P4 P5 P6 Total /13 /20 /12 /20 /20 /15 /100 1 Problem 1: Attack the Code! Assume that you (somehow) have the ciphertext below sent from Alice to Bob, and you know that they are using Vigenere cipher to encrypt/decrypt their messages. You will be given a Python code that implements Vigenere cipher using a 4-character secret key. Use this code to find the key and the original plaintext that Alice sent. You can use (1) brute force attack (not recommended), (2) dictionary attack, or (3) two-dimensional frequency analysis. Your solution must include a copy of your code that used to break this ciphertext, along with a brief description of your attack. The ciphertext is below: ggwezgshndhpxvpmoofftnhsxjirnovpcjconzxfyodlynsondgbavzdgirsongaomweyvfpmjcondge nzgtyocaoxdcukcdggwdggazyoqzskzpzzpfzcsdhzwymjpdkmjpjvglvdsnkjtqxzgsszoelmcxzcsma nvpyvzztbcgkmucurbqumsdzkoeneixvnosaiucemcezrstrzfhoovekiickdbxgovskywotjhaawztyc zlzzzjgirenpgruobzxvwdkvbrkmalrdqpgirptqmlxzrtyocczdbrndgqgxshnzbenzgngmmcuohhkdz pxvdakvfdyjbpgmdzumztzozpccwekmomhdhdzvfeynvlqdbrcdhslzocjzocydftjjbeszoyzjgzairt skffjzbevgslyzgagmsxegwqkdalvcrdzprptocyrthsxzsjkvfduatftywymvboorccqgwvkvazrzdwa najrvptyvrttbmltyrlxfflhwwenjzpoamzacogkvbjjjimznhsgoajyoccedgexpstivbdnjkxemsdkv fnnxcyjdhtuigeutcfndgsaiupxnimydrpyvbozcsoubgegmhdzjzlabvendgxanhmkvxzqzmzamsyuoh zabvptjirntcfxqctizwdyjgbazovetcfnvjptjgexjbrijfpgoffkycnzjflrnhfjzbespgehzongmbt bjfpogzttyiwmzmzaovtyjbnkbcltygsurapejicrvptltcfrdsoogzpgomzavbomjrcoiylzovpvppdu ovpevamrzowuiuftowwxzonndbrgnhfskbpdohzccwnndglnjzpgirtzgczqnztqzooahdourbduhscox ypztgegdfdzcsjygchrtrpyxsyjdbeuywymtoyjyocqwiewpwekgocmzflhwwejzbhndzpjjudktsdgms ljeidzdbrzjzlifcqrduszcsdkzgmxjyptzefokaptohcgnvdzmshtgsqzvboxduszdbenzatjyzpuaow rovtynweyjblrvfrkovcuislnpupmmwkfgsordcyccctyxvpcdbrgwcykdhdtjhsgmreudalmdbpccoen vdakisozcsynpbrxtfzzokpogscyosyamsnghseuvbptyodhzttznoyenhzxthsgosyjnkprgpfznhlxo goomsenzfpspgehzoxumowzcoecdzwxzookmgttndtxzmzamgtfzrzknbesvhekmoyjistzcscjjsdbjw nkaiczcscsjfpzcsdonhzvdqtyvhcoqwlrxvzoxsljvfvgirnugrwgwktzcrzumgenvhouihwuxysgnbz hzocoiulzvzwuikskmsjupzwhzoaunhouxtzxrvlznwxvjfegihenzfponpfzjbpicctizmzamoobdgzx hoezzfdgirlrgswyzwdtjwdk Solution: 2 Problem 2: Block Cipher Assume that a block size for the toy symmetric cryptosystem below is 8-bits, and you are given a pair of keys K1 = 0x5B and K2 = 0x38, where K = K1||K2 =0x5B38 (i.e., |K| = 16 bits and |K1| = |K2| = 8 bits) and the Initial Vector IV = 0xFF. The encryption function E is defined as: E(K,m) = S(m⊕K1)⊕K2, where |m| = 8, ⊕ is exclusive-or (XOR), and S is the S-box below. For example, S(0xAF) = 0x79 and S(0xF3) = 0x0D. 1. Bob wants to use the encryption function E to send the message “HiPal” to Alice (no spaces). The message is first converted from ASCII to hexadecimal, which is given as input to the encryption function. What is the ciphertext when Bob uses the following mode of operation? Show your work. (1) ECB, (2) CBC, (3) OFB, (4) CFB, and (5) CTR 2. While the ciphertext is sent to Alice, a 1-bit error occurrs in third ciphertext block C3. Assuming that Bob used each mode of operations above, explain what happens to the plaintext that Alice decrypts. (You don’t need to decrypt all of it, but describe which blocks are affected and how.) Solution: 3 Problem 3: Birthday Paradox Extended Assume that each month of the year has 30 days. Grape County News announced that the monthly birthday probability distribution in Grape County is as follows: Jan = 35%, Feb = 5%, March = 10%, April = 5%, May = 5%, June = 5%, July = 10%, August = 0%, September = 5%, October = 10%, November = 0%, December = 10% 1. How many people do you need to pick at random to have a 100% chance of a birthday collision? 2. How many people do you need to pick at random to have a 50% chance of a birthday collision? 3. If we ignore potential collisions in January, what is the minimum number of people picked at random to have a 50% chance of collision in the other months? Solution: 4 Problem 4: Cryptographic Hash Functions Consider the following two protocols and describe which protocol is better in terms of: 1) in- tegrity of ciphertext, 2) integrity of plaintext, and 3) security against Chosen Plaintext Attack (CPA). Note that E is a CPA-secure encryption function with the encryption key kE and H is a HMAC function with the key kH . || denotes concatenation. The protocols are as follows : 1. For a message p, send [c||H(kH , c)], where c := E(kE, p). 2. For a message p, send [E(kE, p)||H(kH , p)]. Solution: 5 Problem 5: Group Theory Recall that there are 4 properties that must be satisfied for a set G and an operator @ to be a group. For the following sets and operations, show whether each (G,@) is a group. If you think (G,@) is a group, show clearly that 4 properties are satisfied and determine if the group is abelian. If you think (G,@) is a abelian group, then determine if the group is cyclic. If you think (G,@) is not a group, provide a counterexample. 1. G = Integers Z, @ = subtraction (denoted by “-”) 2. G = Z∗20 = {a ∈ Z20|a is coprime to 20}, @ = modular multiplication (denoted by “∗”) 3. G = Z, @ = integer division (denoted by “/”) e.g. x@y = x/y 4. G = (a set of n× n non-singular matrices), @ = matrix multiplication (denoted by “∗”) Solution: 6 Problem 6: Basic Number Theory Show your solutions in detail. No points will be given for answers without details. 1. What is the minimum number of multiplications you need to compute 6153 mod 59? 2. Recall that Φ is a Euler phi function. Compute Φ(97) and Φ(221). 3. See if there exists the inverse of: (1) 5 mod 59, and (2) 29 mod 59. Compute the inverse if it exists and, if it doesn’t exist, say why. Solution: 7