Home Page > > Details

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.

Contact Us(Ghostwriter Service)

- QQ：99515681
- WeChat：codinghelp2
- Email：99515681@qq.com
- Work Time：8:00-23:00

- Tsp Course Assignmentghostwriter ,Help... 2020-06-23
- Kit107 Assignmenthelp With ,C++ Progra... 2020-06-23
- Sta302h1f Assignmenthelp With ,Ghostwr... 2020-06-22
- Ghostwriter Seng 474 Assignment,Help W... 2020-06-22
- Cmpsci 187 Binary Search Trees 2020-06-21
- Comp226 Assignment 2: Strategy 2020-06-21
- Math 504 Homework 12 2020-06-21
- Math4007 Assessed Coursework 2 2020-06-21
- Optimization In Machine Learning Assig... 2020-06-21
- Homework 1 – Math 104B 2020-06-20
- Comp1000 Unix And C Programming 2020-06-20
- General Specifications Use Python In T... 2020-06-20
- Comp-206 Mini Assignment 6 2020-06-20
- Aps 105 Lab 9: Search And Link 2020-06-20
- Aps 105 Lab 9: Search And Link 2020-06-20
- Mech 203 – End-Of-Semester Project 2020-06-20
- Ms980 Business Analytics 2020-06-20
- Cs952 Database And Web Systems Develop... 2020-06-20
- Homework 4 Using Data From The China H... 2020-06-20
- Assignment 1 Build A Shopping Cart 2020-06-20

Contact Us - Email：99515681@qq.com WeChat：codinghelp2

© 2014 www.asgnhelp.com

Programming Assignment Help！