[Solved] CPSC 418 -ASSIGNMENT 3

Introduction to Cryptography

http://people.ucalgary.ca/~rscheidl/crypto/assignments.html.

Assignments that dont follow these instructions will incur penalties of varying degree, up to a score of zero.

Problems 1-5 are worth 63 marks and are required for both CPSC 418 and MATH 318 students.

Problems 6 & 7 are worth 37 marks and are for MATH 318 students only; CPSC 418 may do these for limited extra credit.

Problem 8 is worth 37 marks and is for CPSC 418 students only; MATH 318 may do these for limited credit.

The bonus credit policy can also be found under the link above.

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. 1 denotes concatenation of strings).

Algorithm ITHASH

Input: A message M = P1IP2I IPL Output: An n-bit hash of M

• Initialize _H := 0n (n zeros)
• for i = 1 to L do
• H := f(H,Pi)
• end for
• 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. (5 marks) Define a message authentication function PHMAC (Prepend Hash MAC) via PHMACK(M) := ITHASH(KIM) = ITHASH(KIP1IP2I 1PL)

for any message M = P1~P2~ 11PL.

Suppose an attacker knows a message/PHMAC pair (M1, PHMACK(M1)). Let X be an arbitrary n-bit block and put M2 = M1IX. Show how an attacker can compute PHMACK(M2) without knowledge of K, thereby defeating computation resistance for PHMAC.

Hint: Let M1 = P1 P21 ~PL. Tracing through the ITHASH algorithm, compare the results of the first L + 1 rounds of ITHASH(KIM1) and _{ITHASH(KIM2).} Then explain how the attacker can compute PHMACK(M2) from _ITHASH(KIM2) without knowledge of K.

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

1. (6 marks) Define a message authentication function AHMACK (Append Hash MAC) via

AHMACK(M) := ITHASH(MIK) = ITHASH(P1IP2I IPLIK) for any message M = P1~P2~ IPL.

Assume that ITHASH is not weakly collision resistant, and suppose an attacker knows a mes-sage/AHMAC pair (M1, AHMACK(M1)). Show how she can find (without knowledge of K) asecond 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 n1, gcd(C, n) = 1), she proceeds as follows:

Step 1. Compute

d_p d (mod p 1), 0 d_p p 2 , d_q d (mod q 1), 0 d_q q 2.

Step 2. Compute

M_p C^dp (mod p), 1 M_p p 1 , M_q C^dq (mod q), 1 M_q 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 pxM_q + qyM_p (mod n), 0 M n 1.

