Cryptography Homework

QUICK LINK TO HOMEWORK ASSIGNMENTS:

1 2 3 4 5

General information

HTML NOTE: This document was written in HTML 4.01 which supports a rich set of useful mathematical symbols. Open source browsers tend to be better at rendering the symbols than proprietary browsers. If after attempting several different browsers you are still having difficulties, please let us know and we will post a pdf version.

Homework 1: Classical Cryptography

  1. (40 pts.) Cryptanalyze any two of the ciphertexts in your personal directory (you should have received an email about this). For full credit you should give the discovered key. More information is available at the cryptanalysis page and in the cryptanalysis lecture. It is recommended that you use webcrypt for your cryptanalysis work. For EXTRA CREDIT you may cryptanalyze one or both remaining texts for an extra 20 or 40 points.
  2. This problem is related to Stinson's exercise 1.12 (and you will see a useful hint there).
    1. (10 pts.) Find a formula for the cardinality of Mn(26)* (the set of invertible-mod-26 n by n matrices). You may use the following:
      THEOREM: Let a, b be relatively prime integers. There is a one-to-one correspondence between Mn(ab)* and Mn(a)* × Mn(b)*.
    2. (5 pts.) What is the probability that a randomly chosen 3 by 3 mod-26-matrix will be invertible?
    3. (5 pts.) A message has been encrypted with Hill's cipher using a 3 by 3 matrix key. Suppose that a cryptanalyist knows the key-size and is going to use the known plaintext attack described in lecture. How long should the known part of the message be to ensure that the method works with likelihood greater than 95% ?
  3. (5 pts.) Consider the following attempted improvement on the One Time Pad (OTP) cipher. As with OTP, we take P = C = K = {0, 1}n and keys are chosen uniformly at random. We change the encryption function as follows: instead of just taking the XOR of the plaintext with the key, we take an additional XOR with the reversal of the key in an attempt to obfuscate. I.e.
    eK(x) = x ⊕ K ⊕ KR
    where KR denotes string reversal so for example 011010111R = 111010110. Is the modification perfectly secure? Prove your claim.
  4. (15 pts.) Breaking a perfectly secure cipher. Clever Clive is running a server and has come up with a perfectly secure cipher for encrypting passwords when a client (Alice) initiates a session. Clive's cryptosystem is defined by:
    1. Notice that the cryptosystem diverges from Stinson's definition in that eK is no longer a deterministic function. Show that it is still a valid cryptosystem by giving a formula for a deterministic decryption function dK.
    2. Show that Clive's system is perfectly secure. Hint: the definitions and theorems concerning perfect security are still valid, but the probability of any ciphertext occuring depends on the random variable for encryption, in addition to the previous random variables.
    3. To use the system for authenticating passwords, Clive has established the following protocol with Alice (and similarly for other clients):
      • N random session keys K1 ... KN are agreed to off-line
      • A session number I is kept by both parties so that both can know to use KI next
      • At the beginning of a given session Alice attempts to send her password p encrypted as eKI(p)
      • Clive decrypts as usual obtaining p'.
        • If p = p' Alice is authenticated and the session may continue
        • If p ≠ p' Alice is rejected, Clive sends back a special signal "∅", and the session is terminated
      • In either case, I is incremented.
      Now suppose a man-in-the-middle attack is launched by Mallory:
      Here Mallory can listen to and alter all of the communications between Alice and Clive in both directions. How can Mallory learn Alice's password after only 50 sessions? The point here is that "perfect security" guarantees nothing when applied to more complicated protocols than the definition intends.
  5. Problem 2.2 (Stinson)
  6. Problem 2.4 (Stinson)

Homework 2: Block Ciphers, MAC's, Number Theory

