UNIVERSITY OF INFORMATION TECHNOLOGY – VNU-HCM

FACULTY OF COMPUTER NETWORKS AND COMMUNICATIONS

2. Public-Key Cryptography

PHỤC VỤ MỤC ĐÍCH GIÁO DỤC

FOR EDUCATIONAL PURPOSE ONLY

A. OVERVIEW
1. Introduction and learning objective
Symmetric encryption has evolved from classical to modern but also leaves a lot to
be desired. Two of the most difficult problems associated with symmetric encryption
are:

§ Key distribution -the issue of secret key exchange between sender and
receiver: Key distribution under symmetric encryption requires either (1) that
two communicants already share a key, which somehow has been distributed
to them; or (2) the use of a key distribution center. A secure channel is required
for key exchange so that the key must be kept secret and known only to the
sender and receiver. This will be difficult to implement and establishing such
a secure channel will be costly and time-consuming.

§ Digital signatures and confidentiality of keys: If the use of cryptography was

to become widespread, not just in military situations but for commercial and
private purposes, then electronic messages and documents would need the
 Lab 2: Public-Key Crytography

2
equivalent of signatures used in paper documents. Besides, there is no basis
to blame if the key is revealed.

Diffie and Hellman achieved an astounding breakthrough in 1976, by coming up

with a method that addressed both problems and was radically different from all
previous approaches to cryptography, going back over four millennia. That is public-
key cryptography or asymmetric cryptography. The development of public-key
cryptography is the greatest and perhaps the only true revolution in the entire
history of cryptography.

To discriminate between the two, we refer to the key used in symmetric encryption
as a secret key. The two keys used for asymmetric encryption are referred to as the
public key (are often denoted as PU) and the private key (are often denoted as PR).
The plaintext is denoted by M, the ciphertext is denoted by C

There are 2 main approaches in Public-key cryptography:

Figure 1: Two approaches in Public-Key Cryptography

Faculty of Computer Networks NETWORK SECURITY – 09/2022

and Communications [email protected]
 Lab 2: Public-Key Crytography

3
§ Public-Key Cryptosystem for Confidentiality:

Encryption with the public key (Figure 1). If Bob wishes to send a confidential
message to Alice, Bob encrypts the message using Alice’s public key. When
Alice receives the message, she decrypts it using her private key. No other
recipient can decrypt the message because only Alice knows Alice’s private
key.
• Encryption: C = E(M, PU)
• Decryption: M = D(C, PR)

§ Public-Key Cryptosystem for Authentication:

Encryption with public key (Figure 3.1). In this case, Alice prepares a message
to Bob and encrypts it using Alice’s private key before transmitting it. Bob can
decrypt the message using Alice’s public key. Because the message was
encrypted using Alice’s private key, only Alice could have prepared the
message. Therefore, the entire encrypted message serves as a digital signature.
• Encryption: C = E(M, PR)
• Decryption: M = D(C, PU)

The learning objective of this lab is for students to gain hands-on experience with
the RSA and ECDSA algorithm. From lectures, students should have learned the
theoretical part of these algorithms, so they know mathematically how to generate
public/private keys and how to perform encryption/decryption and signature
generation/verification. This lab enhances students’ understanding of algorithms by
requiring them to go through every essential step of the algorithm on actual
numbers, so they can apply the theories learned from the class. Essentially, students
will be implementing the RSA and ECDSA algorithm using a programming
language.

2. Backgrounds and Prerequisites

To complete this task well, you are expected to gain knowledge about:
§ Number Theory:
o Modular Arithmetic.
o Divisor, the greatest common divisor (Euclidian Algorithm).
o Prime numbers, Testing for Primality.
§ RSA Cipher.
§ ECDSA Cipher.

Faculty of Computer Networks NETWORK SECURITY – 09/2022

and Communications [email protected]
 Lab 2: Public-Key Crytography

4
B. LAB TASKS
1. Number Theory
Before starting with the public key encryption algorithm, we will kick off with some
number theory revision, specifically checking for prime numbers, greatest common
divisor (GCD), and modulo with “large” numbers.

In this task, you need to write the necessary functions for the requirements
below. Only C, C++, or C# language is accepted. The large number stands for
the number that has at least 10 bytes in size, recommended as large as possible
that you can handle.