Prove that if the above procedure decrypts correctly. That is, if C M^e (mod n) is a ciphertext obtained by encrypting a message M the normal RSA way, and M is the result of applying the procedure above to C, prove that M = 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 d_p and d_q generally have about half the bit length of d (as d n, d_p 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.

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. Fermats idea was to attempt to find a representation of an integer n as a difference of squares n = x² y² 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.

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

x = n + 12_____ , y = n 1 or x = p + q2_____ , y = p q . (1) 2 2

Note that it is not enough to prove that these given values for x and y satisfy n = x² y². The point is to prove that there are no integer values for x and y other than the ones given here.

1. (2 marks) Prove that p + q < n + 1.
2. (3 marks) Use the inequality p > q to prove that n < p + q 2 < p.
3. (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² 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

• Put x = [n1 (n rounded up to the nearest integer)
• y := x² n
• while y is not an integer do

______

• x := x + 1; y := x² n
• end while
• 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.

2. (2 marks) Show that the while condition in step 3 is tested x [n 1 + 1 times, where x = (p + q)/
3. (4 marks) Prove that x [n1 < y2

2n 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 [n 1.

1. (2 marks) Finally, the coup-de-grce. Suppose p q < 2B⁴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 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)

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).

Alices public key is {p, g, y} Alices private key is {x}

To encrypt a message M E Z p intended for Alice, Bob selects a random integer k E _{Zp_1,} computes C1 g^k (mod p) and C2 My^k (mod p), and sends C = (C1, C2) to Alice.

Alice decrypts the ciphertext C = (C1, C2) by computing C2C^p_1_x M (mod p).

1

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 QR_p and M2 QN_p, and obtains the ciphertext C = (C1, C2) = E(Mi) where i = 1 or 2.

(Mallorys task is precisely to ascertain whether i = 1 or i = 2.)

Step 2. Computes the Legendre symbols (y)_, (C1) and (C2).

p p p

Step 3. If (y) = 1 and (C2) = 1, she asserts that C = E(M1).

p p

If (y) = 1 and (C2) = 1, she asserts that C = E(M2).

p p

If (y) = 1, _(p 1) = 1 and (2) = 1, she asserts that C = E(M1). p If (y) = 1, _(p 1) = 1 and (2) = 1, she asserts that = E(M2). p If (y) = 1, _(p 1) = 1 and (2) = 1, she asserts that C = E(M2). p

If (y) = 1, _(p 1) = 1 and (2) = 1, she asserts that C = E(M1). p

Note that this procedure requires three Legendre symbol computations which can be done with modular exponentiation by Eulers Criterion and hence always takes polynomial time. Note also that Mallory states her assertions with certainty, i.e. probability 1.

Prove that Mallorys 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) Alices RSA public key (n has k bits)
• d Alices RSA private key
• H : {0, 1}^k ~ {0, 1}^m a public random function

Encryption of an m-bit message M Z_n:

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

Step 2. Compute C = (sI t) where s _re (mod n) and t = H(r) M.

Decryption of a ciphertext C = (sIt):

Step 1. Separate C into s and t.

Step 2. Compute M H(_sd (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 for decryption. Almost any two plaintexts M1, M2 will do. Let

C = (sI t) = (_re (mod n) 11 H(r) Mi) where i = 1 or 2

be the encryption of one them; Mallory needs to ascertain whether i = 1 or i = 2. Mallory chooses the ciphertext C = (sI t ED M1) and obtains its decryption (make sure that C =~ C; thats 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 cant 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.

1. (3 marks) Suppose N is prime and let g be primitive root of N. Prove that g(N1)/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.

1. (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 _Nconsists precisely of the powers g^k (mod N) with0 < k < N 2.

1. (3 marks) Suppose N is composite. Prove that (N 1)! # -1 (mod N).

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

1. (3 marks) By parts (b) and (c), the congruence (N 1)! -1 (mod N) can be used as aprimality 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 FN1 (N 1)! (mod N) via the recurrence F0 = 1 and F_{n nFn1} (mod N) for 1 < n < N 1.

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,. . . q_m 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 ,

rm3 = qm1rm2 + rm1 , rm1 = gcd(a, b),

rm2 = qmrm1 + rm , rm = 0.

Recall the familiar sequences

A2 = 0, A1 = 1, Ai = qiAi1 + Ai2 for 0 i m,B2 = 1, B1 = 0, Bi = qiBi1 + Bi2 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:

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 <

n6 .(3)

1. (5 marks) Prove that 1 k < d and gcd(d, k) = 1.
2. (3 marks) Prove that 2 n (n) < 3n.
3. (4 marks) Use parts (a) and (b) to prove that 0 < kn ed < 3dn.
4. (4 marks) Conclude from part (c) and the upper bound (3) on d that 0 < k e 3 1

d _n< ______ < 2d2

1. (3 marks) Let q0, q1, . . . , q_m be the quotients obtained when applying the Euclidean algorithm to e and n, and let A , B be the associated sequences as defined above. Use the theorem from above to prove that k = A and d = B for some i E {0, 1,. . . , m}.
2. (6 marks) Use part (e) to devise a procedure for finding d 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)

Dont 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).

For this assignment, your task is to implement a toy version of the TLS handshake using the cipher suite specified above.² 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.³

The TTP performs signing as follows:

128. 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.
129. 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.
130. Taking the byte array t||t, interpret this as a big-endian integer and reduce by the TTPs RSA modulus to get the value S. 4
131. Compute TTP SIG, the RSA signature on S.
132. Send the values (N, TTP SIG) to the connected party, where N is the TTPs RSA modulus.
133. Resume listening on the socket for another command.

The TTP performs key-request as follows:

1. Sends its public key (N, e).
2. Resumes listening on the socket connection to receive another command.

The Server performs signature-request as follows:

1. Connect and send a one-byte character s to the TTP.
2. 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.
3. Receive and store the TTPs N and TTP SIG.

²With 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. ⁴The purpose of this is to make full use of the RSA message space.

1. Close the socket connection.

The Client performs key-request as follows:

1. Connect and send a one-byte character k to the TTP.
2. Receive and store the TTPs N and d.
3. Close the socket connection.

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

1. Obtain a name, server name.
2. Generates two RSA primes p and q of size 512-bits and computes N = pq.
3. Generates an RSA key-pair (N, e) and (N, d).
4. 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:

1. Client sends the length of its username as a single byte, followed by username to the Server.
2. The Server sends a certificate consisting of the servers 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 ||N||e||TTP SIG

where N, e, 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.

1. 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 Servers 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).

256. 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.
257. Pad the file if necessary, then encrypt it using the appropriate key.

1. 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.
2. Generate a tag of the ciphertext bytes using HMAC-SHA3-256 with the appropriate key, and append the tag to the encrypted bytes.⁵
3. Store the length of the ciphertext in a 4-byte array, then send the length followed by the ciphertext to the Server.
4. 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 debug-ging the protocol substantially easier. This is not required, but in prior years students benefitedgreatly 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.

1. 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.
2. 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.
3. All other primitives should make use of the cryptography
4. 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

⁵There 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.

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 youll need to fill in fall into the following categories:

1. Low-level Functions:

• RSA key.keypair(), which generates e and d for the given p and q.
• RSA key.modulus(), which generates p and q for the specified bit length.
• RSA key.sign(), which signs x for a given N and d.
• RSA key.encrypt(), which encrypts x for a given N and e.
• RSA key.decrypt(), which decrypts x for a given N and d.
• pad encrypt then HMAC(.. . ), which handles the named operations given a plaintext and two keys.
• decrypt and verify(.. . ), which reverses the operations performed by pad encrypt then HMAC() while verifying the input could be decrypted.

1. High-level Functions:

• ttp prepare(), which computes the TTPs RSA key pair.
• ttp sign(), which signs the connecting partys RSA key.
• ttp sendkey(), which sends the TTPs public key.
• sign request(), which requests a signature from the TTP.
• key request(), which requests the TTPs public key.
• client protocol(), which performs the Clients side of the protocol, modified from Assignment 2.
• server protocol(), which performs the Servers side of the protocol, modified from Assignment 2.
• server prepare(), which computes the Servers registration values N,g, k, as well as the Servers 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.⁶ 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

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

If youve 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:

1. A list of files submitted that pertain to the problem and a short description of each file.
2. 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.
3. A list of what is not implemented in the event that you are submitting a partial solution,
4. 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.