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 handson how this works.
a. B ezouts identity states that for positive integers a and b, there always exist integers m and n such that ambngcda, b.
Also, recall that ab mod n means that there exists an integer l such that abln.
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 p1p1 mod q.
i. Apply the definition of modular equivalence and write down what p1p1 mod q means. 1 mark.
ii. Rearrange what you get and apply B ezouts identity to conclude that if gcdp, q1 then p1 exists modulo q. 2 marks.
Division algorithm tells us that, given positive numbers a and b, with ab, there always exist abqr.
b. The
integers q and r, with 0rb such that
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
gcda, bgcdb, r.
The Euclidean algorithm makes use of this fact to calculate gcda,b by repeatedly replacing the larger
number by a remainder which is always smaller. The algorithm is: i. Seta0 a,b0 b,j0.
ii. Use the division algorithm to find qj and rj with 0rjbj such that aj bjqj rj
iii. Ifrj 0thensetaj1 bj,bj1 rj,incrementjj1andgobacktothepreviousstep. iv. Output rj1 as gcda, b.
CAB340 Assessment 3 Publickey encryption
We can keep track of all values in a table. For example, we can calculate gcd27, 16 by:
j aj bj qj rj
0 27 16 1 11 2716111 1 16 11 1 5 161115 2 11 5 2 1 11521 3 5 1 5 0 5150
and we find gcd27,16gcd5,11 on the last row, which is also always going to be equal to the second last value of rj here r21 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 gcd31, 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 ezouts identity. Suppose that we have aj,bj,qj,rj forj0,…,k,k1fromtheEuclideanalgorithm. Thenwehave,
We also have, with some rearrangement,
gcda, brk ak bkqk rk
Here ak and bk are defined in terms of ak1 and bk1 from the iteration in the Euclidean algorithm, so we can substitute in these definitions and find an equation relating al1, bl1 and rl. Repeatedly substituting in, we eventually find an equation relating a, b and rl. 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 j0, . . . , k. ii. Setjk,mk 1,nk qk
iii. While j0:
iv. Decrementjj1andsetmj nj1,nj mj1nj1qj
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 a27, b16, we obtain k2 and:
j qj mj nj
from step ii 2 2 1 2 111521
fromstepiv 1 1 2 3 1621131 fromstepiv 0 1 3 5 2731651
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 a1 mod b
and b1 mod a, provided that gcda, b1. Here: 2713 mod 16 and 161522 mod 27. Run the extended Euclidean algorithm with a31, b19 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 ezouts identity for a31, b19 with all values, including m and n filled in. Deduce the
value of x191 mod 31, represented as an integer x0, 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 commandline 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.
3
a.
b. c. d.
a.
Given the primes p2027 and q2593, and using public exponent e17:
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.
Using the public key, encrypt the message 1024. 1 mark.
Using the private key, decrypt the message 775360. 1 mark.
You are given the public key n7354943, e7. 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.
Digital signatures
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 Alices public key. If the signature is valid, then the server accepts Alices 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..
Suggest a modification to the authentication protocol which would defeat this attack. 2 marks.
DiffieHellman key agreement
4
b.
For this question we will be considering the original DiffieHellman 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 DiffieHellman with or without authentication should be implemented in a mul tiplicative subgroup of prime order; weve 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 Zp, has order pp1 which will not be prime. It works the same, but has a security weakness.
Page 3
4.1 A a too simple implementation
For DiffieHellman we need to choose a public generator g of the group were working with. The multiplicative group modulo p, denoted Zp where p is prime, is the group of units x mod p, i.e., such that gcdp,x1. If g is a generator of Zp , then for every xZp i.e., such that gcdp, x1, there must exist a k such that
gkx modp.
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 gk1 mod p. We know thatgp1 1 modp. Aunitgisageneratormodulopifandonlyiftheorderofgisp1.
a. Using p2027, 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 Fermats little theorem, that gp11 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 gx1 mod p for all divisors x of p1 except p1 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 23452027 to find that 23451660 mod 2027.
b. Choose one of the generators and one of the nongenerators that you have identified, and show that they respectively pass and fail the explicit test based on Fermats 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 p2027 and g the smallest generator that you found in the first part of the question, suppose that Alice and Bob perform DiffieHellman key agreement, where Alices secret is 123 and Bobs 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 DiffieHellman key agreement protocol in the whole group Z2027 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, Zp always has a subgroup of order 2, since pp1 will be even and 2 will be a divisor of p. By solving the discrete log, which is easy in very small subgroups, an attacker is able to gain some information about the shared secret. Lets 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 Alices and Bobs secrets in the whole group. We will use the subscript 2 to indicate the result of projecting an element of Z2027 into the subgroup of order 2.
Page 4
To bring down X from the group Zp into a subgroup of prime order q, we raise X to exponent pq modulo p. Here, this means computing X2X1013 mod 2027, where the residue X2 will be either 1 or 1 mod 2027, as we expect since the multiplicative group of order 2 is 1,1. Note however that when computing with positive numbers youll get 2026 not 1, which is the same since 20261 mod 2027. In other words, our subgroup is equivalently represented as the set 1, 2026.
a. Compute the residues A2 and B2 of Alices and Bobs 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 order2 subgroupor 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 Alices and Bobs 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 Alices and Bobs agreed key K. Hint: simply apply the DiffieHellman keyagreement 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. Showwith equations!what the unauthenticated DiffieHellman 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 primeorder 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 nbit string x.
The dealer generates m1 random nbit strings r1 . . . rm1 .
Thedealersendsrj topartyjforj1…m1.
The dealer sends r1 rm1 x to party m
a. Explain how all of the parties together can reconstruct the secret x. 1 mark.
b. Explain why any m1 parties do not have enough information to reconstruct the message. It may be helpful to note that for m2 this scheme corresponds to the onetimepad. You may also, for the purposes of your explanation, consider a onebit secret i.e. n1. 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 ujsjtj and then they get together to reconstruct the secret from the ujs, the result is xy. 1 mark.
Page 6
Reviews
There are no reviews yet.