RSA Public-Key Encryption and Signature Lab - IT/Computer Science Assignment Help

Assignment Task:

Task:

Introduction
RSA (RivestShamirAdleman) is one of the first public-key cryptosystems and is widely used for secure communication. The RSA algorithm first generates two large random prime numbers, and then use them to generate public and private key pairs, which can be used to do encryption, decryption, digital signature generation, and digital signature verification. The RSA algorithm is built upon number theories, and it can be quite easily implemented with the support of libraries.
The learning objective of this lab is for students to gain hands-on experiences on the RSA algorithm.

From lectures, students should have learned the theoretic part of the RSA algorithm, so they know math- ematically how to generate public/private keys and how to perform encryption/decryption and signature generation/verification. This lab enhances student’s understanding of RSA by requiring them to go through every essential step of the RSA algorithm on actual numbers, so they can apply the theories learned from the class. Essentially, students will be implementing the RSA algorithm using the C program language. The lab covers the following security-related topics:
• Public-key cryptography
• The RSA algorithm and key generation
• Big number calculation
• Encryption and Decryption using RSA
• Digital signature
• X.509 certificate
Lab environment. This lab has been tested on our pre-built Ubuntu 12.04 VM and Ubuntu 16.04 VM, both of which can be downloaded from the SEED website. This lab requires the openssl library, which is already installed on the Ubuntu 16.04, but not on the Ubuntu 12.04 VM. If you use Ubuntu 12.04, please run the following two commands to install openssl:
$ sudo apt-get update $ sudo apt-get install libssl-dev

2 Background

The RSA algorithm involves computations on large numbers. These computations cannot be directly con- ducted using simple arithmetic operators in programs, because those operators can only operate on primitive

data types, such as 32-bit integer and 64-bit long integer types. The numbers involved in the RSA algorithms are typically more than 512 bits long. For example, to multiple two 32-bit integer numbers a and b, we just need to use a*b in our program. However, if they are big numbers, we cannot do that any more; instead, we need to use an algorithm (i.e., a function) to compute their products.
There are several libraries that can perform arithmetic operations on integers of arbitrary size. In this lab, we will use the Big Number library provided by openssl. To use this library, we will define each big number as a BIGNUM type, and then use the APIs provided by the library for various operations, such as addition, multiplication, exponentiation, modular operations, etc.

2.1 BIGNUM APIs
All the big number APIs can be found from https://linux.die.net/man/3/bn. In the following, we describe some of the APIs that are needed for this lab.

• Some of the library functions requires temporary variables. Since dynamic memory allocation to cre- ate BIGNUMs is quite expensive when used in conjunction with repeated subroutine calls, a BN CTX structure is created to holds BIGNUM temporary variables used by library functions. We need to create such a structure, and pass it to the functions that requires it.
BN_CTX *ctx = BN_CTX_new()
• Initialize a BIGNUM variable
BIGNUM *a = BN_new()
• There are a number of ways to assign a value to a BIGNUM variable.
// Assign a value from a decimal number string
BN_dec2bn(&a, "12345678901112231223");
// Assign a value from a hex number string
BN_hex2bn(&a, "2A3B4C55FF77889AED3F");
// Generate a random number of 128 bits
BN_rand(a, 128, 0, 0);
// Generate a random prime number of 128 bits
BN_generate_prime_ex(a, 128, 1, NULL, NULL, NULL);
• Print out a big number.
void printBN(char *msg, BIGNUM * a)
{
// Convert the BIGNUM to number string
char * number_str = BN_bn2dec(a);
// Print out the number string
printf("%s %s\n", msg, number_str);
// Free the dynamically allocated memory
OPENSSL_free(number_str);
}

SEED Labs – RSA Public-Key Encryption and Signature Lab 3

• Compute res = a − b and res = a + b:
BN_sub(res, a, b);
BN_add(res, a, b);
• Compute res = a ∗ b. It should be noted that a BN CTX structure is need in this API.
BN_mul(res, a, b, ctx)
• Compute res = a ∗ b mod n:
BN_mod_mul(res, a, b, n, ctx)
• Compute res = a
c mod n:
BN_mod_exp(res, a, c, n, ctx)
• Compute modular inverse, i.e., given a, find b, such that a ∗ b mod n = 1. The value b is called the inverse of a, with respect to modular n. BN_mod_inverse(b, a, n, ctx);

2.2 A Complete Example
We show a complete example in the following. In this example, we initialize three BIGNUM variables, a, b, and n; we then compute a ∗ b and (a b mod n).

/* bn_sample.c */
#include <stdio.h>
#include <openssl/bn.h>
#define NBITS 256
void printBN(char *msg, BIGNUM * a)
{
/* Use BN_bn2hex(a) for hex string
* Use BN_bn2dec(a) for decimal string */
char * number_str = BN_bn2hex(a);
printf("%s %s\n", msg, number_str);
OPENSSL_free(number_str);
}
int main ()
{
BN_CTX *ctx = BN_CTX_new();
BIGNUM *a = BN_new();
BIGNUM *b = BN_new();
BIGNUM *n = BN_new();
BIGNUM *res = BN_new();

// Initialize a, b, n
BN_generate_prime_ex(a, NBITS, 1, NULL, NULL, NULL);
BN_dec2bn(&b, "273489463796838501848592769467194369268");
BN_rand(n, NBITS, 0, 0);
// res = a*b
BN_mul(res, a, b, ctx);
printBN("a * b = ", res);
// res = aˆb mod n
BN_mod_exp(res, a, b, n, ctx);
printBN("aˆc mod n = ", res);
return 0;
}

Compilation. We can use the following command to compile bn sample.c (the character after - is the letter `, not the number 1; it tells the compiler to use the crypto library). $ gcc bn_sample.c -lcrypto

3 Lab Tasks
To avoid mistakes, please avoid manually typing the numbers used the lab tasks. Instead, copy and paste the numbers from this PDF file.
Submission requirement: In your report, you should describe your steps and include your code and running results.

3.1 Task 1: Deriving the Private Key
Let p, q, and e be three prime numbers. Let n = p*q. We will use (e, n) as the public key. Please calculate the private key d. The hexadecimal values of p, q, and e are listed in the following. It should be noted that although p and q used in this task are quite large numbers, they are not large enough to be secure. We intentionally make them small for the sake of simplicity. In practice, these numbers should be at least 512 bits long (the one used here are only 128 bits).
p = F7E75FDC469067FFDC4E847C51F452DF
q = E85CED54AF57E53E092113E62F436F4F
e = 0D88C3

3.2 Task 2: Encrypting a Message Let (e, n) be the public key. Please encrypt the message "A top secret!" (the quotations are not
included). We need to convert this ASCII string to a hex string, and then convert the hex string to a BIGNUM using the hex-to-bn API BN hex2bn(). The following python command can be used to convert a plain ASCII string to a hex string.

This IT Assignment has been solved by our IT Experts at My Uni Paper. Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+Students in Australia, UK & US by helping them to score HD in their academics. Our Experts are well trained to follow all marking rubrics & referencing style.

Be it a used or new solution, the quality of the work submitted by our assignment Experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed that you could choose one between the two and acquire an HD either way. You could choose a new assignment solution file to get yourself an exclusive, plagiarism (with free Turnitin file), expert quality assignment or order an old solution file that was considered worthy of the highest distinction.