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
*E*be an IND-CCA encryption scheme, and then define a two-block version of this by_{K}(P) -> C*E2*. It turns out that this construction is IND-CPA secure, but_{K}(P_{1},P_{2}) -> (C_{1},C_{2})=(E_{K}(P_{1}),E_{K}(P_{2}))*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*) Consider the value`modPow`function in the`BigInteger`class, and in Python you can use the built-in`pow`function, where`pow(a,x,n)`computes*a*.^{x}mod n*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*a*for each of these three^{n-1}mod n*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."

- (a) Select three different random
- 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*a*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}mod n - (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(n*time, but what exactly is^{c})*c*? Figure it out! Here's what you need to do: Assume that the running time is*T(n)=k·n*for some constants^{c}*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?

- (a) Implement a function in Java that takes a single parameter,
representing a number of bits, and does the following: Use the