Assignment: Assignment 8 - Implementing RSA

Posted: 31 October 2019

Deadline: 2019-11-23 16:00

Introduction

This time, you must create a program, and use it to answer a few questions along the way.

The answers must be submitted in Blackboard as answers to test/assignment 8.

We will in this assignment take a look at implementing RSA in JAVA, including generating keys, encryption and decryption.

To complete this part of the assignment, you must download the rsa-assignment.zip and unpack.

The Character Conversion code from assignment 2 you can reuse for this assignment!

As numbers for encryption can be very large, you will be working with the BigInteger class from java in this project.

Tests have been prepared, and should use these, i.e. do test driven development. In order to run the tests, you must do the following

Use the Gradle wrapper in the project (gradlew for Linux/Mac, gradlew.sh for Windows) and run:

./gradlew test

You can find the test report in the build/reports/tests/test directory.

All tests will at the beginning fail, as the code is not implemented, but as you progress in the assignment, they should pass. The tests are written in the Spock test framework, but knowledge of this is not a requirement.

Alphabet

Here is the following alphabet conversion:

  • 0-9 should return their value 0→0, 5→5, 9→9

  • a should map to 10, b to 11, c to 12 etc. up to z→35

  • Space should map to 36

We will use only 37 characters for our messages (26 lower case letters, 10 numbers and the space). If you find other characters in the plain text message (input message) such as punctuation, white space, etc., simply treat the characters as spaces and assign them the value of 36.

Character Conversion

Before you can implement RSA, you must encode an input message as a number. We will use the following scheme to convert plaintext (input) messages to numbers:

  1. Convert any extra characters to spaces as specified above (and your already implemented code).

  2. Group the plaintext into sets of five characters per group. If the last grouping does not have exactly five characters, then append some space to the end of the plaintext message to fill out the last grouping. Each group must have five characters.

  3. Convert each group into a separate number: If the grouping is [c4,c3,c2,c1,c0] then the number is

\[\sum_{i=0}^{4}{c_i \cdot 37^i}\]

Here is an example. Assume our plaintext grouping is [hi s7]. First we translate the characters into numbers:

c4 = ’h’ = 17
c3 = ’i’ = 18
c2 = ’ ’ = 36
c1 = ’s’ = 28
c0 = ’7’ = 7

Then we compute the plaintext number:

17 · 374 + 18 · 373 + 36 · 372 + 28 · 371 + 7 = 32.822.818

A decoding operation should be performed in the same way except that the process is reversed. A number is converted to its character grouping by using mod and div.

In the file AlphabetConversion.java, you find 2 methods you should implement. Use the description above, CharacterConversion class, the java doc, and study the test file (AlphabetConversionSpec.groovy).

Recommended order of implementation is:

  1. stringToNumber

  2. numberToString

Key Generation

In order to generate the public and private key, e must be chosen relatively prime to z, and d must satisfy e · d mod z = 1. For both of these criterias, the extended euclidean algorithm can be used:

rsa euclidean

The return value provides the following: r = gcd(a, b) and s · a + t · b = r Implement the algorithm in the NumberHelpers.java class.

Encryption and decryption

In order to do encryption and decryption, you should implement fast modular exponentiation. Doing the full calculation before using mod would yield very large numbers and is not feasible. The algorithm is in pseudo code below, and the file is NumberHelpers.java.

rsa mod expo

You are now ready to implement encryption and decryption, using the tools you have developed. Implement the rsa encryption and decryption in the Rsa.java file. Remember the encryption method must pad the input with spaces, if the length is not a multiple of 5.

Questions for Blackboard

Once you have the code implemented, the tests in AlphabetConversionSpec, NumberHelperSpec and RSASpec should pass.

It should be easy to get the AssignmentSpec passing too, with the results for blackboard. The answers are also printed to the console.

(You can use your program to find the correct results using the AssignmentSpec.groovy tests.)

To get the final test to pass - you need to update the test and replace <The answer should replace this message> with the correct answer - the same answer that you should turn into blackboard.

Happy coding