Home

Schedule & Slides

Problem Sets

Problem Set 4: Multi-language Programming and RSA Encryption
[Due 3/7 at noon]

Updated 3/5

In this this assignment you will implement the RSA encryption algorithm discussed in class.

Work on this project with a partner. Email me if you will be working with someone different than in problem set 3.

All code you write must be well documented, and tested as appropriate. NUnit tests are required for parts 1 and 2.

Turn in your solution by email. Please send me all source, project and solution files needed to compile your project.

Overview

In class we discussed the number theory behind RSA, however there are still many interesting implementation issues that we did not touch. In particular, finding the correct mapping from string or binary data to integers is both non-trivial and essential. In this problem set you will be implementing RSA public key cryptography over an existing large integer library and designing a scheme to represent real data as library integers.

RSA, like most public key cryptosystems, requires performing arithmetic on large integers---512 or more bits in our case. As standard integers are only 32 bits, we will need to use an alternative data type for RSA. Implementing large integer arithmetic is notoriously tricky, and the .Net Base Class Library does not support it. Fortunately, Microsoft has ported portions of the Java Library to .Net and we will use java.math.BigInteger.

The Java libraries are not included with Visual Studio Express; you will need to install them. Go to The Visual J# download page. Navigate to "Visual J# Redistributable Packages", and then to "Download the Visual J# 2.0 Redistributable Package-Second Edition (x86)." You can then download vjredis.exe. Run the installer to register the library components. You should now be able to add a reference to vsjlib from your projects, and use the library java.math.

See Sun's documentation for more information about BigIntegers. There are some minor incompatibilities between the Java and .Net implementations. One difference is that most .Net methods take unsigned bytes, type byte, but java methods tend to work over signed bytes, type sbyte. You can cast between these types, and can cast an array of sbytes to an array of bytes by casting through Array. That is,

Note that this changes only the static type of the array; the dynamic type is still sbyte[]. In some cases you may need to actually copy sbyte arrays element by element into byte arrays.

You do not need to implement key generation. I have provided files with sample keys: Alice.key, Bob.key, Charlie.key, Dave.key, and Elif.key. The key files are formatted as follows:

The name field is intended to represent the principal, or user, who owns the key. You do not need to do anything with this field, but it might be useful in Part 2. The n, e, and d fields contain integers expressed as strings of the digits 0-9 and have the meanings indicated.

Additionally, you may use the provided Java program, KeyMaker.java to produce key pairs. Compile with javac KeyMaker.java, and run with java KeyMaker name. The KeyMaker prints a key file to standard out. This is a Java program because the .Net implementation of BigInteger.isProbablePrime is very slow.

Part 1: The RSA algorithms

Following February 27th's lecture notes write and test (using NUnit) a pair of functions,

that implement the encrypt and decrypt operations of RSA. Ensure that your test cases cover all interesting corner cases and demonstrate that decryption inverts encryption. You may assume that msg is less than the RSA modulus n.

Part 2: Working with Data

Design, test, and document a command line or Gui interface for encrypting and decrypting data. You may choose whether to support input data as strings, text files, binary files or any combination of the above. The only requirements for this part are:

• Your program must be able to read and use key files (see above).
• Your program must provide both encryption and decryption functionality.
• Your program must support inputs of length greater than 64 bytes (512 bits).
• You must include a ReadMe file explaining how to use your program.
• The ReadMe must include a walk-through that explains exactly what steps are necessary to run a demo of your program.

Hint: This part is harder than it looks. Before you start coding, think carefully about how to convert data (in whatever format) to a BigInteger.

Bonus: Primalility Testing

As noted above, Microsoft's implementation of isProbablePrime is highly inefficient. Implement a primality tester for BigIntegers. If you do not use Rabin-Miller, please provide a concise description (with appropriate citations) of your approach.