COMS3000/7003 – Information Security Assignment 1
2.1 RSA Public-Key Encryption and Signature Lab
2.1.1 Lab Overview
RSA (Rivest Shamir Adleman) 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. 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
2.1.2 Before Starting Tasks
The RSA algorithm involves computations on large numbers. These computations cannot be directly
conducted 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
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
create 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
// Assign a value from a hex number string
// 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
• 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 ∗ bmodn:
BN_mod_mul(res, a, b, n, ctx)
• Compute res = a
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);
A Complete Example:We show a complete example in the following. In this example, we initialise
three BIGNUM variables, a, b, and n; we then compute a * b and a
b mod n.
2.1.3 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
2.1.4 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.
python -c ‘print(“A top secret!”.encode(“hex”))’
The public keys are listed in the followings (hexadecimal). We also provide the private key d to help
you verify your encryption result.
n = DCBFFE3E51F62E09CE7032E2677A78946A849DC4CDDE3A4D0CB81629242FB1A5
e = 010001 (this hex value equals to decimal 65537)
M = A top secret!
d = 74D806F9F3A62BAE331FFE3F0A68AFE35B3D2E4794148AACBC26AA381CD7D30D
2.1.5 Task 3: Decrypting a Message
The public/private keys used in this task are the same as the ones used in Task 2. Please decrypt the
following ciphertext C, and convert it back to a plain ASCII string.
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: email@example.com 微信号:vipnxx