Problems

  1. Problem 3.1 (Stinson)
  2. (15 pts.) This problem uses the notation of the block-cipher lecture for permutations ρ and substitutions built up from S-boxes, σ.
    1. Show that the following identity holds for any permutation ρ:
      ρ(x ⊕ y) = ρ(x) ⊕ ρ(y)
    2. Consider a substitution-permutation network as defined in Stinson §3.2 (or the the block-cipher lecture). Suppose that each S-box πS were replaced by the identity function. Give a simple formula for the resulting encryption function eK of the substitution-permuation network.
    3. Explain why removing the S-boxes from the substitution-permutation network results in a very weak block cipher. Describe a specific attack method.
  3. (15 pts.) This problem uses the notation of the block-cipher lecture for the three types of coordinate respamplings: Furthermore, x denotes the bitwise complement of x.
    1. Show that the following identity holds for any coordinate resampling ρ:
      ρ(x ) = ρ(x)
    2. Let e(K,x) denote the DES encryption function of plaintext x with key K. Prove the complementary key property:
      e(K, x) = e(K,x)
      The information about DES from the block-cipher lecture should suffice to do this problem.
    3. Show that a Chosen Plaintext Attack can be mounted agains DES that needs only search half of the key-space. HINT: Eve tricks Alice into sending 2 chosen plaintexts.
  4. (5 pts.) Supposing that in the future, holography will allow 3D memory storage at the rate of 1 terabyte per cubic centimeter. What dimensions would a cubic holo-memory 64-bit S-box have?
  5. The Random Oracle Model suffers from the annoying trait that truly random functions require exponential space. Nevertheless, in many applications one needs only a truly random simulated function. Define a Simulated Random Function (SRF) to have the following description: Sometimes one insists on a fourth condition: If all 4 conditions are satisfied, the SRF is called a SRP (Simulated Random Permutation). Describe Probabilistic Polynomial Time algorithms for simulating SRF's and SRP's assuming that there is a randomized algorithm C for picking elements from the co-domain Y with uniform probability. Assume C is guaranteed to succeed in O(1) running-time.
  6. Consider a discrete log hash function hK with p = 23 and the other parts of the key K = (p, q, α, β) to be specified later.
    1. What is the value of q?
    2. What are valid values for the primitive elements α (and hence also for β)?
    3. What are the official domain and co-domain for hK?
    4. Letting α = 5 and β = 10 calculate hK(57).
  7. (5 pts.) Consider the discrete log hash hK with K = (p, q, α, β) = (47,23,43,5). The following collision has been discovered:
    hK(23) = hK(99) = 43
    Use the known collision to compute Dlog43(5) mod 47, as well as Dlog5(43) mod 47.
  8. In class, the following lemma was quoted:
    Let G be a cyclic group with n elements and let g be a primitive element. Then an arbitrary element gi is primitive iff gcd(i, n) = 1.
    Your job is to prove the "gi is primitive ⇐ gcd(i, n) = 1" direction of the theorem. As a hint, here's the proof for the "gi is primitive ⇒ gcd(i, n) = 1" direction:
    Suppose gi is primitive. Then consider the set
    S = { gi, (gi)2, (gi)3, … , (gi)n-1 } = { gi, g2i, g3i … , g(n-1)i}
    By definition of primitivity, 1 is not contained in S. Furthermore, we claim that all the elements of S are distinct. Otherwise, there would be j < k such that gji = gki, so multiplying both sides by (gji)-1 one obtains g(k-j)i = 1, contradicting the fact that g(k-j)i ∈ S cannot equal 1. By Lagrange's theorem,
    if a ≡n b, then ga = gb
    so as the elements of S are all distinct, it must be the case the exponents are all distinct mod n and different from 0. So adding in 0 we get that the set of numbers
    T = {0, i mod n, (2i) mod n, (3i) mod n, … , (n-1)i mod n }
    are all distinct in Zn. Since the set has size n conclude that T = Zn. In other words, the function fi on Zn defined by multiplying by i modulo n:
    fi(m) = (im) mod n
    is a bijection. We saw that this is only the case if i is invertiblue modulo n which establishes the fact that gcd(i, n) = 1.
    HINT: A proof by contradiction is suggested. I.e., suppose that gcd(i, n) = 1 but that it were NOT the case that gi is primitive. Find an argument that results in g being non-primitive thus contradicting our assumptions.
  9. Problem 5.1, Stinson.
  10. Do the following two problems:
    1. Problem 5.3.b, Stinson
    2. Problem 5.8, Stinson

