## Description

**Problems 1-5,**

**Problem 8 only**

Written Problems for CPSC 418 and MATH 318

Problem 1 — Flawed MAC designs (11 marks)

For this problem, you need to carefully trace through the given MAC algorithms, and specifically

through the underlying iterated hash function, to understand the given attacks and explain how

computation resistance is defeated.

Recall that iterated hash functions employ a compression function f in multiple rounds; SHA-1

is an example of such a hash function. Here, f takes as input pairs of n-bit blocks and outputs

n-bit blocks, for some n ∈ N. The compression function f is assumed to be public, i.e. anyone

can compute values of f. As a result, the hash function is also public, so any one can compute

hash values. For simplicity, we assume that the bit length of any message to be hashed is a

multiple of n, i.e. messages have been padded appropriately prior to hashing. Then the input to an

iterated hash function is a message M consisting of L blocks P1, P2, . . . , PL, each of length n. An

algorithmic description of an n-bit iterated hash function is given as follows (as usual. “k” denotes

concatenation of strings).

Algorithm ItHash

Input: A message M = P1kP2k · · · kPL

Output: An n-bit hash of M

1: Initialize H := 0n (n zeros)

2: for i = 1 to L do

3: H := f(H, Pi)

4: end for

5: Output H

This problem demonstrates that the two “obvious” designs for using an iterated hash function as

the basis for a MAC — prepending or appending the key to the message and then hashing — are

not secure. You will prove this by mounting specific attacks that defeat computation resistance.

For simplicity, assume that keys also have length n, the same as the message block length.1

a. (5 marks) Define a message authentication function PHMAC (“Prepend Hash MAC ”) via

PHMACK(M) := ItHash(KkM) = ItHash(KkP1kP2k · · · kPL)

for any message M = P1kP2k · · · kPL.

Suppose an attacker knows a message/PHMAC pair (M1,PHMACK(M1)). Let X be an arbitrary n-bit block and put M2 = M1kX. Show how an attacker can compute PHMACK(M2)

without knowledge of K, thereby defeating computation resistance for PHMAC.

Hint: Let M1 = P1kP2k · · · kPL. Tracing through the ItHash algorithm, compare the results of

the first L + 1 rounds of ItHash(KkM1) and ItHash(KkM2). Then explain how the attacker

can compute PHMACK(M2) from ItHash(KkM2) without knowledge of K.

1The attack in part (a) will in fact work for any key length, but for part (b), this key length restriction is required.

2

b. (6 marks) Define a message authentication function AHMACK (“Append Hash MAC ”) via

AHMACK(M) := ItHash(MkK) = ItHash(P1kP2k · · · kPLkK)

for any message M = P1kP2k · · · kPL.

Assume that ItHash is not weakly collision resistant, and suppose an attacker knows a message/AHMAC pair (M1, AHMACK(M1)). Show how she can find (without knowledge of K) a

second message/AHMAC pair (M2, AHMACK(M2)), thereby defeating computation resistance.

Hint: Note that on input any L-bit message, the first L rounds of the computation of AHMACK(M)

do not depend on K, just on M.

Problem 2 — Fast RSA decryption using Chinese remaindering (7 marks)

In this problem, as usual, a user Alice has an RSA public key (e, n) with corresponding private key

d. Here, n = pq for distinct large primes p and q.

If Alice does not discard p and q after computing n and φ(n), she can employ an alternative

decryption procedure as described below (based on the Chinese Remainder Theorem which some

of you may have seen before). For a given ciphertext C (1 ≤ C ≤ n−1, gcd(C, n) = 1), she proceeds

as follows:

Step 1. Compute

dp ≡ d (mod p − 1), 0 ≤ dp ≤ p − 2 ,

dq ≡ d (mod q − 1), 0 ≤ dq ≤ q − 2 .

Step 2. Compute

Mp ≡ C

dp

(mod p), 1 ≤ Mp ≤ p − 1 ,

Mq ≡ C

dq

(mod q), 1 ≤ Mq ≤ q − 1 .

Step 3. Use the Extended Euclidean Algorithm to find integers x, y such that

px + qy = 1 .

