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 (Figure2), who published it in 1978. About five years earlier, on 20 Novem- ber, 1973, Clifford Cocks (Figure1), 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 asymmet- ric cryptography by Whitfield Diffie and Martin Hellman, and finally leading to RSA. RSA in turn gave rise to numerous related algorithms such as the Schmidt-Samoa algorithm, which will be the focus of this assignment. While Schmidt-Samoa has not gained wide adoption as compared to RSA, variety is the spice of life.

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 mes- sage 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 communi-cate. 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 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 SS algorithm. We have two princi- pals: 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 A (q −1) and q A (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 B. (b)  Bonnie:

i.  Has a message consisting of numbers c1 ,c2, . . . ,cr where 0 < ci < n.

ii.  Sends these encoded as di where di = ci(n)  (mod n).  When written as part of a protocol, B A.

(c) Alice:

i.  Computes using Euclid’s Algorithm p\  such that p x p\ 三 1 (mod q − 1), and q\  such that q x q\ 三 1 (mod p −1).

ii.  Decodes ci = di(p)\    (mod q) = di(q)\    (mod p).

Figure 1: Clifford Cocks

As with the SS algorithm, as you will see, the strength of the algorithm relies on the assumed difficulty of factoring large composite integers. We say assumed difficulty since there is, like 夕 r夕, no proof of this widely held assumption. A proof that 夕 r夕 would be welcome, but unsurprising, while a proof that 夕 = r夕 would probably have theoreticians jumping out of windows.

The paper published by Rivest, Shamir and Adleman in 1978,

Ronald L. Rivest, Adi Shamir, and Leonard Adleman. “A method for obtaining digital signa- tures and public-key cryptosystems,” Communications of the ACM 21.2 (1978): 120– 126.

is one of the most important papers ever published. It enabled the modern Internet and changed the world. You would do well to take the time to read it.

Figure 2: Adi Shamir, Ronald Rivest, and Leonard Adelman

2 Schmidt-Samoa (SS) Algorithm

The magic words are Squeamish Ossifrage.

—Ronald L. Rivest

The security of RSA relies on the practical difficulty of factoring the product of two large prime numbers, known as the factoring problem. However, doing so would allow an adversary to factor all ciphertexts en- crypted under that key. Decrypting particular RSA ciphertexts is known as the RSA problem. At first look it would appear that the RSA problem may be easier than factoring, and there are some cryptographers who believe this is the case. Though there are no published, efficient methods to break RSA if a large enough key is used – short of building a quantum computer and running Shor’s algorithm on it – this theoretical gap between the factoring problem and the RSA problem is not ideal. The Schmidt-Samoa algorithm rectifies this theoretical problem, by modifying the RSA algorithm in such a way that the SS problem is provably equivalent to the factoring problem. However, this property comes as the cost of efficiency, which is why today’s cryptographic protocols have largely ignored SS in favor of RSA.

SS involves a public key and a private key. Everyone can know the public key, and it is used for en- crypting messages. The intention is that messages encrypted with the public key can only be decrypted by using the private key.

The public key consists of the modulus n, which is composed of two large, random primes p and q. The private key consists of the private exponent d and the private modulus lcm(p−1,q−1), which must be kept secret; p, q must also be kept secret since they are used to calculate d and lcm(p −1,q −1). In fact, p and q can be discarded after d has been computed.

We proceed by choosing two large random primes p and q, these numbers must be kept secret. In particular we want large random primes, where p A q−1 and q A p−1 and both p−1 and q−1 have large prime factors. We then publish the number n = p2 q. You might wonder why we can do this, and the reason is that it is believed to be hard to factor large composite integers into their constituent primes. The fundamental theorem of arithmetic tells us that every integer has a unique prime factorization.

We now calculate lcm(p−1,q−1), the private modulus, and a unique secret integer d e (0, . . . ,n−1)  such that d xn 三 1 (mod lcm(p−1,q−1)). 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 p and q while he  only knows n. We call d our private exponent. Together pq and d make up our private key.

We now define two functions: E(m) = mn  (mod n) and D(c) = cd  (mod pq). We will show in §3 that Am e (0, . . . ,pq −1) that D(E(m)) = m.

There’s a catch here. Say we want to publish the public key, so that people can encrypt messages for us. We know that our message space is (0, . . . ,pq −1), and that messages outside of that space will not decrypt correctly, so along with n we have to publish pq, right? Wrong! If we did that, then anyone could calculate p = n/pq and q = pq/p. With that information anyone can determine our private key! Instead, we observe that

,n =p,q

< pq,

so instead of using our full message space, (0, ...,pq − 1), we will just allow messages in a truncated message space (0, ,n −1).

How do we know that this doesn’t break our security like we would have had we published pq? Be- cause, we are just computing some function of the public information n. For a system to be secure, it must be able to keep the private key secret against adversaries with polynomial resources and access to n. Because Schmidt-Samoa is secure, asking people to compute a polynomial time algorithm with n as the input can’t give the adversary any advantage that he didn’t already have!

This issue highlights something important:  don’t write your own cryptographic algorithms!  (this assignment excluded) It’s very easy to make mistakes and write algorithms that look secure but are trivial to break. As Bruce Schneier said, "anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can’t break."

3 Mathematics of SS

If 夕 = r夕, then all of modern cryptography collapses. On this happy thought. . .

Michael O. Rabin, November 1998

The mathematics of SS are based on arithmetic in a set of integers modulo n, denoted Z/n. This is the

set (0, . . . ,n−1) and all sets that are equivalent 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), Aa 2 0,a e Z. In other words, additional integer products of n do not matter.