Homework 3: Number Theory, Public Key Cryptography

Problems

  1. (5 pts.) Find the last digit of the base-13 expansion of 7200.
  2. (15 pts.) [A strengthening of problem 5.9, Stinson.] Suppose that q is known to be an odd prime. Let p = 2q + 1, but suppose it is not known yet whether p is prime. Furthermore, suppose that an element α in Zp* is found such that Show that p must therefore be prime and that α is a primitive element in Zp*. HINT: The following fact might be useful, but you should prove it if you use it: in any group, if x is an element with the property that xm = 1 and xn = 1 then xgcd(m,n) = 1.
  3. Problem 5.14, Stinson
  4. Problem 5.15, Stinson
  5. (5 pts.) Suppose that n = pq with p, q different primes. Suppose also that n = 4,386,607 and φ(n) = 4,382,136. Find p, q.
  6. This problem had a couple of errors in it so has been changed. For posterity here's the original question. Now here's the corrected problem:

    Recall that in showing that hardness of the Discrete Log Problem implies collision resistance of the Discrete Log Hash Family we only showed how to solve Dlogx(y) mod p when both x and y are primitive. No method of solution was provided when y was non-primitive as allowed in the general Dlog problem. (For the case p = 2q + 1, with q prime, this implied failure to solve Dlog for about half of all cases). We give some pseudocode to fix this problem for primes of the type p = 2q + 1, with q prime: 

    INPUT:    x : primitive base in range [2,p-2]
          y : relatively prime to p in range [1,p-1]
          p : a prime of the form 2*q+1 with q prime

OUTPUT:   the number n such that x^n mod p = y

EXTERNAL: ISPRIMITIVE(x) : procedure testing if x is a primitive element

          FINDPRIMITIVE(p) : procedure returning a random primitive element
                 uniformly distributed in the primitives mod-p

          DLOG_FOR_PRIMITIVE(x,z,p) : discrete-log restricted to primitive z
          

DLOG( x, y, p ){
   if ISPRIMITIVE(y)
      return DLOG_FOR_PRIMITIVE(x,y,p)

   if y == 1
      return 0

   if y == p-1
      return (p-1)/2

   r = FINDPRIMITIVE(p)
   log_r = DLOG_FOR_PRIMITIVE(x,r,p)
   z = (y * r) mod p
   if !ISPRIMITIVE(z)
      return "FAIL"
   log_z = DLOG_FOR_PRIMITIVE(x,z,p)
   return (log_z - log_r) mod (p-1)
}
    1. Show that the algorithm is a valid Las-Vegas algorithm for the Discrete Logarithm and calculate that probability of returning "FAIL". HINT: As usual, the problem becomes a lot easier if you use index-calculus to analyze what going in on in the additive group Zp-1 rather than the multiplicative group Zp* .
    2. (EC 10 pts.) Generalize the algorithm to arbitrary primes p and compute the probability of failure. HINTS: The condition y == -1 generalizes to y is neither primitive nor a quadratic residue, but you'll need to make some further adjustments. For the failure probability estimate, you may assume the factorization of p-1. Here's a useful generalization of Euler's phi formula:
      Suppose the number N has prime factorization N = p1e1 ... pkek. Let S1 ⊆ Zp1, ... , Sk ⊆ Zpk be sets, and let T be the set of all numbers in the range [0, N-1] which satisfy the predicate
      x mod p1 ∈ S1 AND x mod p2 ∈ S2 AND ... AND x mod pk ∈ Sk
      Then |T| = |S1| p1e1-1 ⋅ |S2| p2e2-1 ⋅ ... ⋅ |Sn| pkek-1 .
  7. (EC 10 pts.) Generalize the matrix theorem in problem 2a of homework 1 to arbitrary modulii N. In other words, you should come up with a formula for the number of n × n matrices which are invertible modulo N which then readily gives a closed formula for this number. In particular, you should give a closed formula for the N a prime power. Prove your generalization.
  8. (5 pts) Carry out the Miller-Rabin primality test for n = 561 and test case a = 2. Record your calculations and explain what you are doing. You may use the following matlab function for modular exponentation.
  9. Suppose that for the RSA public key (N, e) an algorithm A exists for cryptanalyzing ciphertexts with probability p exists, with running time T seconds per ciphertext. In other words, for proportion p of the possible ciphertexts, the algorithm succeeds in obtaining the ciphertexts, and for all cihpertexts (whether succeeding or failing) the algorithm halts within time T. Describe how you can boost your algorithm to succeed within probability 1-ε for arbitrarily small ε. What is the resulting running time? HINT: Use the same trick as in Stinson Problem 5.14.

