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: