Description
In this assignment you are going to develop an asymmetric encryption tool in C, from scratch.
The purpose of this assignment, now that you are familiar with implementing simple ciphers as
well as using real encryption toolkits, is to provide you the opportunity to get familiar with the
internals of a popular encryption scheme, namely RSA. The tool will provide RSA key-pair
generation, encryption and decryption.
More specifically, you are going to use the basic theory behind RSA and asymmetric encryption
in order to develop the basics that compose a simple RSA toolkit, such as prime number
generation and so on.
Task A
[Key Derivation Function (KDF)]
In this task you have to implement an RSA key-pair generation algorithm. In order to do so, you
will first need to study RSA’s internals: https://en.wikipedia.org/wiki/RSA_(cryptosystem) .
Moreover, you will need to develop a function that implements the Sieve Of Eratosthenes:
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes . This material serves just as a reference
point. You can also utilize any other source you wish. The key generation process will be the
following:
1. Generate a pool of primes using the Sieve Of Eratosthenes. For your convenience, the
sieve’s limit is defined in the provided file, rsa.h.
2. Pick two random primes from the pool. Lets name them p and q.
3. Compute n where n = p * q.
4. Calculate fi(n) where fi(n) = (p – 1) * (q – 1). This is Euler’s totient function, as described
in the original RSA paper “A Method for Obtaining Digital Signatures and Public-Key
Cryptosystems”. You may find out that other implementations use different totient
functions. However, for this implementation, we are going to use Euler’s.
5. Choose a prime e where (e % fi(n) != 0) AND (gcd(e, fi(n)) == 1) where gcd() is the
Greatest Common Denominator.
6. Choose d where d is the modular inverse of (e,fi(n)).
7. The public key consists of n and d, in this order.
8. The private key consists of n and e, in this order.
Hints:
● Use size_t when declaring the variables described above
● The key file should just contain the two numbers, (e.g. n and d) so it just contains two
size_t variables
Task B
[Data Encryption]
Develop a function that provides RSA encryption functionality, using the keys generated in the
previous step. This function reads the data of an input file and encrypts them using one of the
generated keys. Then, it stores the ciphertext to an output file. For each character (1-byte) of
the plaintext, the tool generates an 8-byte ciphertext (size_t on 64-bit machines). For example, if
the plaintext is “hello” then the 5 bytes (5 chars) of the plaintext will produce 40-bytes (5 *
sizeof(size_t)) of ciphertext.
Task C
[Data Decryption]
Implement a function that reads a ciphertext from an input file and performs RSA decryption
using the appropriate one of the two keys, depending on which one was used for the ciphertext
encryption. The keys will be generated using the KDF described in Task A. When the decryption
is over, the function stores the plaintext in an appropriate output file.
IMPORTANT: In order to successfully decrypt the data, you have to use the appropriate key. If
the ciphertext is encrypted using the public key, you have to use the private key in order to
decrypt the data and vice versa. Also, every 8-bytes of the ciphertext produce a 1-byte plaintext.
For example, a 40-byte ciphertext will produce a 5-byte plaintext.
Task D
[Using the tool]
Once you have implemented all the above functionality for your tool, use it to do the following
operations, on the txt files provided for validation and testing purposes:
1. Encrypt the file “hpy414_encryptme_pub.txt” using the hpy414_public.key. Name the
output as TUC_encrypted_pub.txt”
2. Decrypt the file “hpy414_decryptme_pub.txt” using the hpy414_public.key. Name the
output as TUC_decrypted_pub.txt.
3. Encrypt the file “hpy414_encryptme_priv.txt” using the hpy414_private.key. Name the
output as TUC_encrypted_priv.txt.
4. Decrypt the file “hpy414_decryptme_priv.txt” using the hpy414_priv.key. Name the
output as TUC_decrypted_priv.txt.
Hints:
● Remember that the key files contain just two size_t values. The first 8 bytes represent n
while the next 8 bytes represent e or d, depending on the key.
Tool Specifications
In order to assist you in the development of this tool, we provide a basic skeleton of the tool. We
also provide some helper functions, used to print the plaintext as a string and the bytes of the
ciphertext and keys in a human readable form. The tool will receive the required arguments from
the command line upon execution as such:
Options:
-i path Path to input file
-o path Path to output file
-k path Path to key file
-g Perform RSA key-pair generation)
-d Decrypt input and store results to output
-e Encrypt input and store results to output
-h This help message
The arguments “i”, “o” and “k” are always required when using “e” or “d”
Using -i and a path the user specifies the path to the input file.
Using -o and a path the user specifies the path to the output file.
Using -k and a path the user specifies the path to the key file.
Using -g the tool generates a public and a private key and stores them to the public.key and
private.key files respectively.
Using -d the user specifies that the tool should read the ciphertext from the input file, decrypt it
and then store the plaintext to the output file.
Using -e the user specifies that the tool should read the plaintext from the input file, encrypt it
and store the ciphertext to the output file.
Example:
./assign_3 -g
The tool will generate a public and a private key and store them in the files public.key and
private.key respectively.
Example:
./assign_3 -i plaintext.txt -o ciphertext.txt -k public.key -e
The tool will retrieve the public key from the file public.key and use it to encrypt the data found in
“plaintext.txt” and then store the ciphertext to “ciphertext.txt”
IMPORTANT
Even if you chose to redesign your tool from scratch, and not use the provided skeleton, you
have to support the command line options described above.
Important notes
1. You need to submit all the source code of your tool, a README file, a Makefile, and all
the files you used or generated in Task D. The README file should briefly describe your
tool. You should place all these files in a folder named _assign3 and then
compress it as a .zip file. For example, if your login is 2020123456 the folder should be
named 2020123456_assign3 you should commit 2020123456_assign3.zip.
2. Study carefully the operation of RSA and the Sieve Of Eratosthenes.
3. Do not copy-paste code from online examples, we will know 😉
4. The tool’s skeleton provided with this assignment is just an example. Feel free to define
your own functions or change the signatures of the given functions. You can even
re-design it from scratch. However, the switches defined above have to be kept the
same.
5. The ciphertext and the keys are just bytes. That means that they do not terminate with
\0. Don’t try to print them as strings, use the provided functions, if needed.
6. Use the tab “Συζήτηση” in courses for questions.
7. Questions will be answered on Tuesday and Friday.