(Such integers exist because gcd(p, q) = 1.)

Step 4. Set M ≡ pxMq + qyMp (mod n), 0 ≤ M ≤ n − 1.

Prove that if the above procedure decrypts correctly. That is, if C ≡ Me

(mod n) is a ciphertext

obtained by encrypting a message M the “normal” RSA way, and M0

is the result of applying the

procedure above to C, prove that M0 = M.

Hint: You may use without proof the fact that a ≡ b (mod n) if and only if a ≡ b (mod p) and

a ≡ b (mod q) for any a, b ∈ Z. The “only if” direction follows directly from the definition of

congruence; the “if” direction follows from the Chinese Remainder theorem.

Remark: This method performs two modular exponentiations for decryption (in step 2), as opposed

to just one modular exponentiation for the ordinary RSA decryption procedure. However, the

moduli p and q have only about half the bit length of n, and the exponents dp and dq generally

have about half the bit length of d (as d / n, dp / p and d1 / q). Since the computational effort of

steps 1, 3 and 4 is negligible compared to step 2, Chinese remainder decryption is generally almost

four times as fast as ordinary RSA decryption. So this is what is generally used in practice.

3

Problem 3 — RSA primes too close together (21 marks)

This problem explores a difference of squares approach to factoring an RSA modulus due to Fermat, which is hence also known as Fermat factorization. Fermat’s idea was to attempt to find a

representation of an integer n as a difference of squares n = x

2 − y

2 where 0 < y < x < n, which

leads to a factorization n = (x + y)(x − y). When n is an RSA modulus whose prime factors are

very close together, the quantity y is very small compared to x and we will see that this gives rise

to a serious factoring attack on RSA.

Let n = pq with odd primes p, q, and assume without loss of generality that p > q. As always, all

square roots are positive, i.e. when we write √

z for some z > 0, we mean the positive square root

of z.

a. (4 marks) Prove that if x, y are integers with x > y > 0 and n = x

2 − y

2

, then

x =

n + 1

2

, y =

n − 1

2

or x =

p + q

2

, y =

p − q

2

. (1)

Note that it is not enough to prove that these given values for x and y satisfy n = x

2 − y

2

. The

point is to prove that there are no integer values for x and y other than the ones given here.

b. (2 marks) Prove that p + q < n + 1.

c. (3 marks) Use the inequality p > q to prove that √

n <

p + q

2

< p.

d. (4 marks) The idea for factoring n is to iterate over integers x that are potential candidates

for (p + q)/2, starting with the smallest integer exceeding √

n (the lower bound from part (c))

and searching in increments of 1 until a value x is found for which y := √

x

2 − n is an integer.

The assertion (which requires proof!) is that x = (p + q)/2 and y = (p − q)/2, in which case

the method returns the factor x − y = q. Here is pseudocode for this factorization algorithm:

Algorithm Fermat Factorization

Input: n = pq with p > q

Output: q

1: Put x = d

√

n e

√

n rounded up to the nearest integer

2: y := √

x

2 − n

3: while y is not an integer do

4: x := x + 1; y := √

x

2 − n

5: end while

6: Output x − y.

Use parts (a)-(c) to prove that this algorithm terminates s soon as x = (p + q)/2 and outputs

q. Note that there are three things to show here:

• The “while” condition is satisfied when x = (p + q)/2;

• x = (p + q)/2 is the first value that satisfies the “while” condition;

• The algorithm outputs q.

e. (2 marks) Show that the “while” condition in step 3 is tested x − d√

n e + 1 times, where

x = (p + q)/2.

f. (4 marks) Prove that x − d√

n e <

y

2

2

√

n

where x = (p + q)/2 and y = (p − q)/2.

Hint: Find a suitable upper bound on (x −

√

n)(x +

√

n) and divide by x +

√

n. Prove that the

result yields a bound on x − d√

n e.

g. (2 marks) Finally, the coup-de-grˆace. Suppose p − q < 2B

√4 n for some integer B that is very

small compared to n; e.g. B could be on the order of a power of log2

(n) or even a constant

number. In other words, p and q are very close together; they agree in nearly half of their most

