Background

Diffie-Hellman key exchange is a protocol in which two users can securely exchange a secret key over a public network. You will use OpenSSL to perform a Diffie-Hellman key exchange with the lecturer.

RSA is a widely used public key cryptography, where once a key pair is generated, a message is encrypted with:

C = M^e mod n

and decrypted with:

M = C^d mod n

While the public value e can be small, for security d should be large. This presents a performance problem for decryption as raising a large number C to a large power d takes a long time with a computer. Therefore a performance optimization commonly used in implementations of RSA is split the modular exponentation of decryption into two steps where the exponents are much smaller than d. This performance optimization does not (theoretically) reduce the security of the scheme. To use this performance optimization, when generating a key pair several additional values are also generated and stored in the private key. The private key values are listed on slide 18 of the Public Key Cryptography lecture slides. The steps for decrypting using the performance optimization of RSA are listed on slide 6 of the RSA Acoustic Cryptanalysis lecture slides. (Also see the Hints in the steps below)

You will use OpenSSL to generate your own RSA key pair, and solve a small RSA problem by hand (or with a calculator/computer) to illustrate the performance optimization.

Tasks

This homework is assessed. You need to use OpenSSL, as well as manual calculations, to perform the following steps. I will test using OpenSSL version 1.0.1 14 Mar 2012. In files/text below, replace ID with your actual student ID.

The following steps are performed with OpenSSL. Follow my examples for using OpenSSL with RSA, Diffie-Hellman and AES encryption. (Note you don't have to perform all the steps on the examples, only those steps as required by the tasks below).

1. Generate your own RSA 4096-bit key pair, saving as ID-rsa-private.pem. Use the default public exponent (65537). View the values, comparing them to the private key values on slide 18 of the lecture notes. Save your key information (you will need it in later homeworks - losing it will result in a penalty).
2. Extract your RSA public key and submit it on Moodle as the file ID-rsa-public.pem. Make sure your private key information is NOT included or released to anyone else.
3. Generate Diffie-Hellman global public parameters, saving them in the file ID-dh-param.pem. View and understand the values.
4. Generate your Diffie-Hellman private key, saving in the file ID-dh-private.pem. View and understand the values. Save the private key for later use - do not lose it.
5. Extract your Diffie-Hellman public key, saving in the file ID-dh-public.pem. View and understand the values.
6. Upload your Diffie-Hellman public key to your private web directory on the ICT server. Specifically, on ict.siit.tu.ac.th you must have a file: ~/public_html/private/ID-dh-public.pem
7. After several minutes, the ICT server will automatically copy your DH public key and create the public key for Steve named: ~/public_html/private/ID-dh-steve.pem . If you have made a mistake in the file you uploaded you may instead see a file called ID-dh-error.txt which may contain hints on what you did wrong - try again. If you delete the file ID-dh-steve.pem, then a new one will automatically be created.
8. Use Steve's public key to create a shared secret, e.g. ID-dh-secret.bin
9. Extract the first 256 bits from the secret file to be used for an AES-256 key by using xxd and cut as follows: xxd -l 32 -g 32 -c 32 ID-dh-secret.bin | cut -d " " -f 2 . You will use the 256-bit key to decrypt the next file.
10. An encrypted file called ~/public_html/private/ID-manual-rsa.bin is automatically created at the same time as ID-dh-steve.pem. Decrypt this file using AES-256-CBC and the secret key from the previous step. The IV is all 0's (that is, 32 hex 0's).

The decrypted file, e.g. ID-manual-rsa.txt, contains 4 fields: your ID, someone's RSA public key (e and n) and the ciphertext (c) value created using that persons public key. Using the values of e, n and c in the file, do the following manually (e.g. with paper, calculator, software; not using OpenSSL):

1. Give the persons public key, find their private key. Specifically, find all the values that are stored in a RSA private key when using the performance optimization. Write the values in the file ID-manual-private.txt (the file is already in your directory - you just need to edit and add the values).
2. Given that you have found their private key and given the ciphertext, find the corresponding plaintext. Use the performance optimization technique to find the plaintext. Write the values used in the file ID-manual-decrypt.txt (the file is already in your directory - you just need to edit and add the values).
3. Submit the two files, ID-manual-private.txt and ID-manual-decrypt.txt, on Moodle.

Important hints when using RSA performance optimization: when you find p and q, make sure p is greater than q. Also if you use bc or another calculator to calculate a mod, then it may return a negative number. But modular arithmetic used in RSA does not use negative numbers. Therefore if you get a negative number, then convert it to positive by adding the modulus. For example, in mod 10, -3 would be converted to -3 + 10 = 7.

You are done!

File Formats and Names

Make sure you use the exact file names as given in the instructions (replacing ID with your actual student ID). Marking of the submissions will be automatic, and the file names must be as expected otherwise your submissions will be ignored. Do not use uppercase in file names.

For the two "manual" text files submitted on Moodle, make sure they only have lines of the format parameter=value. There should be no spaces and no other lines added to the provided files.

Submission

Three files must be submitted on Moodle:

• ID-rsa-public.pem
• ID-manual-private.txt
• ID-manual-decrypt.txt

Do not submit any other files and do no zip/archive the files.

Also, you must save (and keep secret) the following files (but do NOT submit them):

• ID-rsa-private.pem
• ID-dh-private.pem

Losing these files will result in penalty in later homeworks.

You should also save all other files you created just in case you made a mistake.

Software

OpenSSL is available on several operating systems. It is usually installed by default on Linux (e.g. Ubuntu) and Mac OSX. I suggest you use either of these (as opposed to Windows) since I also include examples of command line utilities that will be used in addition to OpenSSL. If you don't have Ubuntu or OSX on your own computer you can try the following:

1. Use the ICT server, that is SSH (using Putty in Windows or ssh on the command line in OSX) into ict.siit.tu.ac.th. Since some tasks require you to put files on the ICT server this is probably the easiest option.
2. Use the lab computers at Bangkadi, especially the Network Lab.
3. Install virtnet and use a virtual node.

For the manual tasks (not using OpenSSL) you can still use software. On Linux/OSX I suggest using bc as the calculator. Also to factor large numbers you can use the command factor on the command line.

Feedback

Grades can be seen below. 2 marks for submitting RSA public key, 4 marks for finding the correct values of the RSA private key and 4 marks for finding the correct values of the RSA message. Several people made a typo or small mistake in submissions leading to 1 mark penalty. Others gave wrong answers (especially for qinv, h, d and m). You should have checked the message M that you found be encrypting it with the provided e and n; if it gave the provided C then you confirm that your M is correct. So those that submitted a wrong M received a penalty of 3 marks.

For those that didn't obtain full marks of 10, you can see my comments in the files named ID-comments-private.txt and ID-comments-decrypt.txt at the same location as your DH files:

ict.siit.tu.ac.th/~uID/private/

Make sure you keep your private keys. Especially for RSA, as a subsequent homework will require it.