### 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 `sbyte`

s to an
array of `byte`

s by casting through `Array`

.
That is,

` myBytes = (byte[])(Array)(mySBytes); `

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:

` name = ` name` n = ` modulus` e = ` encryption exponent` d = ` decryption exponent |

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,

` BigInteger EncryptBigInt(BigInteger msg, ...) ` , |

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
`BigInteger`

s. If you do not use Rabin-Miller, please provide a
concise description (with appropriate citations) of your approach.