# 信息安全代写 | COMS3000/7003 – Information Security Assignment 1

这个作业是完成信息加密等网络安全相关的问题

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

2

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

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.

3

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);

}

• 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

cmodn:

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”))’

# 4120746f702073656372657421

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.