A printable PDF is available.
Assignment 4 - Due Thursday, March 24
Like Assignment 3, this is a slightly shorter assignment, with only 9 days to complete it rather than a full two weeks. Because of this, it will be graded out of 50 points, and count half as much as the regular-length assignments.
- It's clear that repeating a deterministic block cipher, as in ECB
mode, is not secure. But what about repeating a secure
(non-deterministic) cipher? In other words, let EK(P) -> C
be an IND-CCA encryption scheme, and then define a two-block version
of this by E2K(P1,P2) -> (C1,C2)=(EK(P1),EK(P2)). It turns out that this construction is
IND-CPA secure, but not IND-CCA secure. Prove the second part
of that statement (in other words, give an adversary that wins the CCA
game against the E2 two-block encryption scheme -- like almost all
CCA attacks, the trick is to disguise your decryption oracle requests
so they don't exactly repeat the challenge ciphertext). Make sure you
analyze the advantage of your adversary!
- (Note: Taking large modular powers is tricky, but modern
programming languages have good support for this -- for example, in Java you can use the
modPow function in the BigInteger class, and in
Python you can use the built-in pow function, where
pow(a,x,n) computes axmod n.)
Consider the value n=8911 (this is a composite number with factors
7, 19, and 67).
- (a) Select three different random a values in the range 2,...,8909 that are relatively prime to n, and calculate an-1mod n for each of these three a values. Does it seem that n behaves like a prime number as far as Fermat's Little Theorem is concerned?
- (b) Use your random a values from part (a) to run the Miller-Rabin primality-testing algorithm on n, showing each step. If your first a value returns "composite" you can stop with just that one simulation -- otherwise, try the other a values until you get "composite."
- What are the primitive roots of 31? (A very simple program can quickly
solve this problem.)
- All traditional public-key algorithms rely heavily on computing large
modular powers, and in this problem you will explore the computational
cost of modular powering. This problem assumes you will program this
in Java -- if you really want to use Python or another language, talk to me about this as
an alternative.
- (a) Implement a function in Java that takes a single parameter, representing a number of bits, and does the following: Use the BigInteger constructor that generates a random big integer with the specified number of bits to generate three different random big integers, say a, b, and n. Next, simply call the BigInteger method modPow to compute abmod n and return the result. Test this on some very small values (like 3 bits), print the generated values and results, and check the results using a calculator. For this part, turn in a printout of your function and show the results of your testing.
- (b) Use the "profiling" tool in NetBeans to benchmark this function (you're really profiling the built-in modPow method on random inputs) and see how long it takes to compute modular powers on 4000, 8000, and 16000 bit inputs (you can remove the printing functions you put in for part a). You should run each input size 3-5 times and record the average time (more iterations are better -- think about automating this!). If you are unsure how to use the profiling tool, documentation is available on the class web site.
- (c) Modular powering algorithms generally take Theta(nc) time, but what exactly is c? Figure it out! Here's what you need to do: Assume that the running time is T(n)=k·nc for some constants k and c, and use the times you measured for 2000 and 4000 bit powering to plug in to write out formulas for T(4000) and T(8000). Now you have two equations with two unknowns -- solve for c! Repeat the calculation using T(8000) and T(16000) and see if your results are consistent. You may very well see some small inconsistencies here -- don't worry about this for now!
- (d) Now that you know the running time of modPow, use this to estimate the running time for 32,000 bit inputs. Calculate this using the values you found, and then run a test with this input size and report on how accurate you were.
- (e) Given all of these results, why might there be some inconsistencies between measurements? Are there other issues that come into play other than just CPU speed? Can you think of a way in which cache size might make a difference?