## Description

Learning Objectives:

● Introduction to Rust programming

● Getting up and running with Rust

● Running your first Rust program

● Add dependencies to your project

● Experiment with arithmetic libraries in Rust.

What is Rust?

● Rust is a multi-paradigm system programming, focused on safety, speed, and concurrency.

● Rust supports a mixture of imperative procedural, concurrent actor, object-oriented, and pure

functional styles.

● It also supports generic programming and metaprogramming, in both static and dynamic styles.

● The syntax is similar to C++.

● The compiler is free and open-source software.

Getting Started with Rust

● You can try Rust online in the Rust Playground.

● Alternatively, you can install Rust using the Rustup tool, which is a Rust installer and version

management tool.

o On Linux and macOS systems, this is done as:

$ curl https://sh.rustup.rs -sSf | sh

o On windows, install rustup-init.exe.

● When you install Rustup, you will also get the latest stable version of the Rust build tool and package

manager, also known as Cargo.

● Editors: Rust support is available in many editors such as Sublime, IntelliJ IDEA, and Eclipse.

What is Cargo?

● Cargo is a tool that allows Rust packages to declare their various dependencies and ensure that you’ll

always get a repeatable build.

● To accomplish this goal, Cargo does four things:

o Introduces two metadata files with various bits of package information.

o Fetches and builds your package’s dependencies.

o Invokes rustc or another build tool with the correct parameters to build your package.

o Introduces conventions to make working with Rust packages easier.

1

ECE 522 | Software Construction, Verification and Evolution

Deliverable 1: Writing your First Package with Cargo

● To create a new package, you can use cargo new:

$ cargo new hello_world

● Cargo has generated a new directory hello-rust with the following files:

hello-rus

├── Cargo.toml

└── src

└── main.rs

1 directory, 2 files

o Cargo.toml: is the manifest file which keeps metadata for the project along with the

dependencies.

o src/main.rs is where you write your code.

● Here’s what you’ll find in src/main.rs:

fn main() {

println!(“Hello, world!”);

}

● To compile your project, we’ll use Cargo:

$ cargo build

● And then run it:

$ cargo run

● You can also use Cargo to:

o build a project with cargo build

o run a project with cargo run

o test a project with cargo test

o create documentation with cargo doc

o publish a project as a library (crate) with cargo publish

● DEMO this deliverable to the lab instructor.

2

ECE 522 | Software Construction, Verification and Evolution

Deliverable 2: Adding dependencies

● Now, let us add a dependency to our project.

Rust stores all sorts of libraries on crates.io. Crates are what you use to refer to packages.

● In this part of the lab, we will use a crate called Rand, which is a Rust library for random number

generation (Hint: this library may come handy with any randomness-related algorithms)

● To add the crate to our project, we need to modify the Cargo.toml file as follows:

[dependencies]

rand = “0.7.0”

● You can find this information on from the crate page

● Now we run to let Cargo install the dependency:

cargo build

● Note that running this command creates a new file, Cargo.lock, which is the log for the versions of

the dependencies we are using.

● To actually use Rand in your code, you need to open main.rs and modify it as follows:

use rand::prelude::*;

fn main() {

let mut rng = thread_rng();

if rng.gen() {

let x: f64 = rng.gen();

let y = rng.gen_range(-10.0, 10.0);

println!(“x is: {}”, x);

println!(“y is: {}”, y);

println!(“Random Number between 0 and 9: {}”, rng.gen_range(0, 10));

3

ECE 522 | Software Construction, Verification and Evolution

}

}

● The first line imports everything from the prelude which is the lazy way to use rand as it only imports

the most common items.

The Rand library automatically initializes a thread-local generator which can be accessed via the

thread_rng and random functions. For more information, see this link.

● DEMO this deliverable to the lab instructor.

4

ECE 522 | Software Construction, Verification and Evolution

Deliverable 3: The Mathematics of Cryptology

Nearly all modern systems use cryptography as an important tool. At the hearty of cryptography are

prime numbers, a prerequisite in a public-key system is the efficient generation of public-key parameters.

For instance, cryptosystems require prime numbers p and q for an admissible RSA modulus n = pq.