significant bits. Prove that the above algorithm factors n after at most

B2

2

+ 1

steps, where a step corresponds the an evaluation of the “while” condition in step 3.

Problem 4 — El Gamal is not semantically secure (12 marks)

This problem requires typesetting Legendre symbols. To facilitate this, include at the beginning of your assignment file, right after the line \documentclass{…} the two lines

\usepackage{amsmath}

\providecommand{\Leg}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

Be sure that you copy these verbatim; the easiest is to copy and paste them right from this

PDF file. The assignment template provided on the Piazza Resourcesd page already includes

these lines. The command $\Leg{a}{n}$ will produce the typeset output

a

n

, which is much

easier than producing a fraction with large parentheses around it.

Recall that for the El Gamal public key cryptosystem, a user Alice produces her public and private

keys as follows:

Step 1. Selects a large prime p and a primitive root g of p.

Step 2. Randomly selects x such that 0 < x < p − 1 and computes

y ≡ g

x

(mod p).

Alice’s public key is {p, g, y}

Alice’s private key is {x}

To encrypt a message M ∈ Z

∗

p

intended for Alice, Bob selects a random integer k ∈ Zp−1, computes

C1 ≡ g

k

(mod p) and C2 ≡ Myk

(mod p), and sends C = (C1, C2) to Alice.

Alice decrypts the ciphertext C = (C1, C2) by computing C2C

p−1−x

1 ≡ M (mod p).

In this problem, you will prove that the El Gamal public key cryptosystenm is not polynomially

secure, and hence not semantically secure. This is because an attacker Mallory can distinguish

messages according to whether they are quadratic residues or quadratic nonresidues modulo p.

Mallory mounts her attack with the following procedure:

Step 1. Selects two messages M1 and M2 such that M1 ∈ QRp and M2 ∈ QNp, and obtains

the ciphertext C = (C1, C2) = E(Mi) where i = 1 or 2.

(Mallory’s task is precisely to ascertain whether i = 1 or i = 2.)

Step 2. Computes the Legendre symbols

y

p

,

C1

p

and C2

p

.

Step 3. If

y

p

= 1 and C2

p

= 1, she asserts that C = E(M1).

If

y

p

= 1 and C2

p

= −1, she asserts that C = E(M2).

If

y

p

= −1, C1

p

= 1 and C2

p

= 1, she asserts that C = E(M1).

If

y

p

= −1, C1

p

= 1 and C2

p

= −1, she asserts that = E(M2).

If

y

p

= −1, C1

p

= −1 and C2

p

= 1, she asserts that C = E(M2).

If

y

p

= −1, C1

p

= −1 and C2

p

= −1, she asserts that C = E(M1).

Note that this procedure requires three Legendre symbol computations — which can be done with

modular exponentiation by Euler’s Criterion — and hence always takes polynomial time. Note also

that Mallory states her assertions with certainty, i.e. probability 1.

Prove that Mallory’s assertions are correct, so the El Gamal system is not semantically secure.

Problem 5 — An IND-CPA, but not IND-CCA secure version of RSA (12 marks)

Consider the following semantically secure variant of the RSA public key cryptosystem:

Parameters:

• m — length of plaintext messages to encrypt (in bits)

• (n, e) — Alice’s RSA public key (n has k bits)

• d — Alice’s RSA private key

• H : {0, 1}

k

7→ {0, 1}

m a public random function

Encryption of an m-bit message M ∈ Zn∗:

Step 1. Generate a random k-bit number r < n.

Step 2. Compute C = (sk t) where s ≡ r

e

(mod n) and t = H(r) ⊕ M.

Decryption of a ciphertext C = (skt):

Step 1. Separate C into s and t.

Step 2. Compute M ≡ H(s

d

(mod n)) ⊕ t.

Prove that this cryptosystem is not IND-CCA secure.

Hint: To mount her CCA, Mallory gets to choose two plaintexts and submit a ciphertext C

0

for

decryption. Almost any two plaintexts M1, M2 will do. Let

C = (sk t) = (r

e

(mod n) k H(r) ⊕ Mi)