The Euler-Fermat theorem says that if a e N and n e 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 SS algorithm, we choose two large primes p and q, where p A q −1 and q A p −1, and we make n = p2 q. Then we calculate d such that d . n 三 1 (mod lcm(p −1,q −1)). What does this mean for us with respect to ϕ(pq)?

ϕ(pq) = ϕ(p) x ϕ(q)

= (p −1)(q −1)

= pq −(p +q)+1.

Now because we chose p and q such that p A q −1 and q A p −1, n = p2 q is relatively prime to ϕ(pq), that is, gcd(n,ϕ(pq)) = 1.  Because of this we know that a decryption key d exists, such that n x d 三 1 (mod ϕ(pq)).  Our encryption algorithm is simply E(M) = Mn  (mod n) = C, and our decryption algorithm is D(C) = Cd  (mod pq) = M.

Observe that,

Mnd 三 Mkϕ(pq)+1     (mod pq)

for some integer k 2 1. This is true because, prior to the modular reduction, nd must be one greater than some multiple of ϕ(pq); applying the modulus is what makes nd 三 1 (mod ϕ(pq)). We can rewrite this as

Mnd 三 (Mϕ(pq))k x M   (mod pq).

Here we apply Euler’s theorem, which states that if a and n are coprime integers, then aϕ(n) 三 1 (mod n). So, assuming that M is coprime with pq, we can simplify the above equation to

Mnd 三 (1)k x M (mod pq)

三 (1) x M (mod pq)

三 M (mod pq)

which proves that decryption really does work on encrypted messages.

In practice, Carmichael’s function can be used in place of Euler’s totient in the computation of the SS key pair.  Carmichael’s function is denoted with λ(n), where λ(n) = lcm(λ(p),λ(q)).  We indicate

the least common multiple of some a and b with lcm(a,b). From the definition of the least common multiple, we see that

λ(n) = λ(pq)

= lcm(λ(p),λ(q))

lλ(p) x λ(q)l

gcd(λ(p),λ(q)) .

If d and b are prime, then we know Y(d) = 山(d) = d −L, and Y(b) = 山(b) = b −L. Thus,

lY(d) x Y(b)l

Y(n) =

l山(d) x 山(b)l

gcd(d −L‘b −L)

l山(n)l

gcd(d −L‘b −L) .

It should be clear from this that 山(db) is a multiple of Y(db). Therefore,

Mnp 三 (M山(db))入 x M (mod db)

三 (M车xY(db))入 x M (mod db)

三 (MY(db))车入 x M (mod db)

for some multiplier 车 2 L.

From Carmichael’s generalization of Euler’s theorem, we know that DY(db) 三 L (mod db). Thus,

Mnp 三 (MY(db))车入 x M (mod db)

三 (L)车入 x M (mod db)

三 (L) x M (mod db)

三 M (mod db)‘

which demonstrates how Y(db) can be used in place of 山(db) for the computation of the SS key pair. For your assignment, you will be using Carmichael’s function when computing your SS key pair.

4 Your Task

“Personally,” he said, “my great ambition is to count all this,”—he waved vaguely at the treasure around him—“and possibly sort it into piles. ”

—John C. Gardner, Grendel

You will be creating three programs for this assignment:

1. A key generator: keygen

2. An encryptor: encrypt

3. A decryptor: decrypt

The keygen program will be in charge of key generation, producing SS public and private key pairs. The encrypt program will encrypt files using a public key, and the decrypt program will decrypt the encrypted files using the corresponding private key.

You will need to implement two libraries and a random state module that will be used in each of your programs.  One of the libraries will be hold functions relating to the mathematics behind SS, and the other library itself will contain implementations of routines for SS. You also need to learn to use a library: the GNU multiple precision arithmetic library.