1. Generate a random large number.

2. Determine the Greatest Common Divisor (GCD) of 2 arbitrary large
numbers.
3. Compute the modular exponentiation ax mod p. Your program should be
able to compute in case of “large” exponents (x > 80), for example, 794 mod
19.
4. Primary number:
+ Check if an arbitrary integer larger than 289 is prime or not.
+ Generate random large prime numbers.
5. Benchmark your application: Evaluate the performance of your function
by running batches of thousand numbers (or pair of numbers)
simultaneously for each subtask above multiple times. Report the average
time (include the environment and hardware resources used to run your
program)

It would be best if you could define a new suitable data structure for handling large
numbers, but you can use any libraries for your necessary data types. Only standard
arithmetic operators supported by these libraries, including addition, subtraction,
multiplication, division, modulus, increment, and decrement, are allowed. You must
define the appropriate algorithms based on the allowed arithmetic operations above to
conquer all requirements of this task.

Tips:
§ To determine the greatest common divisor, you should use the Euclidian algorithm.

Faculty of Computer Networks NETWORK SECURITY – 09/2022

and Communications [email protected]
 Lab 2: Public-Key Crytography

5
§ To check large prime numbers, you can find out and use the Miller-Rabin1 algorithm.
§ Modular multiplications have the following property:
(𝑎 × 𝑏) ≡ [(𝑎 𝑚𝑜𝑑 𝑛) × (𝑏 𝑚𝑜𝑑 𝑛)] 𝑚𝑜𝑑 𝑛
It can be applied in computing modular exponentiation in case of “large” exponents.

2. Simple RSA Public-Key Encryption

RSA is one of the first public-key cryptosystems and is widely used for secure
communication. This cipher was developed in 1977 by Ron Rivest, Adi Shamir, and
Len Adleman at MIT and first published in 1978. In RSA scheme, the plaintext and
ciphertext are integers between 0 and n - 1 for some n. A typical size for n is 1024
bits, or 309 decimal digits. That is, n is less than 21024. RSA algorithm can be
summarized as follows.

1. Select two “large” prime numbers p and q (p ≠ q), then calculate n = pq

2. Calculate 𝜙(𝑛) = (𝑝 − 1)(𝑞 − 1)
3. Select e such that e is relatively prime to 𝜙(𝑛) and less than 𝜙(𝑛)
4. Determine d such that 𝑒. 𝑑 ≡ 1 𝑚𝑜𝑑 𝜙(𝑛) (d can be calculated using the extended

Euclid’s algorithm)
5. The resulting keys are public key PU = (e,n) and private key PR = (d,n)
6. To encrypt a plaintext input of M:
+ Encryption for Confidentiality: C = E(M,PU) = Me mod n
+ Encryption for Authentication: C = E(M,PR) = Md mod n
7. To decrypt ciphertext input of C:
+ Decryption for Confidentiality: M = D(C, PR) = Cd mod n
+ Decryption for Authentication: M = D(C,PU) = Cemod n

Figure 2: Example of RSA Algorithm

When using RSA to process multiple blocks of data, each plaintext symbol could be
assigned a unique code of two decimal digits (e.g., a = 00, A = 26). A plaintext block
consists of four decimal digits, or two alphanumeric characters. Figure 3.3.a
1
https://asecuritysite.com/encryption/rabin

Faculty of Computer Networks NETWORK SECURITY – 09/2022

and Communications [email protected]
 Lab 2: Public-Key Crytography

6
illustrates the sequence of events for the encryption of multiple blocks, and Figure
3.3.b gives a specific example. The circled numbers indicate the order in which
operations are performed.

Figure 3: RSA Processing of Multiple Blocks

Write a cryptography application to simulate the working of the simple RSA Cipher.
The allowed programming languages are C, C++, and C#. Your application
needs to show up how to achieve the goal of the following requirements in detail:

1. Generate a key pair (PU, PR) from the given “valid” inputs (p, q, e), or
generate a randomized.
Note that the key pair is as large as possible.

2. Use the generated keys to encrypt/decrypt the message. The message can
be numeric or string.

Recommend reusing all functions that you defined in the previous task. Using any
cryptographic libraries is not allowed.