Many cryptosystems depend on a trapdoor one-way function, which is a mathematical function that is

easy to compute in one way but requires secret information to compute efficiently its inverse. We can

construct trapdoors one-way functions from hard number-theoretic problems like the integer

factorization. The formal definition of factoring is:

Given a composite integer N, the factoring problem is to find integers p, q such that pq=N.

So far, the largest number factored is 232 digits long (768-bit) by using hundreds of computers and two

years. Using a home computer, it would have taken 2000 years. Finding the prime factors for numbers

the size of what we use for cryptography today (2048 bits) it is approximately four billion times harder

than 768-bits.

Before starting to generate prime numbers, we need to select an arbitrary-precision arithmetic library.

This is required; because the numbers that we are going to manipulate might be pretty big (a 1024-bit

number is an integer of 309 digits). It is needed to use a special data structure to support big integers.

Usually, the Integer class manages 32 bits, meaning it can hold values up to 2³² (4,294,967,295) which for

many applications might be enough; however, to achieve security we need to be able to use big

numbers. We do not just need to store the numbers, but to compute operations like multiplications and

exponentiations between them. Rust has (many) common arbitrary-precision arithmetic libraries, e.g.,

rug, apint.

// Blue code is pseudo-code.

use rand::prelude::*; // Need this for rng.gen_range(…) function to work.

fn function(n: u32) -> Int {

let mut rng = rand::thread_rng();

loop {

let mut candidate::Int = Int::from(rng.gen_range(0, n));

candidate.set_bit(0, true);

let i = u64::from(&candidate);

if is_prime(i)== true {

return candidate;

}

}

}

Question 1. What is the above algorithm doing?

5

ECE 522 | Software Construction, Verification and Evolution

Question 2. Rewrite the above algorithm to use another multiple-precision arithmetic library (e.g., rug,

apint). Note: You can use a library (crate) for the is_prime function (i.e. you do not have to write the is

prime function from scratch).

● To test whether a number is prime or not, there is the school method which is to iterate over all the

smaller numbers and check if any of those numbers perfectly divide the prime candidate. We can

immediately optimize our first attempt. First of all, we do not need to iterate through all the

numbers, but just up to the square root, (the random number is forced to be odd). A better

approach is to use a probabilistic algorithm, which can be used to determine whether a number is

prime with a given degree of confidence. Probabilistic algorithms are algorithms that employ

randomness to reduce the complexity or expected running time. The most known probabilistic

algorithm used in practice is the Miller-Rabin test. It determines whether a candidate number is

prime or not. The confidence of the algorithm depends on the number of iterations. Three iterations

lead to a probability of failing to once in 2⁸⁰, which is considered a secure implementation.

// Blue code is pseudo-code.

fn miller_rabin(candidate: &Int) -> bool {

// Rewrite finds the values s and d from this equation: candidate-1=d*2^s

let (s, d) = rewrite(candidate);

for _ in 0..5 {

let basis = thread_rng().gen_int_range(&Int::from(2), candidate-2);

let mut x = mod_exp(&basis, &d, candidate);

// 1_usize is just the number 1.

if x == 1_usize || x == (candidate – 1_usize) {

continue;

} else {

for i in Int::zero()..s – 1_usize {

x = mod_exp(&x, &Int::from(2), candidate);

if x == 1_usize {

return false;

} else if x == candidate – 1_usize {

break;

}

if i == s – 2_usize {

return false;

{

}

}

}

true

}

Question 3. Explain the algorithm the above code segment is implementing.

6

ECE 522 | Software Construction, Verification and Evolution

Question 4. Several cryptographic libraries use the Miller-Rabin test to output probable primes. Albrecht

et al. were able to construct composite numbers that some of these libraries declared to be prime.

Hence, we need something better. Identify the crate which most closely implements the

recommendations from Prime and Prejudice. (Hint: The crate mentions the paper Prime and Prejudice.)

Question 5. Finally, prime fun. Prime number 41, can be written as the sum of six consecutive prime

numbers: 41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime contains X terms and is

equal to Y. Write a Rust program which calculates and prints X, Y, and the list of primes.

● DEMO this deliverable to the lab instructor.

7