MATH/CMSC 456 (Washington) Final Spring 2018
Algorithm | math代写 – 该题目是一个常规的Algorithm的练习题目代写, 涵盖了Algorithm等程序代做方面
MATH/CMSC 456 (Washington) Final Exam Spring 2018
This exam is worth 140 points. You must show your work to receive credit for a problem.
You may use calculators.
- (10 points = 5+5) Alice uses an improvement of the Vigen
ere cipher: She writes all the letters in the plaintext as numbers mod 26 in the standard way (witha= 0 andz= 25) and she chooses an integerband integersa 1 , a 2 ,... , a 5. She applies the affine functionsa 1 x+b, a 2 x+b,... , a 5 x+b(mod 26) as in Vigenere (soa 1 x+b is used on the 1st, 6th, 11th,… letters,a 2 x+bis used on the 2nd, 7th, 12th,… letters, etc.). (a)What condition doa 1 , a 2 ,… , a 5 need to satisfy for Bob (who knows the key) to be able to decipher the message? (b)Describe a chosen plaintext attack that will yield the key. You know the encryption method and you know the key length. You mustexplicitlysay what plaintexts you use. 2.(20 points = 5+5+5+5) At the end of the semester, the professor randomly chooses and sends one of two possible messages: m 0 =YOUPASSEDandm 1 =YOUFAILED. To add to the excitement, the professor encrypts the message using one of the following methods: (a)Shift cipher (b)Vigenere cipher with key length 3 (c)RSA with a public 300-digit modulusnand encryption exponente= 65537 (the message is not padded with extra bits) (d)One-time pad You receive the ciphertext and want to decide (in less than one minute, but you have a computer) whether the professor sentm 0 orm 1. For each method (a), (b), (c), and (d), explain how to decide which message was sent or explain why this is impossible. (Notes:You may assume that you know which method is being used. For the Vigenere, do not use frequency analysis; the message is too short.) - (20 points = 10+5+5) Huey, Dewey, and Louie ask their uncle Donald, Isn= 19887974881 prime or composite? Donald replies, Yes. Therefore, they decide to obtain more information on their own. (a)Huey computes 13(n1)16739180549 (modn). What does he conclude? (b)Dewey computes 7n^1 1 (modn), and he does this by computing
7 (n1)/^32 1992941816 (modn)
7 (n1)/^16 19887730619
7 (n1)/^8 1
7 (n1)/^4 7 (n1)/^2 7 (n1) 1.
What information can Dewey obtain from his calculation that Huey does not obtain? (c)Louie notices that 19857930655^2 1232 (modn). What information can Louie compute? (in parts (b) and (c), you do not need to do the calculations, but you should indicate what calculations need to be done) 4.(10 points) Suppose Eve factors Alices RSA modulusnand obtainspandq. Eve knows Alices encryption exponenteand has intercepted a ciphertextcthat Bob has sent to Alice. Explain all of the steps that Eve uses to recover the messagemthat Bob encrypted (cme(modn)). Indicate at each step what Algorithm is used to perform the computation. (That is, if some method other than the obvious naive method needs to be used, say what it is. In particular, there are two methods that need to be mentioned.) 5.(10 points) The Modulus Supply Company sells RSA moduli. To save money, it has one 300-digit prime pand, for each customer, it randomly chooses another 300-digit primeq(different frompand different from qsupplied to other customers). Then it sellsn=pq, along with encryption and decryption exponents, to unsuspecting customers. (a)Suppose Eve suspects that the company is using this method of providing moduli to customers. How can she read their messages? (as usual, the modulusnand the encryption exponentefor each customer are public information) (b)Now suppose that the customers complain that Eve is reading their messages. The company computes a setSof 10^6 primes, each with 300 digits. For each customer, it chooses a random primepfromS, then randomly chooses a 300-digit primeq, as in part (a). The 100 customers who receive modulin=pqfrom
1
this update are happy and Eve publicly complains that she no longer can break their systems. As a result, 2000 more customers buy moduli from the company. Explain why the 100 customers probably have distinct primesp, but among the 2000 customers there are probably two with the samep. 6.(10 points) Alice and Bob (and no one else) share a keyK. Each time that Alice wants to make sure that she is communicating with Bob, she sends him a random stringSof 100 bits. Bob computesB=H(S||K), whereHis a good cryptographic hash function, and sendsBto Alice. Alice computesH(S||K). If this matches what Bob sent her, she is convinced that she is communicating with Bob. (a)What property ofHconvinces Alice that she is communicating with Bob? (b)Suppose Alices random number generator is broken and she sends the sameSeach time she commu- nicates with anyone. How can Eve (who doesnt knowK, but who intercepts all communications between Alice and Bob) convince Alice that she is Bob? 7.(15 points = 5+5+5)(a)Alice claims that she knows who will win the next World Cup. She takes the name of the team,T, and encrypts it with a one-time padK, and sendsC=TKto Bob. After the World Cup is finished, Alice revealsK, and Bob computesT=CKto determine Alices guess. Why should Bob not believe that Alice actually guessed the correct team, even ifT=CKis correct? (b)To keep Alice from changingK, Bob requires Alice to send not onlyC=TKbut alsoH(K), where His a good cryptographic hash function. How does the use of the hash function convince Bob that Alice is not changingK? (c)In the procedure in (b), Bob receivesCandH(K). Show how he can determine Alices prediction, without needing Alice to sendK? (Hint:There are fewer than 100 teamsTthat could win the World Cup.) 8.(10 points) Bob has an elliptic curveEmod some prime and he has computed a secret integernsuch that nP=for each pointPonE. He chooses integersdandesuch thatde1 (modn). He makesEande public, and keepsdandnsecret. Alice wants to send a message to Bob, and the message is represented as a pointMonE. Alice computesC=eM, which is a point onE, and sendsCto Bob. Bob computesdC. Show thatdCis the original messageM. 9.(10 points) Letpbe a large prime, letgbe a primitive root modp, and letb60 (modp). Peggy claims to know an integerssuch thatgsb(modp). Give a zero knowledge procedure for Peggy to convince Victor that she knowss(Victor does not knows). The first step should be Peggy chooses a random integer r 1 (modp1) and letsr 2 sr 1 (modp1). 10.(10 points) Bob has a good cryptographic hash functionH, but he is worried that it is not good enough. He has taken a cryptography course (its not known whether he passed), so he knows discrete logs are hard. Therefore, he chooses a 300-digit primepand a primitive rootgmodp. He strengthens his hash function by combining it with a discrete log: h(m) =H(gm(modp)). This yields a hash function that is slow to compute, but this is a sacrifice that Bob is willing to make, since he mistakenly thinks he has made a better hash function. Give another property of hash functions thathdoes not satisfy, and justify your answer. 11.(10 points = 5+5) In the setup of the ElGamal signature scheme, Alice chooses a primep, a primitive rootgmodp, and a secret integera. She computeshga (modp). The numbersp, g, hare made public, andais kept secret. To sign a message, Alice chooses a random integerkwith gcd(k, p1) = 1 and computes
rgk (modp), sk^1 (mar) (modp1).
The signed message (m, r, s) is valid ifgmhrrs(modp). (a) Why is gcd(k, p1) = 1 required? (b) Suppose Eve finds a valid signed message (, r, s) but the message * is unreadable. How difficult is it for Eve to find a messagemfor which theserandsgive a valid signed message (m, r, s)? Explain your answer. 12.(5 points) The following was encrypted by a shift cipher with shift of1. Find the plaintext: GZUDZFNNCRTLLDQ