Homework 4: Probabilistic Encryption

Problems

  1. (15 pts.) Bob wants to send Alice a secret number. He converts the number to binary in the standard way, then sends it over to Alice using the Blum-Goldwasser public key cryptostystem (see slides #3-#6): 
    0000100100100101100100001011010
    Alice's private key is ( p, q ) = ( 983, 1019 ). What message did Bob send? You'll need to show work as follows: If you write a program you should print it out, if you do it in matlab you should print out your matlab session, or if you do it by hand include your calculations. HINTS: the answer is the name of a song. Again, I am providing you with a matlab function for modular exponentation. Other useful matlab functions are dec2bin / bin2dec for converting between decimal and binary, and xor.
  2. For this problem, you will show that multi-message security implies key security. In particular, suppose we take the following definition of insecurity of key under chosen plaintext attack:
    The cryptosystem (M, K, G, E, D) is NOT key-secure if there is a PPT key-cracking algorithm C with associated plaintexts m1, m2, ... , mL such that when C is given the plaintexts and corresponding ciphertexts, C returns the key k with non-negligible probability. More precisely:
    • the messages mi depend on the security parameter 1l and the number of messages L is polynomial in l
    • runnning time is as a function of l
    • non-negligibility is measured in terms of l
    • Prob( C( [m1, m2, ... , mL] , [Ek(m1), Ek(m2), ... , Ek(mL)] ) = k ) is non negligible
    Show that if such a cracking algorithm C exists, it can be used to create a multi-message distinguisher A and thus the cryptosystem would not be computationally secure.
  3. (15 pts) The definition of computational security (slide #7) is really a definition of security under chosen-plaintext attack. This is because we assume that there exist message sequences [mi,a] and [mi,b] whose encryptions can be distinguished with non-negligible success. Your problem is to find appropriate definitions for strengthenings and weakenings of these notions. Feel free to search the literature, or just be creative and try to come up with these on your own. If you do search the literature, please cite.
    1. define the notion of computational security under known ciphertext attack HINT: This weakest condition should imply semantic security so that one shouldn't learn even a single bit of information about plaintexts from their ciphertexts. In particular, your definition should probably include a phrase such as "for all PPT boolean functions on plaintexts" )
    2. define the notion of computational security under known plaintext attack (Hint the word "exist" above changes to a probabilistic condition on messages)
    3. adaptive chosen plaintext attack (HINT: assume you have oracle access to a black box B that on input ma, mb returns either Ek(ma) or Ek(mb) with a , b fixed for the entire run of the adversary algorithm, with the adversary not knowing a or b and in essense trying to guess correctly which choice of a versus b the black box is making. See also the next problem.)
  4. Suppose that some cryptosystem CS1 = (M, K, G, E, D) works on messages of size m. Suppose that we attempt to extend the cryptosystem to messages of size 2m by simply breaking each 2m-bit message up into two m-bit pieces, encrypting each part with the same key, and then sending the two parts over. Call the resulting cryptosystem CS2. Show that CS2 is insecure under adaptive chosen ciphertext attack. Use the following definition of security under adaptive chosen ciphertext attack:
    An a-b encryption oracle OE,ab is a black box that takes as input two equal sized plaintexts ma , mb and outputs either ciphertext Ek(ma) or ciphertext Ek(mb) with a or b fixed for all calls of the oracle during any given session, and the ciphertext being returned chosen at random from the set of all possible ciphertexts. A decryption oracle OD is a black box that takes as input any ciphertext c and outputs the plaintext Dk(c). The cryptosystem (M, K, G, E, D) is secure under adaptive chosen ciphertext attack if there is no PPT message distinguishing algorithm A calling on OE,ab and OD a polynomial of times such that OD is never called on any of the previous outputs of OE,ab, and such that A has non-negligible a-b advantage
    Pr[A(when OE,ab returns a-messages)=1] - Pr[A(when OE,ab returns b-messages)=1]
    HINTS: Your argument should still be valid when CS1 is secure under chosen ciphertext attack. The definition of chosen ciphertext attack pre-cludes you from decrypting what you just encrypted, but you are allowed to modify the received ciphertext. You should be able to demonstrate insecurity with just 1 call to OE,ab and 1 call to OD.
  5. Show that the following statement is false by finding a counterexample:
    CLAIM: Suppose (M, K, G, E, D) is a computationally secure stateful cryptosystem from messages of size l to messages of polynomial size P(l) (and defined on all bitstring keys and messages). Consider the function g defined by g(x) = Ex(0l). Then g is a PRG with expansion P(l) proving that the existence of computationally secure ciphers implies the existence of PRG's.
    HINT: Try to find a perfectly secure cryptostystem where the resulting bitstrings don't look random at all.
  6. Show that if P = NP, then no PRG can exist. Your proof should not rely on any other assumptions, such as assuming that if P = NP, then no one-way functions can exist, etc.
  7. (EC 10pts.) Let f : {0,1}k × {0,1}n → {0,1}n be any secure pseudo random permutation family. Define a new function family with larger domain g : {0,1}k × {0,1}2n → {0,1}2n by setting
    gk ( x || y ) = fk ( x ) || fk ( x ⊕ y )
    where x, y ∈ {0,1}n. Show that g is not a secure pseudo random permutation family.

Homework 5:

Problems

  1. Suppose that f : A → B is a one way function, and that g : B → C is an easily computed bijection. Show that the composition
    g • f : A → C
    is a one way function. Use this idea to construct a one-way permutation family from the discrete log one-way family. Recall that for valid index (p, g) the discrete log function has formula f(p, g)(x) = gx mod p, with domain Zp-1 and codomain Zp*. NOTE: You should assume that p is prime and g is primitive in Zp*.
  2. Show that the least significant bit (LSB) is not a hard core bit for the discrete-log function family (also called Discrete Exponential in the notes).
  3. (5 pts.) Which of the following messages is signable using the naïve Rabin signature scheme with public key n = 187?
    message1 = 3, message2 = 4, message3 = 5
    For each signable message, give the corresponsing signature.
  4. Suppose that we take as our security definition for digital signatures the following:
    Signature scheme (M, K, G, S, V) is considered to be secure if the existence of a successful PPT selective forger using a known public key attack would imply the existence of PPT algorithm for factoring products of equal-sized primes. (see digital signatures lecture, slide 6)
    Show that the naïve Rabin digital signature scheme is secure under this weaker than usual security definition. Note: Assume the forger knows somehow which messages are valid. (This isn't a major issue since 25% of all messages are valid).
  5. (5 pts.) Refer to digital signatures lecture, slides 14-18 for this problem.
    1. Assuming that there is no lower-limit on key-sizes, what is the smallest legal secret key (p, q) for the Cramer-Shoup digital signature scheme? (For this problem assume also that 2 is not a Sophie Germain prime)
    2. Now consider the associated public key (n, g, x, ê) and suppose that g = 4 while x = 9. What is n ? What is the smallest allowable value of ê ? HINT: ê depends on l -the security paramater. You should choose l to be the consistent with good exponent sizes for g.
  6. Show that finding an RSA-decryption exponent is directly reducible to an appropriate instance of the hidden kernel problem. This shows that if Quantum Computers are ever implemented then the RSA cryptosystem will be obsolete, even without factoring the modulus n. Hint: Let G = Z, H = Zn*. ψ should be chosen so that K is generated by the decryption exponent d with non-negligible probability.
  7. Consider the quantum key exchange protocol described in lecture. How many random bits should Alice prepare in order to be sure to probabability 1-ε that nobody is eavesdropping? Explain.
  8. For this problem consider the reduction from FIND-ORDER to HIDDEN-KERNEL in the quantum cryptography lecture, slide no. 7.
    1. (5 pts.) Show that even if you get a generated of the kernel K different from ord(a) you can still recover ord(a).
    2. (EC 5 pts.) The specification of HIDDEN-KERNEL only requires that the quantum algorithm return a finite set of generators for K. Show that even under this weak condition, on can still recover ord(a).
  9. (20 pts.) A guided walk to proving that Simple Fiat-Shamir (SFS) is a Zero Knowledge Interactive Proof System.
    1. Prove that SFS is complete. In particular, show that when honest P and V interact, V accepts with probability 1.
    2. Next, the goal is to show that SFS is sound. Show something a little more modest: the probability that P* will fool V is not significantly greater than 1/2. I suggest using a proof by contradiction with the following outline (but if you have another good proof, by all means present it!)
      1. Suppose for contradiction that the probability that P* succeeds to fool V is significantly better than 1/2.
      2. Let p0 be the probability that P* succeeds when V chooses b = 0, and let p1 be the probability that P* succeeds when V chooses b = 1. Show that the assumption in (I) would imply that p0 + p1 is significantly greater than 1.
      3. Using (II) show that the probability that P* is able to choose s (in the first round) and t (in the third round) to succeed regardless of V's choice is significantly greater than 0.
      4. Using (III) and some algebraic manipulation, prove that P* is able to find a square root of y with probability significantly greater than 0.
      5. Using (IV) show that P* can be used to create an algorithm for factoring n with non-negligible success probability, thus proving computational security.
    3. How should you modify SFS so that it will be sound (probability that P* succeeds is at most 1/3) ?
    4. Now show that SFS is Zero-Knowledge. We give an algorithm for Simon: 
      INPUT:    n, y
EXTERNAL: black box for V*
OUTPUT:   a transcript (s, b, t)

while( true ){
   b' = random guess from {0, 1}
   r  = random guess from [0, n-1] relatively prime to n
   s = r^2 / y^(b') mod n
   call V* for second round and let b be V*'s returned bit
   if (b == b') return (s,b,r)
}
      Show the algorithm is a Las-Vegas algorithm and that if the while loop is allowed to run k times, the probability of failure (not returning any value) is 1/2k . Show that for both Simon's S-V* simulations, as well as Villain's P-V* sessions, transcripts are of the form
      ( r2 / yb mod n, b, r )
      Furthermore, show that the probabilities of obtaining any particular transcript are within a factor of (1 - 1/2k) from each other, so negligibly different. This would show that the protocol is zero knowledge since V* would not be able to learn more information talking to P than S would without talking to P.
Last modified: Mon Nov 22 02:01:06 2004