Data Structures and Algorithms
Please answer the following questions in electronic form and upload and submit your files to the Canvas Assignment site before the due date. Make sure to click on the submit button.
You have two choices for the format.
First Choice: Submit in pdf format all theoretical questions. You may ei- ther typeset or hand-write your answers. In case of hand-write transform your work into pdf using apps such as CamScan. You should have only a single pdf file. For Python scripts, include the text of the script as a separate *.py file. You should have a single file for Questions 3 & 4. For other questions, if you use Python to compute your answers include it with the pdf text above.
Second Choice: You can use a single Python Notebook *.ipynb file. You should use the text format of the notebook for the theoretical results, and the Python script for the programming parts.
1. Solve the following recurrence relations and give the solution in terms of Θ(·). Explain if the master method is applicable. If so, use the master method. If not, directly solve the recurrence.
1a) F(n) = 3F(n/4) + log(n)
1b) F(n) = 4F(n/2) + n3
1c) F(n) = F(n/2) + 1
1d) F(n) = 2F(n/2) + n log(n)
2. In the this question by using a sequence of algebraic manipulations we develop an algorithm that computes the coefficients of p(t + α) for some constant α, given the array of coefficients of p(t). Suppose p(t) = p0 + p1t + · · · + pntn is a polynomial of degree n. Observe that the coefficients of (t+α)k are given by binomial coefficients( k j
) = k!
(t + α)k =( k0) αk +( k1) tαk−1 +( k2) t2αt−2 · · · +( kk) tk=k∑ j=0( kj) tjαk−j
Another, equivalent definition of binomial coefficients is given by the re- currence relation: (k0) =( kk) = 1(kj) =( k − 1j − 1) +( kj − 1)
This quantity, in particular, also counts the number of subset of size j of a set of k elements.
2a) Devise an algorithm that for an integer k, all numbers ( i j) for i, j ≤ k
are calculated. What is the complexity of this algorithm? (Look up Pascal Triangle) If we only want for a fixed k the numbers( k j) for2j = 0, . . . ,k, using the factorial formula above, what algorithm should we use and what is its time complexity?
2b) Now consider the polynomial p(t) = p0 + p1t + · · · + pntn. We wish to compute the coefficients of the shifted polynomial p(t + α) = q0 + q1t + · · · + qntn, where α is a fixed number. Explain how you can use the Fast Fourier Transform to compute qi from pi and α. In total what is the time complexity of recovering coefficients of p(t+α) from the coefficients of p(t)? (Hint: Expand each term of the shifted polynomial, and collect terms for each power ti, and try to see if you can detect a convolution.)
3. Here is a modification to Euclid’s algorithm which does not use division or mod operations. It only uses subtraction and division by two, which in computers, where numbers are represented in binary form, only involves a simple shift. For instance, 100110/2=010011 and 100111/2=010011 with a remainder of 1.
3a) Show that if a and b are both even numbers, then gcd(a,b) = 2 gcd(a/2,b/2)
3b) Show that if one of a and b is even and the other odd, say a is even and b is odd, then gcd(a,b) = gcd(a/2,b).
3c) If both a and b are odd then show that gcd(a,b) = gcd ( a−b 2 ,b
) 3d) Use the above facts to design an algorithm for finding gcd where only
subtraction, division by two and checking if an integer is even or odd. Present your algorithm in a precise pseudocode (If you wish you can instead use Python instead of pseudocode, but this is voluntary.) Provide a time complexity analysis of your algorithm.
4. While the exponentiation operation k = ab mod c can be computed in polynomial time and can be efficiently implemented, the inverse operation is quite difficult to achieve. More precisely, given c, k and a, no one knows an efficient algorithm to find b. The number b in the relation k = ab mod c is called the discrete logarithm of k in base a and mod c. It is conjectured that no efficient algorithm exists in general to compute the discrete logarithm b for any given values of k,a and c1.
1A computer scientist, Peter Shor, however, has devised a polynomial-time algorithm for both discrete logarithm and for integer factorization using quantum computers.
The Diffie-Hellman public key exchange is a protocol where two parties exchange a secret shared key over the open channels (for instance, the in- ternet) and can use this shared key to send each other encrypted messages that only they can decrypt. See the wikipedia page for more informa- tion. The strength of the method rests on the assumption that computing discrete logarithm mod very large prime numbers is computationally in- tractable.
Here is how two people, Alice and Bob, who don’t even need to know each other, and are only aware of each others’ e-mail or IP addresses can exchange a shared key, K which only the two of them will know. Assume a third party, Eve, is eavesdropping, but otherwise can not alter the messages. The protocol works as follows. The teal-colored items are public and anybody eavesdropping can know them. The orange-colored items are secret and known to only the owner.
• Alice selects a large prime number p and another number g. She also chooses a private key a which only she knows and computes A = ga
mod p. Alice sends A,p and g to Bob.
• Bob, upon receiving Alice’s A,g and p, chooses a private key b which only he knows. He computes B = gb mod p and sends it back to Alice. Note that by this stage everyone, including Eve, know the values of p,g,B,A.
• Alice computes K = Ba = gab mod p. • Likewise, Bob computes Ab = gba mod p = K.
So now both Alice and Bob are in possession of the shared key K that nobody else knows. They can use this key to send each other messages. For instance, they can use the XOR method. If Alice wishes to send Bob the message M, she computes E = M ⊕ K (the result of applying XOR to the binary representations of M and K,) and sends it over the open channel to Bob. Once Bob receives E, he decrypts it by M = E ⊕ K. Note that Eve, knowing A,B,g, and p, as well as the encrypted message E, nevertheless cannot find out what K is easily. To do so she needs to solve the equation gx = A mod p, to find a = x, and solve gy = B mod p for y = b. If she could do so, then she would know K = gab mod p and would be able to decrypt E and recover the message M = E ⊕ K.
4a) Write in Python a class called diffHellSend for the person who ini- tiates a communication (Alice). The init method of this class should have three optional parameters: a the sender’s secret key a defaulted to None, and a pair of integers low (default 0) and high
(default 2100) which will be the range of random integers to be cho- sen later2. Furthermore, the init method should set the values of a,g,p, and A. For generating p you may use the methods provided in the number theory and cryptography module. If the argument a is None its value should be randomly generated. The other values that are not computed by a formula should also be randomly generated.
All of these values should be private attributes. The class should have a method called getPublic which returns the public values, that is A,g and p.
In addition, this class should have a method called receive which receives the value of B from the other person (Bob). Using B it should compute the common key K, which should be another private member of the class.
Finally, the class should have a method crypt which should take a message M and encrypt it using the XOR operation with key K and return E, the encrypted version of M.
4b) Write a second class for the second person (Bob) who is signaled to have a communication with the first person; this class should be called diffHellReceive. The init method of this class should take the public values of A,g,p, and possibly Bob’s secret key b (which has the default value of None.) It should also have the optional arguments low (defaulted to 0) and high (defaulted to 2100.) If b equals None a random integer between low and high should be used for it. Also init should compute the value of B and the common secret key K, both of which should be private members of the class.
The class should have the method getPublic which returns the public value B.
The class should also have a method called crypt that takes a secret message E from the sender Alice and decrypts is using XOR and the secret common key K and returns Alice’s original message M.
4c) Create a diffHellSend object called alice and set her secret key a = 700090980808 (let low and high be the default values.)
4d) Create a diffHellReceive object bob and set his secret key b = 209573994589 (let low and high be the default values.)
4e) Alice wishes to send the message “M=159786939486074610063241937” to Bob. Write the sequence of calls necessary to send the message,
2Use Python module random and the method randint(low,high) to generate arbitrary long random integers
and for Bob to receive and decrypt the message. Print, M, E Alice’s encrypted message and Bob’s decryption M1 and see if M = M1.
5. Alice and Bob are participating in an online community that uses the RSA public key system for secure communications.
5a) For Alice compute random prime numbers pa, and qa between 2 50 ≤
pa,qa ≤ 252. Similarly, for Bob compute random prime numbers pb, qb between 2
50 ≤ pb,qb ≤ 252.
5b) Compute na and the Euler function φ(na), and nb and φ(nb).
5c) Alice chooses `a = 73 for her public key in an RSA system. Compute her private key ka. Similarly, Bob chooses `b = 41 for his public key. Compute his private key kb. Write a function called find k to compute ka from `a and , kb, from `b.
5d) Write a Python function crypt that takes a list of integers as the message and encrypts them one by one, using a provided pair of keys. The pair may be either the receiver’s public key (`,n), or it could be the sender’s private key (k,n). The function should return the list of encrypted integers as computed by the RSA system.
5e) Write a function txtToRSA which takes a string and a pair of inte- gers (k,n). This function first turns the string into its list of unicode integers, and encrypts this list (by using crypt function above) and outputs the encrypted list of integers. You may use the built-in func- tion ord(c) to turn each character into its unicode equivalent.
5f) Write a function RSAtoTxt which takes a list of integers, and a pair of additional integers (`,n) and using crypt decrypts the list to recover the unicode integers. It then turns the unicode integers into a single string. You may use the built-in function chr(m) that takes an integer m and returns its unicode equivalent character (so ord and chr are inverse of each other.)
5g) Write a function RSAsign that takes a text message M from the sender (say Bob) and a signature from him with exactly ten characters, and computes the RSA encoding along with the signature. Note that you need to do two encryptions: First, encrypt the message M using Bob’s private key kb to get Eb. Then attach Bob’s signature (text turned into a list of ten integers σb) using the built-in function ord and form
Eb + σb (’+’ here refers to appending of two lists of integers.) Then encrypt this joined list again, this time using the receiver’s (say Alice) public key `a.
5h) Next write a script unpack that gets the message from sender (Bob), and then uses receiver’s (Alice) own private key to decrypt it and re- cover Bob’s signature σb and his encrypted message Eb. Note, since Alice knows Bob’s signatire is exactly ten characters, she can take the last ten numbers of the decrypted list, and turn them into characters by using the built-in chr function. Then she takes away Bob’s sig- nature from the end of the once decrypted list and then uses Bob’s public key to decrypt the rest of the encrypted message to get Bob’s text.
5i) To test your code, suppose Bob wants to send the message “Bitcoin to double next week! ” Also, let’s Bob’s signature be simply “Bob” followed by enough blank characters to make it exactly ten characters. Print, pa,qa,na,φ(na) for Alice and similarly, pb,qb,nb,φ(nb) for Bob. Set public keys `a = 73 and `b = 41. Find and print Alice and Bob’s private keys.
Print the encrypted message Alice receives. Print Alice’s completely decrypted message and recover Bob’s message to Alice along with Bob’s recoverd message and check to see they are what Bob sent.
Assignment status: Solved by our experts