Faculty of Computer Networks NETWORK SECURITY – 09/2022

and Communications [email protected]
 Lab 2: Public-Key Crytography

7
Tips:

You need to solve some problems when writing this application such as: generating/testing
large prime numbers (can use Miller-Rabin algorithm); finding the greatest common divisor
(can use Euclidian’s algorithm); applying modular multiplication and exponentiation
properties to calculate “large” 𝑎 ! 𝑚𝑜𝑑 𝑛.

3. The application of asymmetric cipher

In this task, you will propose the solution and develop the application for one of
the topics below. You are not limited to using programming languages, libraries,
or frameworks.

1. The secure files transfer over the network:

Features: Send or Receive files securely between nodes in the Peer-To-Peer model.
Your application should support up to dozen Gigabytes of file size.
Advanced features: Your application should use pipeline connections to speed up
transferring progress.

2. The secure chat in the insecure network environment:

Features: Setting up a chat system so that users can send or receive messages
securely with each other. The application will work as a Client-Server model. You
must ensure that when users chat, no one else can get their messages in plaintext.
Your system must support multiple users chatting simultaneously.
Advanced features: Advanced features: Integrate the simple End-to-End
encryption feature to enhance privacy. Only two end devices can decrypt their
message.

3. Simple botnet system:

In this task, you need a controller and multiple agents. The controller will be able to
broadcast a command to all bots to conquer a special task, e.g., a DDOS attack.
- Controller: Working as the server and always ready for new agent joining. Users
(such as botnet’s owner) can interact with whole bots through the controller.
- Bots: Each bot is required to join with the controller before working. They can
communicate with the controller to receive commands or send data back; and
communicate with nearby bots to broadcast commands faster. The criterion for
nearby bots is your self-define, e.g., in the same network. How do the bots
discover each other is depending on you, e.g., get the bots list from the controller,
and scan in your network.

Faculty of Computer Networks NETWORK SECURITY – 09/2022

and Communications [email protected]
 Lab 2: Public-Key Crytography

8
- You need to apply cryptography to ensure that communication between
controller and bot, or between bot and bot, is secure.
- Some suggested commands: broadcast file to bots, schedule request to target from
all bots (e.g., HTTP request, ping).

§ To get the best performance efficiency, you may need a hybrid RSA- or ECC-based
cipher with other ciphers, e.g., symmetric ciphers.
§ Your application will be graded in various metrics, e.g., security, performance,
UX/UI, data structure, and algorithms.
§ Organize your code so that you can easily add new features. This application can be
used for the next lab with enhanced integrity and confidentiality from hashing,
digital certificates, etc.
,

C. REQUIREMENTS
You are expected to complete all tasks in section B (Lab tasks). Advanced tasks
are optional, and you could get bonus points for completing those tasks. We
prefer you work in a team of two or three to get the highest efficiency.

Your submission must meet the following requirements:

§ You need to submit a detailed lab report in .docx (Word Document) format,
using the report template provided on the UIT Courses website.

§ Either Vietnamese or English report is accepted, that’s up to you. The

report written in the mixing of multiple languages is not allowed (except
for the untranslatable keywords).

§ When it comes to programming tasks (require you to write an application or

script), please attach all source-code and executable files (if any) in your
submission. Please also list the important code snippets followed by
explanations and screenshots when running your application in your
report. Simply attaching code without any explanation will not receive
points.

§ Submit work you are proud of – don’t be sloppy and lazy!

Your submissions must be your own. You are free to discuss with other
classmates to find the solution. However, copying reports is prohibited,
even if only a part of your report. Both reports of the owner and the copier

Faculty of Computer Networks NETWORK SECURITY – 09/2022

and Communications [email protected]
 Lab 2: Public-Key Crytography

9
will be rejected. Please remember to cite any source of the material
(website, book,…) that influences your solution.

Notice: Combine your lab report and all related files into a single ZIP file (.zip),
name it as follow:

StudentID1_StudentID2_ReportLabX.zip

Attention: Don’t share any materials (slides, readings, assignments, labs, etc..) out of our
class without my permission!

Faculty of Computer Networks NETWORK SECURITY – 09/2022

and Communications [email protected]