be the encryption of one them; Mallory needs to ascertain whether i = 1 or i = 2. Mallory chooses

the ciphertext C

0 = (sk t ⊕ M1) and obtains its decryption (make sure that C

0 6= C; that’s a

requirement in the CCA). Now trace through the decryption method applied to C and use the

result to figure out how Mallory can detect whether C is the encryption of M1 or M2. (Of course

Mallory can’t actually decrypt C, but she/you can still apply the decryption method symbolically

to C.)

Written Problems for MATH 318 only

Problem 6 — A primality test of sorts (12 marks)

Let N be an integer withN > 1. In this problem, you will prove the assertion

(N − 1)! ≡ −1 (mod N) if and only if N is prime (2)

and analyze its suitability for primality testing.

For the primes N = 2 and N = 3, it is easy to verify that (2) holds, so assume henceforth that

N ≥ 4. Note that in this case, 1 and −1 are distinct elements in ZN as 1 ≡ −1 (mod N) implies

that N divides 1 − (−1) = 2, forcing N = 2.

a. (3 marks) Suppose N is prime and let g be primitive root of N. Prove that

g

(N−1)/2 ≡ −1 (mod N) .

You may use without proof the fact if a prime divides the product of two non-zero integers,

then it divides one of the factors.

b. (3 marks) Suppose N is prime. Prove that (N − 1)! ≡ −1 (mod N).

Hint: Primitive roots. Remember that for any primitive g of N, the set Z

∗

N consists precisely

of the powers g

k

(mod N) with0 ≤ k ≤ N − 2.

c. (3 marks) Suppose N is composite. Prove that (N − 1)! 6≡ −1 (mod N).

Hint: Consider (N − 1)! modulo some prime divisor of N and draw the necessary conclusion

about (N − 1)! (mod N).

d. (3 marks) By parts (b) and (c), the congruence (N − 1)! ≡ −1 (mod N) can be used as a

primality test, actually even as a primality proof. Do you think this is a good primality test?

How does this compare, for example, to trial division (dividing N successively by 2, 3, 4, . . .)?

Give a yes/no answer and a concise, coherent and convincing explanation of your answer.

Remark: A wrong answer is “No because (N − 1)! is a really big number.” This is true,

but we are doing modular arithmetic here. The intermediate operands in the computation of

(N − 1)! (mod N) can be kept bounded by reducing modulo N in each step, i.e. by computing

FN−1 ≡ (N − 1)! (mod N) via the recurrence F0 = 1 and Fn ≡ nFn−1 (mod N) for 1 ≤ n ≤

N − 1.

7

Problem 7 — An attack on RSA with small decryption exponent (25 marks)

This problem explores an attack on RSA with small private key d.

Preliminaries. Let r be a positive rational number and write r = a/b with a, b ∈ N. Let

q0, q1, . . . qm ∈ N be the sequence of quotients produced by applying the Euclidean Algorithm to

the numerator and denominator of r:

a = q0b + r0 , 0 < r0 < b ,

b = q1r0 + r1 , 0 < r1 < r0 ,

r0 = q2r1 + r2 , 0 < r2 < r1 ,

.

.

.

rm−3 = qm−1rm−2 + rm−1 , rm−1 = gcd(a, b),

rm−2 = qmrm−1 + rm , rm = 0 .

Recall the familiar sequences

A−2 = 0, A−1 = 1, Ai = qiAi−1 + Ai−2 for 0 ≤ i ≤ m,

B−2 = 1, B−1 = 0, Bi = qiBi−1 + Bi−2 for 0 ≤ i ≤ m.

The quotients Ai/Bi (0 ≤ i ≤ m) are called the convergents of r because they oscillate around

and converge toward r as i increases, with Am = a, Bm = b, and hence Am/Bm = r. In fact, the

following theorem (which you may use without proof) asserts that any rational number sufficiently

close to r must occur as one of the convergents:

Theorem. Let r =

a

b

∈ Q with a, b > 0, and let A

B

∈ Q be a fraction in lowest terms such that

r −

A

B

<

1

2B2

. Then A = Ai and B = Bi for some i ∈ {0, 1, . . . , m}.

