Problem 1 [30 points]
Write a program that increments a counter 210, 220
and 230 times (so the initial counter
value will be 0, then 1, 2, …, up to 210, then repeat with 0, 1,
220 and so on).
1. For each counter value, in each iteration compute the bitwise XOR of the counter with
the value 8003 (so let the counter be ctr
= 0, compute tr © 8003, then set etr = 1
and compute the XOR, and so on. Do that for 210, 220
and 230 counter values.
Measure how many seconds your program takes to run in each case (list the machine
specifications and the programming language you have used). Estimate how many
years your program would take to do this operation when the counter is incremented
2330 times
2. Repeat the previous counter increments but now in each iteration compute the division
of the counter value by the number 4009. Measure how many seconds your program
takes to run in each case (list the machine specifications and the programming language
you have used). Estimate how many years your program would take to do this operation
when the counter is incremented 2330 times.
Problem 2 (40 points]
Let Go : {0, 1}”
› {0, 132 and Gi: {0,1 n
› {0, 132n be PRGs. For each of the following
constructions, prove whether it is
a PRG or
not
To prove insecurity you have to show
an attack against the scheme and provide an informal argument about the attack success
probability. For security provide a convincing informal argument why it is a PRG.
1. Ge(s || t || =) = GI(s) | (tO =)
2. G3(s) = Go(5) 0 12n
3. Gals || =) = ( (s || =) @ Go(S)) || Go(s)
4. G3(s) = msb(Go(s)) | Go(s) || G1(=), where msb is the most significant bit.
(Il is the concatenation operation, @ is the bitwise XOR operation, s and & are random
strings each of which is of length n bits, and t is any string
-not necessarily random
-of
length n bits.)
Problem 3 30 points
Part 1: Answer the following for the monoalphabetic substitution cipher.
Assume you have a CPA attacker,
how much plaintext this attacker must request
encrypting in order to recover the full key (which is the permutation of the letters)?
why?
2. Will your answer change for the previous question if we consider a CCA attacker?
why?
3. If we use this cipher with totally random messages, will the letter frequency attack
that we studied in class apply here as well? why?
Part 2: Answer the following about OP (just provide informal convincing arguments, no
need for formal proofs).
Assume that Alice reuses the pad for every 500 messages she sends to Sponge. Is this
a secure way to protect the confidentiality of her communication with Sponge given
that they will exchange only 100 messages? why?
2. Is the original OTP, as we took it in class, secure if used to encrypt messages each of
which is of length 1 bit? why?