5 GNU Multiple Precision Arithmetic

One reason you should not use web applications to do your computing is that you lose control. It’s just as bad as using a proprietary program. Do your own computing on your own computer with your copy of a freedom - respecting program. If you use a proprietary program or somebody else’s web server, you’re defenceless.

—Richard Stallman

As you should know by now, C, unlike languages like Python, does not natively support arbitrary preci- sion integers. The security of SS, however, relies on large integers. So, we elect to use the GNU multiple precision arithmetic library, usually referred to as GMP. You can find the manual and documentation for 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:

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 SS. 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 inte- ger 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 mod- ule, 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. You should call srandom() using this seed as well. This function will also entail calls to gmp_randinit_mt() and 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().

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 SS before you can tackle your SS 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 an where both a,n e N for SS . We could simply multiply:

n

an = ╱a x a x ╱.↘ x a xa(`) .

The number of multiplications is n−1, which is O(n). While correct, this approach is naïve and extremely inefficient. Since we are working with very large numbers in SS, we must be able to compute modular exponentiation quickly. So the question is, can we do better? We can in fact do much better, computing an in O(log2 (n)) steps.

Recall that we can write any integer as a polynomial

n = cm2m + cm−12m−1 + ... + c121 + c020 = 渥 ci2i ,

0sism

where n 2 2m and cie(0,1). And so,

an = acm2m +cm一 12m一 1 +...+c121+c020 .

Since ab+c = ab x ac , then we can rewrite the formula as

an = acm2m  x acm一 12m一 1  x . . . x ac121  x ac020  = Ⅱ aci2i .

0sism

As an example, consider a13 = a23+22+20  = a8+4+1 = a8 x a4 x a1 . You will want to try a few more to get a feeling for it before you attempt to write code.

This leaves us with the problem of computing the a2i  terms. We start with a = a1 and if we square it then (a1 )2 = a2 . Each time we square, (a2 )2 = a4 , (a4 )2 = a8 , . . . the exponents are a power of 2. We only have to square our previous result log2 n times at most.

You will notice that the numbers get very large, very fast.  Although we want enormous numbers for cryptography, we do not want numbers that would be impossible to even write down if we used every atom in the universe.  Recall that 10k is k digits long.  That means that if k = 101000 then there are that many digits (there are approximately 1082 atoms in the observable universe).  Consequently, we will usually do such computations (mod n) for some modulus n, meaning that all numbers are in (0, . . . ,n − 1).

To implement modular exponentiation, you should simply follow the steps to perform exponentia- tion by squaring as shown above and reduce your results modulo n after each operation that is likely to yield a large result (you do not need to do it, if for example, you just add a small constant). The following pseudocode shows the repeated squaring and modular reduction at each step.

POWER -MOD(a,d,n)

1   v é 1

2   p é a

3 while d > 0

4 if ODD(d)

5                 v é (v x p)  mod n

6          p é (p x p)  mod n

7           d é ld/2l

8 return v

The function that you are expected to implement to perform modular exponentiation should be de- clared as follows:

void pow_mod(mpz_t out, mpz_t base, mpz_t exponent, mpz_t modulus)

Performs fast modular exponentiation, computing base raised to the exponent power modulo modulus, and storing the computed result in out.

6.2 Primality Testing

There are many methods—none of them as good as the randomized primality test.

—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,n. Thus, this simple algorithm1is O(,n), but can we do better? The answer is subtle. To be certain, we must try all of the primes from up to,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 proba- bility 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 an−1  (mod n).  If the result is different from 1, then n is composite. If it is 1, then n may be prime. If an−1 = 1 (mod n) n is not prime, then n is called a pseudoprime to base a. In practice, we observe that, if an−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 SS.

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 more sophisticated probabilistic test, which detect all composites (once again, this means: for every composite number n, at least of numbers a are witnesses of compositeness of n).  The accuracy of these tests is compared in Figure 5.

The Miller–Rabin primality test works as follows: Given an integer n, choose some positive integer a < n. Let 2s d = n −1, where d is odd. If ad \= +1 (mod n) and a2r d \= +1 (mod n) for all 0 s r s s −1, then n is composite and a is a witness for the compositeness. Otherwise, n might be prime. That is, we might be wrong of the time.  If we repeat the test 100 times then our chance of being wrong is

1 How big is ,n? A typical encryption key has more than 600 decimal digits. Thus, ^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 x 109 years ago).

Pr(prime)

1.0

0.9

0.8

Miller-Rabin

Solovay-Strassen

0.7

0.6