Now back to RSA. Let n = pq where p, q are odd primes satisfying

q < p < 2q .

These inequalities are reasonable as p and q are usually assumed to have the same bit length. Let

e, d be integers with 1 < e, d < φ(n) and ed ≡ 1 (mod φ(n)). Let k ∈ Z satisfy ed = 1 + kφ(n) and

suppose that d is small compared to n; specifically,

d <

√4 n

√

6

. (3)

a. (5 marks) Prove that 1 ≤ k < d and gcd(d, k) = 1.

b. (3 marks) Prove that 2 ≤ n − φ(n) < 3

√

n.

c. (4 marks) Use parts (a) and (b) to prove that 0 < kn − ed < 3d

√

n.

d. (4 marks) Conclude from part (c) and the upper bound (3) on d that 0 <

k

d

−

e

n

<

3

√

n

<

1

2d

2

.

8

e. (3 marks) Let q0, q1, . . . , qm be the quotients obtained when applying the Euclidean algorithm

to e and n, and let Ai

, Bi be the associated sequences as defined above. Use the theorem from

above to prove that k = Ai and d = Bi for some i ∈ {0, 1, . . . , m}.

f. (6 marks) Use part (e) to devise a procedure for finding d efficiently. Explain why your procedure

works and why it is efficient, i.e. argue that the number of computation steps performed by

your procedure is small.

Programming Problem for CPSC 418 only

Problem 8 — Secure file transfer with prior key agreement (37 marks)

Don’t be daunted by the long description of this problem! Most of it is very clear specifications,

including those for the autograder, to make your life easier.

Overview. Transport Layer Security (TLS) is a security protocol which aims to provide end-to-end

communication security over networks. It provides both privacy and data integrity. TLS has many

steps, but our focus will be the cipher suite, a set of algorithms that add cryptographic security to

a network connection. There are four main components to a cipher suite:

• Key Exchange Algorithm

• Authentication Algorithm (signature)

• Bulk Encryption Algorithm (block cipher and mode of operation)

• Message Authentication Algorithm

Cipher suites are specified in shorthand by a string such as

SRP-SHA3-256-RSA-AES-256-CBC-SHA3-256.

• This implies SRP-SHA3-256 as the key exchange algorithm, RSA signatures for authentication, AES-256-CBC for encryption and SHA3-256 as the MAC (used as HMAC).

• SRP is the protocol implemented in Assignment 2. The hash function used in the protocol is

specified as SHA3-256.

• SHA3-256 as the MAC implies the use of HMAC with SHA3-256.

In a TLS handshake, upon connection two parties automatically negotiate TLS settings, including

the cipher suite to use. Through an exchange of messages the two parties verify each other and

establish a session key. In this assignment, the two parties will be a server and client. The server

will authenticate itself to the client by means of a certificate, and if successful, will derive a shared

session key. The two parties are then able to use the session key to exchange encrypted and

authenticated messages.

In reality, a certificate is an electronic document which contains a public key and information about

the owner of the key. The certificate must be signed by a trusted authority to verify the contents

of the certificate. For us, the certificate will merely be a name concatenated with a public key,

concatenated with the signature of a trusted third party (TTP).

9

For this assignment, your task is to implement a toy version of the TLS handshake using the cipher

suite specified above.2 The protocol will have two parties a Client and Server, which rely on a

certificates provided by a TTP.

To execute the protocol, the Client and Server first need to obtain certificates from the TTP. We

perform a simplified version of this process as follows:

The TTP initializes in the following manner:

• Generates two RSA primes p and q of size 512-bits and computes N = pq.

• Generates its own RSA key-pair (N, e) and (N, d).

• Opens a socket connection on a specified IP and port and attempts to receive a single byte,

whose value indicates the TTP response. This byte is limited to the UTF-8 encoding of the

characters ‘s’ indicating the connecting party wishes the TTP to sign their data; ‘k’ indicating

the connecting party wishes to obtain the TTP public key; and ‘q’ indicating the party wishes

the TTP to shut down.3

The TTP performs signing as follows:

a. Receives the following: a single byte encoding of the length of name, a utf-8 encoded name and

