Homework #2

CMPS 122, Winter 2005

Assigned: January 20th
Due: Thursday, January 27th at noon

Please read the homework guidelines for information about how to work on the assignment and how to submit it.

  1. Decrypt this binary file (hw2-1.crypt). It was encrypted using AES with a 128-bit key. To make this problem tractable in a reasonable amount of time, the key has only 24 bits that change, followed by 104 bits that are all set to 0. For this problem, you need to write the code that decodes the message, which is plain ASCII text. A compressed tar file with AES encryption and decryption code along with examples of how to use it is available online. The file was encrypted with this AES code (in CBC mode, with IV=0), so you should probably use this source code to try and break it.
    You may use any programming language you like to do this problem, but it's likely that only C or C++ will be fast enough to complete the assignment (this is brute force decryption...). For this assignment, please turn in any code you wrote (and you must write the code on your own) along with the key and decrypted message.
    HINT: you don't need to decode the entire message to determine whether it's a valid ASCII & English message. How can you quickly (in the first few 128-bit blocks) tell whether an possible decryption is not valid?
  2. The Rijndael algorithm uses a byte substitution table that comes from a formula applied to GF(28). Is it necessary to use that formula, or would any substitution table work? What restrictions are there on the form of the table?
  3. It's possible to write an encryption / decryption system that uses "random" number generators. For this problem, you'll be writing code that encrypts / decrypts using the Unix random number generators. The key size is 32 bits, and the block size is 32 bits. Each ciphertext block is calculated by XORing the plaintext block with the value returned by the random number generator.
    1. Write code (in C) that encrypts and decrypts data using the Unix random() and srandom() functions. The key should be passed to srandom(), and successive values obtained from random() should be XORed with the plaintext to generate the ciphertext. You should write them into a single program called randcrypt, which should be called as follows:
      randcrypt E|D key < input > output
      In other words, randcrypt E 6789abcd < plaintext > ciphertext would encrypt plaintext using the (hex) key 0x6789abcd and put the resulting ciphertext into ciphertext. To decrypt ciphertext, you would use randcrypt D 6789abcd < ciphertext > decryptedtext. You can test your code by deciphering this message, which is encrypted using the key 0x12345678.
      HINT: read the man pages for random() and srandom() functions (they're in section 3).
    2. Why is it not absolutely necessary to use CBC mode for this encryption algorithm?
    3. How do encryption and decryption differ from one another?
    4. How could you adapt this technique to use a 128-bit key? Don't implement the code—just describe what you might do.
  4. Problem 9.3 in Stallings (page 280).
Last updated 20 Jan 2005 by Ethan L. Miller (elm at ucsc d0t edu)