Assignment 6
Public Key Cryptography
CSE 13S – Fall 2021
First DESIGN.pdf draft due: November 11th at 11:59 pm PST
Assignment due: November 21st at 11:59 pm PST
1 Introduction
Doo Jdxo lv glylghg lqwr wkuhh sduwv, rqh ri zklfk wkh Ehojdh lqkdelw, wkh
Dtxlwdql dqrwkhu, wkrvh zkr lq wkhlu rzq odqjxdjh duh fdoohg Fhowv, lq rxu Jdxov,
wkh wklug.
—Julius Cæsar
Cryptography, once restricted to government, spies, and the military is now pervasive in our lives. Most
web sites that you visit are protected using SSL. Your SSH connections are protected in the same way.
How is this accomplished? Through a mixture of public key and symmetric key cryptography. The
earliest known practical public-key cryptography algorithm is RSA, after its inventors Ronald Rivest, Adi
Shamir, and Leonard Adleman (Figure 2), who published it in 1978. About five years earlier, on 20 November,
1973, Clifford Cocks (Figure 1), working for GCHQ (the British equivalent of the NSA), invented a very
similar algorithm. His classified memorandum“A note on‘non-secret’encryption”was to remain secret
for 24 years. In fact, when you read the Cocks memorandum, you will see that the idea of public key encryption
was proposed by J. H. Ellis three years earlier in 1970. Unknown in the public literature, the idea
was independently proposed by Ralph Merkle for public key distribution, which inspired asymmetric
cryptography by Whitfield Diffie and Martin Hellman, and finally leading to RSA.
Public-key cryptography, or asymmetric cryptography, is a cryptographic system that uses pairs of
keys: public keys (known to others) and private keys (known only by the owner). The generation of such
key pairs depends on cryptographic algorithms that are based on mathematical objects called one-way
functions. Security requires keeping the private key private; the public key can be distributed widely.
Any person can encrypt a message using the intended receiver’s public key, but that encrypted message
can only be decrypted with the receiver’s private key. This allows a server to create a cryptographic
key for suitable symmetric-key cryptography and then use a client’s openly shared public key to encrypt
the newly generated symmetric key. The server can then send this encrypted symmetric key over an
insecure channel to the client; only the client can decrypt it using its private key. With the client and
server both having the same symmetric key, they can safely use symmetric key encryption to communicate.
This scheme has the advantage of not having to pre-share symmetric keys while gaining the higher
speed of symmetric-key cryptography.
Symmetric-key algorithms use the same cryptographic keys for the encryption of plaintext and the
decryption of ciphertext. The keys may be identical, or there may be a simple transformation between
© 2021 Darrell Long 1
the two keys. The keys represent a shared secret between two or more parties. The requirement that
both parties have access to the secret key is one of the main disadvantages of symmetric-key encryption
compared to public-key encryption.
Let’s briefly look at the Cocks algorithm before moving on to the more popular RSA algorithm. We
have two principals: Alice (A), who is the receiver, and Bonnie (B), who is the sender.
(a) Alice:
i. Chooses two primes p and q such that p – (q−1) and q – (p−1). That is, p does not divide
q−1 and q does not divide p−1.
ii. Transmits the computed product n = pq to the sender, which we write as A
n−→ B.
(b) Bonnie:
i. Has a message consisting of numbers c1,c2,…,cr where 0 < ci < n.
though we can calculate it much more rapidly using division. A good choice for e is 2
16 +1 = 65537. You
will understand why—to some extent—after you finish §6.3. Here’s a hint: How many 1 bits are in that
number?
The ϕ function is called the totient of n, and that denotes the number of positive integers up to a
given integer n that are relatively prime to n. Note that for any prime p, ϕ(p) = p−1, and so ϕ(n) =
ϕ(pq) = (p−1)(q−1). We can share e with impunity. We say that our public key is the pair 〈e,n〉.
We now calculate a unique secret integer d ∈ {0,…,n − 1} such that d × e ≡ 1 (mod ϕ(n)). How
do we find this d? It turns out that we have known how to do it for more than 2300 years—we use an
algorithm attributed to Euclid. How is it that we can easily calculate d while our adversary cannot? We
know a secret that he does not: we know ϕ(n) while he only knows n. We call d our private key.
We now define two functions: D(m) = me
(mod n) and E(c) = c
d
(mod n). We will show in §3
that ∀m ∈ {0,…,n−1} that D(E(m)) = E(D(m)) = m. Since D and E are mutual inverses and this will
enable us to perform not only encryption but also digital signatures.
3 Mathematics of RSA
If P = NP , then all of modern cryptography collapses. On this happy
thought. . .
Michael O. Rabin, November 1998
The mathematics of RSA are based on arithmetic in a group of integers modulo n, denoted Z/n. This
is the set {0,…,n − 1} and all sets that are isomorphic to it. For example, {n,…,2n − 1} (mod n) =
{0,…,n−1} (mod n), and there are an infinite number of such sets. Since they are all the same we will
only concern ourselves with the one with the smallest numbers. What do we mean when we say that
are the same? We mean that if x ≡ k (mod n) then an+x ≡ k (mod n),∀a ≥ 0,a ∈ Z. In other words,
additional integer products of n do not matter.
The Euler-Fermat theorem says that if a ∈ N and n ∈ N are coprime, that is gcd(a,n) = 1, then
a
ϕ(n) ≡ 1 (mod n).
This will allow us, for example, to take a message M and have Mϕ(n) ≡ 1 (mod n).
What is ϕ(n)? It is the Euler totient function, and gives the number of positive integers than that or
equal to n that are relatively prime to n. For any prime number p,
ϕ(p) = p−1.
For the RSA algorithm, we choose two large primes p and q, and we make n = pq. What does this
mean for us with respect to ϕ(n)?
ϕ(n) = ϕ(p)×ϕ(q)
the library here: https://gmplib.org/manual.
Take some time to look through the manual, taking note of which functions may be useful.
You will need to install both gmp and pkg-config. The latter is a utility used to assist in finding and
linking libraries, instead of having the program hard-code where to find specific headers and libraries
during program compilation. To install these packages on Ubuntu 20.04, run the following:
$ sudo apt install pkg – config libgmp -dev
Get started on this as soon as possible. Make sure to attend section for assistance on using pkg-config
in a Makefile to direct the compilation process for your programs.
You may notice that GMP already provides number theoretic functions, several of which could be
used in RSA. You may not use any GMP-implemented number theoretic functions. You must implement
those functions yourself.
The following two sections (§6 and §7) will present the functions that you have to implement, but
they both will require the use of random, arbitrary-precision integers.
GMP requires us to explicitly initialize a random state variable and pass it to any of the random integer
functions in GMP. Not only that, we also need to call a dedicated function to clean up any memory
used by the initialized random state. To remedy this, you will implement a small random state module,
which contains a single extern declaration to a global random state variable called state, and two
functions: one to initialize the state, and one to clear it. The interface for the module will be given in
randstate.h and the implementation must go in randstate.c.
void randstate_init(uint64_t seed)
Initializes the global random state named state with a Mersenne Twister algorithm, using seed as the
random seed. This entails a call to gmp_randinit_mt() and a call to gmp_randseed_ui().
void randstate_clear(void)
Clears and frees all memory used by the initialized global random state named state. This should just
be a single call to gmp_randclear().
© 2021 Darrell Long 6
6 Number Theoretic Functions
No one has yet discovered any warlike purpose to be served by the theory of
numbers or relativity, and it seems unlikely that anyone will do so for many
years.
—G. H. Hardy
Number Theory is the branch of mathematics that studies the nature and properties of numbers. Though
many have made important contributions to the field, including Gauß in his Disquisitiones Arithmeticae
(which he completed when he was 21 years old), the most important for public-key cryptography are
Fermat and Euler (Figure 3).
You will first need to implement the functions that drive the mathematics behind RSA before you
can tackle your RSA library. The interface for these functions will be given in numtheory.h and should
be defined in corresponding C file. Read each of the subsections carefully to understand, on some level,
the theory behind each of the number theoretic functions. Pseudocode is provided to assist you.
Figure 3: Leonhard Euler (1707–1783) and Pierre de Fermat (1607–1665)
6.1 Modular Exponentiation
As shown in §2, we must compute a
—Michael O. Rabin, October 1997
The simplest primality test is trial division: given an input number, n, check whether it is evenly divisible
by any prime number between 2 and p
n. Thus, this simple algorithm1
is O(
p
n), but can we do better?
The answer is subtle. To be certain, we must try all of the primes from up to p
n; there is no way to escape
it. But we can do much better if we are willing to accept an answer of probably.
Since it is infeasible to use a deterministic algorithm, we can solve many problems with high probability
by using a randomized algorithm. Such algorithms explore random parts of the problem space so
that we have high (but not perfect) confidence that they have solved the problem.
Probabilistic tests are more rigorous than heuristic tests in that they provide provable bounds on the
probability of being fooled by a composite number. All practical primality tests are probabilistic tests.
These tests use, apart from the tested number n, some other number a (called a witness) that is chosen
at random from some sample space. The usual randomized primality tests never report a prime number
as composite, but a composite number may be reported as prime.
The simplest probabilistic primality test is the Fermat primality test. It works as follows: Given an
integer n, choose some integer a coprime to n and calculate a
n−1
(mod n). If the result is different
from 1, then n is composite. If it is 1, then n may be prime. If a
n−1 ≡ 1 (mod n) n is not prime, then n
is called a pseudoprime to base a. In practice, we observe that, if a
n−1 ≡ 1 (mod n), then n is usually
prime.
Better yet is the Solovay-Strassen probabilistic primality test, developed by Robert M. Solovay and
Volker Strassen in 1977. It is of particular importance since it made practical public-key algorithms such
as RSA.
Figure 4: Gary L. Miller and Michael O. Rabin
The Miller–Rabin primality test, invented by Gary Miller and Michael O. Rabin (Figure 4), is an even
1How big is p
n? A typical encryption key has more than 600 decimal digits. Thus, p
10600 = 10300. Suppose we can do one
trial division every nanosecond, then that’s 10300−9 = 10291 seconds. There are 22,896,000 or about 107 seconds per year, so
it will take about 10284 years (the Big Bang was about 13.7×109 years ago).
© 2021 Darrell Long 9
more sophisticated probabilistic test, which detect all composites (once again, this means: for every
composite number n, at least 3
4
of numbers a are witnesses of compositeness of n). The accuracy of
these tests is compared in Figure 5.
Miller-Rabin
Solovay-Strassen
5 10 15 20
Rounds
0.5
0.6
0.7
0.8
0.9
1.0
Pr(prime)
Figure 5: Pr[prime(p)] after successfully passing a given number of rounds.
The Miller–Rabin primality test works as follows: Given an integer n, choose some positive integer
a < n. Let 2
sd = n−1, where d is odd. If a
d
6≡ ±1 (mod n) and a
2
rd
6≡ ±1 (mod n) for all 0 ≤ r ≤ s−1,
then n is composite and a is a witness for the compositeness. Otherwise, n might be prime. That is,
−200 and that is usually more than good enough. The Miller–Rabin test is considered a strong
pseudoprime test, where a pseudoprime is a number that is determined to be probably prime by a probabilistic
test, but not actually prime. Deterministic primality tests, such as the AKS primality test, do not
give false positives.
MILLER-RABIN(n,k)
1 write n−1 = 2
s
r such that r is odd
2 for i ← 1 to k
3 choose random a ∈ {2,3,…,n−2}
4 y = POWER-MOD(a,r,n)
5 if y 6= 1 and y 6= n−1
6 j ← 1
7 while j ≤ s−1 and y 6= n−1
8 y ← POWER-MOD(y,2,n)
9 if y == 1
10 return FALSE
11 j ← j+1
12 if y 6= n−1
13 return FALSE
14 return TRUE
© 2021 Darrell Long 10
The function that you are expected to implement to perform primality testing should be declared as
follows:
void is_prime(mpz_t n, uint64_t iters)
Conducts the Miller-Rabin primality test to indicate whether or not n is prime using iters number of
Miller-Rabin iterations. This function is needed when creating the two large primes p and q in RSA,
verifying if a large integer is a prime.
In addition to the is_prime() function, you are also required to implement the following function:
void make_prime(mpz_t p, uint64_t bits, uint64_t iters)
Generates a new prime number stored in p. The generated prime should be at least bits number of bits
long. The primality of the generated number should be tested using is_prime() using iters number
of iterations.
6.3 Modular Inverses
The Euclidean algorithm, also called Euclid’s algorithm, is an efficient method for computing the greatest
common divisor (gcd) of two integers, the largest number that divides them both with a zero remainder.
The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers
does not change if their difference replaces the larger number with the smaller number. Since this replacement
reduces the larger of the two numbers, repeating this process gives successively smaller pairs
of numbers until the two numbers become equal. We can accomplish this much faster if we compute
the remainder, which is equivalent to subtracting the smaller number from the larger until it is no longer
larger. You will first want to implement the following function to compute the greatest common divisor
of two integers, which should be defined as follows:
void gcd(mpz_t d, mpz_t a, mpz_t b)
Computes the greatest common divisor of a and b, storing the value of the computed divisor in d.
GCD(a,b)
1 while b 6= 0
2 t ← b
3 b ← a mod b
4 a ← t
5 return a
The extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition
to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout’s identity,
which are integers x and y such that
ax+by = gcd(a,b).
The extended Euclidean algorithm is particularly useful when a and b are coprime. With that provision,
x is the modular multiplicative inverse of a (mod b), and y is the modular multiplicative inverse of b
(mod a).
© 2021 Darrell Long 11
Bézout’s identity asserts that a and n are coprime if and only if there exist integers s and t such that
ns+at = 1.
Reducing this identity modulo n gives
at ≡ 1 (mod n).
To adapt the extended Euclidean algorithm to the problem of computing the multiplicative inverse, note
that the Bézout coefficient of n is not needed and so does not need to be computed. Also, for getting a
positive and result that is less than n, use the fact that the integer t provided by the algorithm satisfies