an RSA public key (N, e) where N, e are each encoded as byte-arrays of size 128.

b. Hashes the byte array (name||N||e) using SHA3-512 to obtain a 512-bit value t, stores it, and

hashes t once again to produce t

0

.

c. Taking the byte array t||t

0

, interpret this as a big-endian integer and reduce by the TTP’s RSA

modulus to get the value S.

4

d. Compute TTP SIG, the RSA signature on S.

e. Send the values (N0

, TTP SIG) to the connected party, where N0

is the TTP’s RSA modulus.

f. Resume listening on the socket for another command.

The TTP performs key-request as follows:

a. Sends its public key (N, e).

b. Resumes listening on the socket connection to receive another command.

The Server performs signature-request as follows:

a. Connect and send a one-byte character ‘s’ to the TTP.

b. Send a single byte encoding of the length of name, a utf-8 encoded name and an RSA public

key (N, e) where N, e are each encoded as byte-arrays of size 128.

c. Receive and store the TTP’s N and TTP SIG.

2With TLS 1.3, there has been a move towards using authenticated encryption schemes such as AES-GCM. For

pedagogical reasons, we will look at a more classic cipher-suite.

3A true implementation would not have this last feature, but it makes debugging much easier.

4The purpose of this is to make full use of the RSA message space.

10

d. Close the socket connection.

The Client performs key-request as follows:

a. Connect and send a one-byte character ‘k’ to the TTP.

b. Receive and store the TTP’s N and d.

c. Close the socket connection.

The following steps must be added to the Server initialization from the previous assignment before opening a listening socket:

a. Obtain a name, server name.

b. Generates two RSA primes p

0 and q

0 of size 512-bits and computes N0 = p

0

q

0

.

c. Generates an RSA key-pair (N0

, e0

) and (N0

, d0

).

d. Connect and request a signature from the TTP

Once the Client and Server have both obtained the relevant information from the TTP and the

Client has registered with the Server, the TLS handshake proceeds (finally!) as follows:

a. Client sends the length of its username as a single byte, followed by username to the Server.

b. The Server sends a certificate consisting of the server’s name and public key as well as a signature

of these values by the TTP.

• The server sends the length of server name as a single byte, followed by

server name ||N0

||e

0

||TTP SIG

where N0

, e,0 TTP SIG are each encoded as 128-byte arrays.

• Upon receiving the certificate, the Client should verify the signature of the TTP. If verification fails, the client should close the socket.

c. Initiate the protocol from Assignment 2 with the following modifications:

• Instead of the Client sending A as plaintext, they will send Enc(A), the RSA encryption

of A under the Server’s public key.

• Upon receiving Enc(A) the server must decrypt to obtain A.

• In case you did not implement the following check in Assignment 2: the server should

ensure that the value A is not congruent to 0 under the SRP modulus and abort otherwise

(it may be fun to think about why).

• The remainder of the protocol proceeds as n Assignment 2 (derive the shared key and

verify).

d. With the shared key derived, take the first 32-bytes as key for AES-256. Use the next 32 bytes

as the key for HMAC.

e. Pad the file if necessary, then encrypt it using the appropriate key.

11

f. Also note that you will require an IV for AES-CBC. This should be randomly generated and

prepended to the encrypted message (just as in Assignment 1). The IV is considered part of

the ciphertext.

g. Generate a tag of the ciphertext bytes using HMAC-SHA3-256 with the appropriate key, and

append the tag to the encrypted bytes.5

h. Store the length of the ciphertext in a 4-byte array, then send the length followed by the

ciphertext to the Server.

i. Have the server receive the ciphertext and decrypt and verify the tag.

Problem Your task is to complete the template program

basic handshake.py

which performs the above handshake protocol. The program consists of functions corresponding to

establishing a connection and transmitting data through a socket, parameter generation and the

actions performed by the Client, Server and TTP.

It is recommended to echo messages sent over the socket to standard output, as this makes debugging the protocol substantially easier. This is not required, but in prior years students benefited

greatly from being able to watch the network traffic. The varprint(. . . ) function is useful for this.

