DOC PREVIEW
MIT 6 042J - Study Guide

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Problem 1(a)(b)(c)(d)(e)Problem 2(a)(b)(c)(d)Problem 3(a)(b)(c)(d)Problem 4(a)(b)Problem 5(a)(b)Problem 6(a)(b)(c)Problem 7Problem 8(a)(b)Massachusetts Institute of Technology 6.042J/18.062J, Fall ’05: Mathematics for Computer Science October 19 Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld revised October 31, 2005, 1054 minutes Problem Set 6 Due: October 26 Reading: Notes 7 on State Machines & Notes 8 on Series and Asymptotics. Problem 1. You’ve seen how the RSA encryption scheme works, but why is it hard to break? In this problem, you will see that finding secret keys is as hard as finding the prime factorizations of integers. Since there is a general consensus in the crypto commu-nity (enough to persuade many large financial institutions, for example) that factoring numbers with a few hundred digits requires astronomical computing resources, we can therefore be sure it will take the same kind of overwhelming effort to find RSA secret keys of a few hundred digits. This means we can be confident the private RSA keys are not somehow revealed by the public keys 1 For this problem, assume that n = p · q where p, q are both odd primes and that e is the public key and d the secret key of the RSA protocol as described in Week 6 Notes. Let x ::= e· d − 1. (a) Show that φ(n) divides x. (b) Conclude that 4 divides x. x(c) Show that if gcd(r, n) = 1, then r ≡ 1 (mod n). 2A square root of m modulo n is a nonnegative integer s < n such that s ≡ m (mod n). Here is a nice fact to know: when n is a product of two odd primes, then every number m such that gcd(m, n) = 1 has 4 square roots modulo n. In particular, the number 1 has four square roots modulo n. The two trivial ones are 1 and n− 1 (which is ≡ −1 (mod n)). The other two are called the nontrivial square roots of 1. (d) Since you know x, then for any integer, r, you can also compute the remainder, y, of 2 ≡ rxrx/2 divided by n. So y (mod n). Now if r is relatively prime to n, then y will be a square root of 1 modulo n by part (c). Copyright © 2005, Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld. 1This is a very weak kind of “security” property, because it doesn’t even rule out the possibility of deci-phering RSA encoded messages by some method that did not require knowing the secret key. Nevertheless, oveer twenty years experience supports the security of RSA in practice.2 Problem Set 6 Show that if y turns out to be a nontrivial root of 1 modulo n, then you can factor n. Hint: 2From the fact that y − 1 = (y + 1)(y − 1), show that y + 1 must be divisible by exactly one of q and p. (e) It turns out that at least half the positive integers r < n that are relatively prime to n will yield y’s in part (d) that are nontrivial roots of 1. Conclude that if, in addition to n and the public key, e, you also knew the secret key d, then you can be sure of being able to factor n. Problem 2. The Massachusetts Turnpike Authority is concerned about the integrity of the new Zakim bridge. Their consulting architect has warned that the bridge may collapse if more than 1000 cars are on it at the same time. The Authority has also been warned by their traffic consultants that the rate of accidents from cars speeding across bridges has been increasing. Both to lighten traffic and to discourage speeding, the Authority has decided to make the bridge one-way and to put tolls at both ends of the bridge (don’t laugh, this is Mas-sachusetts). So cars will pay tolls both on entering and exiting the bridge, but the tolls will be different. In particular, a car will pay $3 to enter onto the bridge and will pay $2 to exit. To be sure that there are never too many cars on the bridge, the Authority will let a car onto the bridge only if the difference between the amount of money currently at the entry toll booth minus the amount at the exit toll booth is strictly less than a certain threshold amount of $T0. The consultants have decided to model this scenario with a state machine whose states are triples of natural numbers, (A, B, C), where • A is an amount of money at the entry booth, • B is an amount of money at the exit booth, and • C is a number of cars on the bridge. Any state with C > 1000 is called a collapsed state, which the Authority dearly hopes to avoid. There will be no transition out of a collapsed state. Since the toll booth collectors may need to start off with some amount of money in order to make change, and there may also be some number of “official” cars already on the bridge when it is opened to the public, the consultants must be ready to analyze the system started at any state. So let A0 be the initial number of dollars at the entrance toll booth, B0 the initial number of dollars at the exit toll booth, and C0 the number of official cars on the bridge when it is opened. The Authority will be careful to ensure that C0 is not large enough to cause a collapse. You should assume that even official cars pay tolls on exiting or entering the bridge after the bridge is opened.3 Problem Set 6 (a) Give a mathematical model of the Authority’s system for letting cars on and off the bridge by specifying a transition relation between states of the form (A, B, C) above. (b) Characterize each of the following derived variables A, B, A + B, A − B, 3C − A, 2A − 3B, B + 3C, 2A − 3B − 6C, 2A − 2B − 3C as one of the following constant C strictly increasing SI strictly decreasing SD weakly increasing but not constant WI weakly decreasing but not constant WD none of the above N and briefly explain your reasoning. The Authority has asked their engineering consultants to determine T and to verify that this policy will keep the number of cars from exceeding 1000. The consultants reason that if A0 is the initial number of dollars at the entrance toll booth, B0 is the initial number of dollars at the exit toll booth, and C0 is the number of official cars on the bridge when it is opened, then an additional 1000 − C0 cars can be allowed on the bridge, so as long as A − B has not increased by 3(1000 − C0) there shouldn’t more than 1000 cars on the bridge. So they recommend defining T0 ::= 3(1000 − C0) + (A0 − B0). (c) Use the results of part (b) to define a simple predicate, P , on states of the transition system which is satisfied by the start state, that is P (A0, B0, C0) …


View Full Document

MIT 6 042J - Study Guide

Documents in this Course
Counting

Counting

55 pages

Graphs

Graphs

19 pages

Proofs

Proofs

14 pages

Proofs

Proofs

18 pages

Proofs

Proofs

18 pages

Quiz 1

Quiz 1

9 pages

Quiz 2

Quiz 2

11 pages

Load more
Download Study Guide
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Study Guide and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Study Guide 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?