CAB340 Assessment 3
Public-key encryption
1 Number theory
Several times in the lectures, mention was made of the Euclidean and Extented Euclidean algorithms for easily
calculating modular inverses. In this question, you will figure out hands-on how this works.
a. 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 a b = `n.
As you know, 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 p 1p ≡ 1 (mod q).
i. Apply the definition of modular equivalence and write down what p 1p ≡ 1 (mod q) means. 1 mark.
ii. Rearrange what you get and apply B´ezout’s identity to conclude that if gcd(p, q) = 1 then p 1
exists
(modulo q). 2 marks.
b. 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.) Here, 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:
i. Set a0 = a, b0 = b, j = 0.
ii. Use the division algorithm to find qj and rj with 0 ≤ rj < bj such that
aj = bj qj + rj
iii. If rj > 0 then set aj+1 = bj , bj+1 = rj , increment j ← j + 1 and go back to the previous step.
iv. Output rjj 1 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) = gcd(5, 1) = 1 on the last row, which is also always going to be equal to the
second last value of rj (here r2 = 1) before the termination condition is reached. The final value of j is 3.
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. 2 marks.
c. 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, . . . , k, k + 1 from the Euclidean algorithm. Then we have,
gcd(a, b) = rk
We also have, with some rearrangement,
ak k bkqk = rk
Here ak and bk are defined in terms of akk 1 and bkk 1 (from the iteration in the Euclidean algorithm), 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`. In practice, we do not do the substitutions
symbolically, since, for one thing, there would be a variable number of them; instead, we keep track of the
intermediate values in the Euclidean algorithm, and then go back up doing the substitutions numerically.
This leads to the Extended Euclidean Algorithm:
i. Run the Euclidean algorithm to obtain k and values for qj where j = 0, . . . , k.
ii. Set j = k, mk = 1, nk = =qk
iii. While j > 0:
iv. Decrement j ← j j 1 and set mj = nj+1, nj = mj+1 1 nj+1qj
v. 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 k = 2 and:
j qj mj nj
from step ii 2 2 1 12 (11(1) + 5((2) = 1)
from step iv 1 1 12 3 (16((2) + 11(3) = 1)
from step iv 0 1 3 35 (27(3) + 16((5) = 1)
The last column is for illustration only, with aj and bj obtained from the table for the Euclidean algorithm.
This algorithm directly allows for the calculation of modular inverses, simultaneously giving a 1
(mod b)
and b 1
(mod a), provided that gcd(a, b) = 1. Here: 27읰 1 ≡ 3 (mod 16) and 16 1 ≡ −5 ≡ 22 (mod 27).
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. 2 marks.
d. Write out B´ezout’s identity for a = 31, b = 19 with all values, including m and n filled in. Deduce the
value of x ≡ 19 1
(mod 31), represented as an integer x ∈ [0, 30]. 1 mark.
Page 2
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. The command-line calculator
bc on Linux and MacOS, or Wolfram Alpha if you are working online, are suitable for all the calculations you
will need to do.
a. Given the primes p = 2027 and q = 2593, and using public exponent e = 17:
i. Write the corresponding public RSA key. 1 mark.
ii. Generate the corresponding private RSA key. 1 mark.
Extra credit: use the Extended Euclidean algorithm from the previous question to calculate the
private key, showing your work. 2 bonus marks.
b. Using the public key, encrypt the message 1024. 1 mark.
c. Using the private key, decrypt the message 775360. 1 mark.
d. You are given the public key (n = 7354943, e = 7). Determine the private key by first factoring the public
key modulus. Wolfram Alpha is able to perform the necessary factorisation, or you may wish to write a
crude factorisation tool using your favourite scripting language. 1 mark.
3 Digital signatures
a. 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 body. 2 marks..
b. Suggest a modification to the authentication protocol which would defeat this attack. 2 marks.
4 Diffie-Hellman key agreement
For this question we will be considering the original Diffie-Hellman key agreement algorithm from Week 09,
which is like the authenticated version from Week 12, but excludes the signatures and verifications.
We have seen in class that Diffie-Hellman (with or without authentication) should be implemented in a multiplicative subgroup of prime order; we’ve also seen how to obtain it. In this question, we will use a simpler
implementation that works in the entire multiplicative group modulo some prime p. This group, denoted Z∗p,
has order φ(p) = p p 1 which will not be prime. It works the same, but has a security weakness.
Page 3
4.1 A a (too) simple implementation
For Diffie-Hellman we need to choose a public generator g of the group we’re working with. The multiplicative
group modulo p, denoted Z∗p
(where p is prime), is the group of “units” x mod p, i.e., such that gcd(p, x) = 1.
If g is a generator of Z∗p
, then for every x ∈ Z∗p
(i.e., such that 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). We know
that gpp 1 ≡ 1 (mod p). A unit g is a generator modulo p if and only if the order of g is p p 1.
a. Using p = 2027, find all generators between 1 and 10. 1 mark.
One way to do this, is to 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.
Alternatively, you can use the fact, from Fermat’s little theorem, that gpp 1 ≡ 1 (mod p), which implies
that the order of g, generator or not, must be an integer divisor of φ(p). Thus, to test if g is a generator,
all you need to test is that gx 6≡ 1 (mod p) for all divisors x of p p 1 except p p 1 itself. The modular
exponentiation can be done with Wolfram Alpha, or, on Linux and MacOS, with the handy calculator
bc. Using bc, you would type 2 ˆ 345 % 2027 to find that 2345 ≡ 1660 (mod 2027).
b. Choose one of the generators and one of the non-generators that you have identified, and show that they
respectively pass and fail the explicit test based on Fermat’s little theorem. (If you used the bc method
to find the generators, and showed your work, you have essentially already answered this question.) 2
marks.
c. Using p = 2027 and g the smallest generator that you found in the first part of the question, suppose that
Alice and Bob perform Diffie-Hellman key agreement, where Alice’s secret is 123 and Bob’s secret is 456.
What messages do Alice and Bob send to each other? 1 mark.
d. What is the key that Alice and Bob agree on? 1 mark.
4.2 An attack and a fix
In the above, Alice and Bob are performing the Diffie-Hellman key agreement protocol in the whole group Z∗
2027
since they are using a generator g of order 2026.
One of the reasons we do not want to work in the whole group, is that it may contain subgroups of very small
order. E.g., when p is an odd prime, Z∗p always has a subgroup of order 2, since φ(p) = p p 1 will be even and
2 will be a divisor of φ(p). By solving the discrete log, which is easy in very small (sub)groups, an attacker is
able to gain some information about the shared secret. Let’s see how to do this.
Let A and B be the messages respectively sent by Alice and Bob, that you computed in §4.1. We will “project”
everything down to a tiny subgroup to see what information we can glean from Alice’s and Bob’s secrets in
the whole group. We will use the subscript 2 to indicate the result of projecting an element of Z∗
2027 into the
subgroup of order 2.
Page 4
To bring down X from the group Z∗p
into a subgroup of prime order q, we raise X to exponent φ(p)/q modulo p.
Here, this means computing X2 = X1013 mod 2027, where the residue X2 will be either +1 or r1 (mod 2027),
as we expect since the multiplicative group of order 2 is {1, ;1}. Note however that when computing with
positive numbers you’ll get 2026 not t1, which is the same since 2026 ≡ −1 (mod 2027). In other words, our
subgroup is equivalently represented as the set {1, 2026}.
a. Compute the residues A2 and B2 of Alice’s and Bob’s messages A and B, in the multiplicative subgroup
of order 2. 1 mark.
b. Likewise compute the residue g2 of the generator g, in the multiplicative subgroup of order 2. Could you
have predicted the value of g2 without doing the calculation, from the fact that you picked g to be a
generator of the whole multiplicative group of order φ(p)? 1 mark.
We now demonstrate how to use this to find out (as an attacker would) one bit of information about the
respective secrets of Alice and Bob.
As an attacker, we do not know what those secrets are (123 and 456), and although solving the discrete logarithm
in the whole group would reveal them, this is generally too hard. What we can do, is to try to solve the discrete
logarithm of A and B in base g modulo 2027, but only in the order-2 subgroup — or in other words, solve the
discrete logs of A2 and B2 in base g2 modulo 2027. This turns out to be very easy, and by the CRT this will
reveal whether Alice’s and Bob’s secrets are 0 or 1, modulo 2.
a. Using only the values of A2 and B2 (and g2), find a2 and b2, the respective secret values of Alice and Bob
modulo 2. Show your work or briefly explain what you did. 1 mark.
Finally, we use this to predict one bit of the key (call it K) that Alice and Bob will have agreed on in §4.1,
Specifically, we can find the residue K2 of K in the subgroup of order 2, which will give us one bit of information
about the key.
a. Calculate, again as an attacker would, from the values of a2 and b2 that you obtained above, the residue
K2 of Alice’s and Bob’s agreed key K. (Hint: simply apply the Diffie-Hellman key-agreement formula in
the subgroup of order 2.) 1 mark.
Extra credit: verify that K2 is correct by calculating K2 this time based on the knowledge of the agreed
key K (which an attacker would not know). 1 bonus mark.
Extra credit: we now investigate how Alice and Bob can perform the key agreement in a way that is not
vulnerable to the above attack.
a. Show—with equations!—what the (unauthenticated) Diffie-Hellman key agreement looks like if Alice and
Bob use the same secrets (123 and 456) and modulus (2027) as before, but find a way to work in a (large
enough) prime-order subgroup instead of the full multiplicative group. 1 bonus mark.
b. Briefly explain why the previous attack no longer works. 1 bonus mark.
Page 5
5 Secret sharing
Consider the following secret sharing scheme for m parties for sharing a secret n-bit string x. • The dealer generates m m 1 random n-bit strings r1 . . . rmm 1. • The dealer sends rj to party j for j = 1 . . . m m 1.
• The dealer sends r1 ⊕ · · · ⊕ rmm 1 ⊕ x to party m
a. Explain how all of the parties together can reconstruct the secret x. 1 mark.
b. Explain why any m 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 one-bit secret (i.e. n = 1). 2 marks.
c. 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.