In adherence to the specified TLS ciphersuite, the hash function H used in the protocol will be

SHA3-256 as implemented in the cryptography library. Remember to change this when

using the protocol from Assignment 2. Additionally, when randomness is required use either

os.urandom or the secrets library.

We will allow the use of the sympy library, as it is useful for handling prime numbers; however,

certain functions will not be permitted including

• sympy.primitive root()

Requirements.

a. You must implement your own version of the RSA related functions. You may not use the built

in functions related to RSA from the cryptography library for this exercise.

b. For efficiency we have chosen very small parameter sizes: The server and TTP choose RSA

primes p and q to be 512 bit safe primes. Thus the modulus N will be 1024 bits (128 bytes).

See the course notes for the specifics of the RSA encryption and signature schemes.

c. All other primitives should make use of the cryptography library.

d. Please be careful to note the changes in functions used in past assignments. In particular the

use of AES-256, SHA3-256, and HMAC in the symmetric protocol.

Specifications. Fill in the empty functions in the template program basic handshake.py. Since

this is built on top of the previous assignment, once complete, you should be able to perform the

full TLS handshake between two parties, one acting as the Client and the other as Server, using

a TTP by running

5There is some debate within the cryptography over whether it is more secure to encrypt the hash or append the

hash to the encrypted bytes. Since we used the former method on Assignment 1, we will use the latter on this one.

12

python3 basic handshake.py –ttp

python3 basic handshake.py –server

python3 basic handshake.py –client

python3 basic handshake.py –quit server –quit ttp

You may also combine these actions with one invocation of basic handshake.py, although this

makes debugging substantially more difficult. There will be additional command-line options to

change the username and password from the defaults, as well as the IP address and ports the TTP

and server listen on.

In detail, the new functions you’ll need to fill in fall into the following categories:

a. Low-level Functions:

(i) RSA key.keypair(. . . ), which generates e and d for the given p and q.

(ii) RSA key.modulus(. . . ), which generates p and q for the specified bit length.

(iii) RSA key.sign(. . . ), which signs x for a given N and d.

(iv) RSA key.encrypt(. . . ), which encrypts x for a given N and e.

(v) RSA key.decrypt(. . . ), which decrypts x for a given N and d.

(vi) pad encrypt then HMAC(. . . ), which handles the named operations given a plaintext and

two keys.

(vii) decrypt and verify(. . . ), which reverses the operations performed by pad encrypt then HMAC(. . . )

while verifying the input could be decrypted.

b. High-level Functions:

(i) ttp prepare(. . . ), which computes the TTPs RSA key pair.

(ii) ttp sign(. . . ), which signs the connecting party’s RSA key.

(iii) ttp sendkey(. . . ), which sends the TTPs public key.

(iv) sign request(. . . ), which requests a signature from the TTP.

(v) key request(. . . ), which requests the TTP’s public key.

(vi) client protocol(. . . ), which performs the Client’s side of the protocol, modified from

Assignment 2.

(vii) server protocol(. . . ), which performs the Server’s side of the protocol, modified from

Assignment 2.

(viii) server prepare(. . . ), which computes the Server’s registration values N, g, k, as well as

the Server’s RSA key pair.

Note that some values may be supplied as an integer or as a bytes object; your functions will need

to translate between them as the context requires. All numbers are converted to bytes via network

byte order, which is big-endian.6 Additional details and documentation of these functions can be

found in the template program found on the Piazza resources page.

Submission: Submit a completed version of the template program with filename

basic handshake.py

6Functions will be supplied with the template to help with conversion.

13

If you’ve spread your code across multiple source files, submit all of them.

Provide a description of your implementation in a separate README file in text format. Do not

include the written portion of the programming problem in the PDF file containing your solutions

to the written problems. Your description should include the following:

a. A list of files submitted that pertain to the problem and a short description of each file.

b. A list of what is implemented in the event that you are submitting a partial solution or a

statement that the problem is fully solved.

c. A list of what is not implemented in the event that you are submitting a partial solution,

d. A list of known bugs or a statement that there are no known bugs.

You may either use your own code or the solution files from Assignments 1 and 2.

14