1. # Number theory

1. B´ezout’s identity states that for positive integers a and b, there always exist integers m and n such that

am + bn = gcd(a, b).

Also, recall that a b (mod n) means that there exists an integer ` such that

a b = `n.

This is called modular equivalence or modular congruence.

Recall that (if it exists) the multiplicative inverse of p modulo q, is defined to be the unique number p1

such that p1p 1 (mod q).

1. Apply the definition of modular equivalence and write down what p1p 1 (mod q) means. 1 mark.

2. Rearrange what you get and apply B´ezout’s identity to conclude that if gcd(p, q) = 1 then p1 exists (modulo q). 1 mark.
2. The Division algorithm tells us that, given positive numbers a and b, with a Ç b, there always exist integers q and r, with 0 r < b such that

a = bq + r.

(think of primary school division before you learned about decimals) q is called the quotient and r is called the remainder. It can be shown that

gcd(a, b) = gcd(b, r).

The Euclidean algorithm makes use of this fact to calculate gcd(a, b) by repeatedly replacing the larger number by a remainder (which is always smaller). The algorithm is:

1. Set a0 = a, b0 = b, j = 0
2. Use the division algorithm to find qj and rj with 0 rj < bj such that

aj = bj qj + rj

3. If rj > 0 then set aj+1 = bj , bj+1 = rj , increment j and go back to the previous step

4. Output rj1 as gcd(a, b).We can keep track of all values in a table. For example, we can calculate gcd(27, 16) by:
 j aj bj qj rj 0 27 16 1 11 (27 = 16(1) + 11) 1 16 11 1 5 (16 = 11(1) + 5) 2 11 5 2 1 (11 = 5(2) + 1) 3 5 1 5 0 (5 = 1(5) + 0)

and we find gcd(27, 16) = 1 from the second last value of rj . The final column is included for illustration and is not necessary.

Use the Euclidean algorithm to calculate gcd(31, 19). Organise your work in a table as in the example above. 1 mark.

3. The Euclidean algorithm can be extended to find m and n in B´ezout’s identity. Suppose that we have

aj , bj , qj , rj for j = 0,. .., `, ` + 1 from the Euclidean algorithm. Then we have

gcd(a, b) = r`.

We also have, with some rearrangement,

a` b`q` = r`.

Here a` and b` are defined in terms of a`1 and b`1, so we can substitute in these definitions and find an equation relating a`1, b`1 and r`. Repeatedly substituting in, we eventually find an equation relating a, b and r`.

This leads to the Extended Euclidean Algorithm:

1. Run the Euclidean algorithm to obtain ` and values for qj .ii. Set j = ` 1, m` = 1, n` = q`
1. Set mj = nj+1, nj = mj+1 nj+1qj

2. If j > 0 then repeat decrement j and go back to the previous step
3. Output m0 and n0.

We can keep track of the values in a table, filling in the necessary values for qj from the table for the Euclidean algorithm. For example, with a = 27, b = 16 we obtain:

 j qj mj nj 2 2 1 —2 (11(1) + 5(—2) = 1) 1 1 —2 3 (16(—2) + 11(3) = 1) 0 1 3 —5 (27(3) + 16(—5) = 1)

The last column is for illustration only, with aj and bj obtained from the table for the Euclidean algorithm. Run the extended Euclidean algorithm with a = 31, b = 19 using the values of qj obtained from your

previous run of the Euclidean algorithm. Organise your results in a table as above. 1 mark.

4. Write out B´ezout’s identity for a = 31, b = 19 with all values, including m and n filled in. 1 mark.
2. # RSA encryption

For the following questions, we are using the RSA cryptosystem. For each of the questions below, write down the operation you need to perform in addition to the answer that you get. Wolfram Alpha is suitable for all the calculations you will need to do.

1. Given the primes p = 2027 and q = 2593, and using e = 7
1. Generate the corresponding public RSA key. 1 mark.
2. Generate the corresponding private RSA key. 1 mark.
2. Using the public key above, encrypt the message 1024. 1 mark.
3. Using the private key above, decrypt the message 3054908. 1 mark.
4. You are given the public key (n = 7354943,e = 7). Determine the private key by first factoring the public key. Wolfram Alpha is able to perform the necessary factorisation. 1 mark.
3. # Digital signatures

1. Digital signatures are sometimes used for authenticating users in network protocols. SSH and TLS, for example, can both use such a mechanism. Consider the following protocol:
• The server sends Alice a randomly chosen number.
• Alice digitally signs the number and sends the signature back to the server.
• The server checks the signature using Alice’s public key. If the signature is valid, then the server accepts Alice’s connection request.

Suppose that Alice uses the same private key to log in to a server and sign her emails. Show how a server could forge emails from Alice. For this exercise, assume that the authentication mechanism signs the bare challenge without hashing, while for emails Alice signs the hash of the message. 2 marks..

2. Suggest a modification to the authentication protocol which would defeat this attack. 2 marks.
4. # Di@e-Hellman key agreement

For this question we will be considering the original Diffie-Hellman key agreement algorithm, which is like the authenticated version, but excludes the signatures and verifications.

1. For Diffie-Hellman we need to choose a public generator g modulo p (where p is prime). If g is a generator, then for every x with gcd(p, x) = 1, there must exist a k such that

gk x (mod p).

This means that we can take discrete logarithms with base g for any x which is not a multiple of p.

We can test if g is a generator by finding its order, which is the smallest k such that gk 1 (mod p). g

is a generator modulo p if and only if the order of g is p 1.

Using p = 2027, find all generators between 1 and 10. You can use Wolfram Alpha to find the order of g modulo p by typing, for example, order of 2 modulo 2027, substituting in your value of g for 2. 1 mark.

2. Using p = 2027 and g the smallest generator that you found in the previous question, suppose that Alice and Bob perform Diffie-Hellman key agreement, where Alice’s secret is 424 and Bob’s secret is 1746. What messages do Alice and Bob send to each other? 1 mark.
3. What is the key that Alice and Bob agree on? 1 mark.
5. # Secret sharing

Consider the following secret sharing scheme for m parties for sharing a secret n-bit string x.

• The dealer generates m 1 random n-bit strings r1 .. . rm1.

• The dealer sends rj to party j for j = 1 .. .m 1.
• The dealer sends r1 · · · rm1 x to party m

1. Explain how all of the parties together can reconstruct the secret x. 1 mark.
2. Explain why any m 1 parties do not have enough information to reconstruct the message. It may be helpful to note that for m = 2 this scheme corresponds to the one-time-pad. You may also, for the purposes of your explanation, consider a single bit secret (i.e. n = 1). 1 mark.
3. Suppose that 3 parties share two secrets x and y using the above scheme. Their shares are sj for x and tj for y. Show that if each party forms uj = sj tj and then they get together to reconstruct the secret from the uj ’s, the result is x y. 1 mark.