CS 341: Cryptography

RSA Party

The second attempt at a party will happen from 8:30-9:40AM Wednesday, February 2. Code and results will be due by 11:59PM the same day.

Each person or team should come to CMC 306 equipped with:

  1. A collection of at least 20 ASCII text messages. Keep these secret.
  2. A program written by the person or team in Python, C, C++, Java, or Perl, named rsa.py (or .c, .cpp, .java, .pl), with usage as described below.
  3. Any other code (again written by the person or team in question) that seems like it might be handy if, hypothetically, you have the opportunity to try to spy on other people's communications during the party.

Message representations

For our purposes, messages will begin life as ASCII text, which is then transformed into "encoded" text. The RSA algorithm will be used to encrypt, decrypt, sign, etc. encoded text.

The ASCII text will be encoded in five-character blocks, each of which will be transformed into a 12-digit upper-case hexadecimal number. The first two digits of the encoded block will be 00. Then each character in the five-character ASCII block will be represented as the two-digit hexadecimal representation of its ASCII value. For example, "moose" will be encoded to "006D6F6F7365". If the last block in the message has fewer than five characters, its encoded version will start with enough 00's to fill the encoding to 12 hexadecimal digits. For example, if the last block is "r.", its encoding will be "00000000722E". To make it easier to read the encoded text, the encoding will be separated into 60-digit lines.

For example, the ASCII text:

The moose and the goat plotted the downfall of the tapir.

will be encoded as:

00546865206D006F6F73652000616E64207400686520676F00617420706C 006F7474656400207468652000646F776E6600616C6C206F006620746865 00207461706900000000722E

Once you have encoded text, you'll need to separate it into blocks for encryption or decryption. We are going to use 48-bit n's, and we want each block to be an integer smaller than n. By encrypting the 12-hexadecimal-digit blocks described above, we achieve this goal with room to spare (since the encoded blocks represent integers no more than 40 bits long). For example, the first M to be encrypted will be the integer whose hexadecimal representation is 00546865206D. This number is 39 bits long in binary, since the leading hexadecimal 5 has a leading 0 in its binary form 0101, and is thus plenty small enough to be encrypted using a public key (e, n) for which n is a 48-bit number.

Really, all we're doing here is treating ASCII text like a big long bit string, which we then break into 40-bit (i.e. 5-character) chunks for encryption. The folderol about "encoding" just gives us input and output routines and a uniform way of writing long bit strings (encrypted or not) to make it easy for us to deliver these long binary numbers via e-mail.

The program

Your program should support, at minimum, the following command-line options. I have written them here as Python command lines, but the C/C++, Java, or Perl variants should be straight-forward.

python rsa.py --keygen Input: none Output: three lines of text to standard output. The first line will be "n: " followed by a 48-bit integer expressed in upper-case hexadecimal. The second and third lines will start with "e: " and "d: " respectively, with upper-case hexadecimal representations of the encryption and decryption integers following. (Your integers may have leading 0's or not, as you prefer.) The value of n should be at least 2^46 and strictly less than 2^48 (i.e. either 47 or 48 bits when leading 0's are removed). You may have additional output (e.g. lines for p and q) if that helps you debug or do anything else of value. python rsa.py --encrypt e n Input: e and n are expressed as upper-case hexadecimal integers (with or without leading zeros). The message to be encrypted will be delivered via standard input, and may be assumed to be encoded text as described above. Output: The encrypted message, expressed as encoded text, sent to standard output. python rsa.py --decrypt d n Input and output are the same as for --encrypt. In fact, the --decrypt syntax is just a convenience for clarity, since it will perform precisely the same operation as --encrypt. python rsa.py --encode [message] Input: The ASCII message to be transformed into encoded text is either provided as command-line argument, or as text via standard input if the message argument is absent. (Don't forget quotation marks if you type your message as a command-line argument, so the shell will interpret the message as a single argument rather than one argument per word.) Output: The encoded text, to standard output. python rsa.py --decode Input: Encoded text delivered via standard input. Output: The corresponding ASCII text, to standard output.

Example results

Here are results from my implementation. I generated these items and stored them in like this:

python rsa.py --keygen echo "The moose and the goat plotted the downfall of the tapir." > message.txt python rsa.py --encode < message.txt > encoded.txt python rsa.py --encrypt 000000000017 AA93FC019C7F < encoded.txt > encrypted.txt python rsa.py --decrypt 4674C605851B AA93FC019C7F < encrypted.txt > decrypted.txt python rsa.py --decode < decrypted.txt > decoded.txt