EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 13 1 (For reference) RSA Encryption Review
Problem setup: Alice wishes to receive confidential messages from Bob (and maybe from others as well). Ideally, Bob would be able to pick a message, encrypt it, and then send it to Alice. On Alice’s end, she would receive some encrypted message and then (only she would) be able to decrypt it, recovering the original message.
RSA is an asymmetric encryption scheme that depends on the hardness of factoring large numbers. It depends on the following theorem, which can be seen as similar to Fermat’s little theorem (though its proof actually relies on the Chinese Remainder Theorem):
Copyright By PowCoder代写 加微信 powcoder
Theorem 1.1. If n = pq, where p and q are distinct primes, and if 0 ≤ a < n and k ≥ 1, then we have a1+kφ(n) ≡ a (mod n). With this theorem, to send a message, one need only use the following protocol: RSA Protocol: • Alice picks two (large) primes p and q and computes n = pq and φ(n) = (p − 1)(q − 1). She then finds a pair of keys (e, d) such that e · d ≡ 1 (mod φ(n)) and broadcasts n and e publicly • Bob decides to send a message m ∈ Zn. He computes the ciphertext c = me mod n and sends c to Alice • Alice receives c and computes m′ = cd mod n Notice that ed = 1+kφ(n) for some k ∈ Z since e·d ≡ 1 (modφ(n)). In the end, Alice ≡ m1+kφ(n) ≡ m1mkφ(n) ≡ m (mod n), which is exactly the message Bob originally sent. Why does this scheme provide confidentiality? For an eavesdropper Eve to be able to determine m from c, she would have to be able to determine Alice’s private key d. Eve knows n, e, and c. To find d, she would need to solve the congruence e · d ≡ 1 (mod φ(n)). If she were to know φ(n), she could use the extended Euclidean algorithm to find such a d. However, to find φ(n) = (p−1)(q−1), she would need to factor n into p · q, which is believed to be a difficult problem.1 Again, quantum computers present a possible long-term vulnerability in this encryption scheme. As of 2020, however, the largest number factored by a quantum computer using Shor’s algorithm is 21. 1To be more technically correct, if Eve were able to efficiently compute φ(n), she would be able to efficiently find p and q by solving a certain quadratic equation. EECS 376: Foundations of Computer Science University of Michigan, Winter 2022 Discussion Notes 13 Example 1.2. RSA Encryption Suppose that Bob wants to secretly send Alice the message m = 5. First, Alice must pick her primes, say p = 11 and q = 13. With this, she then computes n=pq=143andφ(n)=(p−1)(q−1)=120. Tocreateherkeys,shemustfindsapairof integers (e, d) which are inverses module φ(n) i,e, e · d ≡ 1 (mod 120). Since e ∈ Z has an inverse module 120 if and only if gcd(e, 120) = 1, Alice sees that e = 17 is suitable. Using the Extended Euclidean algorithm, she can then compute d = 17−1 mod 120 and finds d = 113. She then publicly broadcasts n = 143 and her public key e = 17. Bob computes the ciphertext c = me (mod n), encrypted using Alice’s public key c = 517 (mod 143) = 135. Alice receives c and compute the plaintext m′ = cd (mod n), decrypting with her private key m′ = 135113 (mod 143) = 5, correctly receiving Bob’s message. (For reference) RSA Signatures Review One application of RSA is the idea of “signing” messages. Signing a message is not intended to hide the contents of the message, but rather allow the receiver of the message to verify that it indeed came from a specific sender (i.e. provide a means of authenticating the sender). The process of signing a message is coincidentally very similar to the process of encrypting a message, but rather than encrypting using the recipient’s public key and decrypting using the recipient’s private key, you sign a message using your own private key and a recipient authenticates the signature using your public key. Example 2.1. RSA Signatures Suppose that Alice wants to send Bob the message m = 6, signing it to convince Bob that it is really her sending the message. • First, Alice must pick her primes, say p = 7 and q = 11. With this, she then computes n = pq = 77 and φ(n) = (p−1)(q−1) = 60. To create her keys, she must finds a pair of integers (e, d) which are inverses module φ(n) i,e, e · d ≡ 1 (mod 60). Since e ∈ Z has an inverse module 60 if and only if gcd(e, 60) = 1, Alice sees that e = 13 is suitable. Using the Extended Euclidean algorithm, she can then compute d = 13−1 mod 60 and finds d = 37. She then publicly broadcasts n = 77 and her public key e = 13. • Alice computes her signature s = md mod n = 637 (mod 77) = 41 and transmits the pair the message and signature pair (m, s) = (6, 41) to Bob. • Bob receives (m, s) = (6, 41) and verifies se ≡ m (mod n) by computing 4113 ≡ 6 (mod 77), confirming that the message indeed came from Alice. EECS 376: Foundations of Computer Science University of Michigan, Winter 2022 Discussion Notes 13 RSA Signature Protocol • Alice picks two (large) primes p and q and computes n = pq and φ(n) = (p − 1)(q − 1). She then finds a pair of keys (e, d) such that e · d ≡ 1 (mod φ(n)) and broadcasts n and e publicly • Alice decides to send a message m ∈ Zn to Bob but wants to prove her identity to Bob, so that no attacker can mimic sending a message to Bob on Alice’s behalf that she did not intend to send. She computes the “signed message” s = md mod n and sends the pair (m, s) to Bob. Notice here that the message m is publicly visible, so the recipient may be arbitrary. • Bob receives (m, s) and verifies se ≡ m (mod n). We can follow the same proof as in the RSA encryption section to show se ≡ m (mod n). We know that ed = 1+kφ(n) for some k ∈ Z since e·d ≡ 1 (modφ(n)). In the end, Bob computes se mod n ≡ mde ≡ med ≡ m1+kφ(n) ≡ m1mkφ(n) ≡ m (mod n), The verification process proves that only Alice could have signed the message m, as she is the only one that knows her private key d. As mentioned before, if an attacker Eve wanted to find d, she would have to factor n into p and q, which is believed to be a difficult problem. 3 Final Exam Topics (Reference only, not exhaustive!) Before Midterm Euclidean Algorithm Divide and conquer: Mergesort, Karatsuba, Master’s Theorem Dynamic programming and Greedy Algorithms (ex: Knapsack, MST) Discrete Finite Automata Turing Machines: 7-tuple definition, equivalence of Turing Machines (ex: 2-tape TM and single- tape TM) Undecidability and Turing Reductions Examples of undecidable languages: LHALT, LACC, Lε−HALT, L∅, LEQ, LACC, LHALT Recognizability, Complexity Rice’s theorem After Midterm EECS 376: Foundations of Computer Science University of Michigan, Winter 2022 Discussion Notes 13 P, NP, NP-Hard, NP-Complete Polynomial reductions Examples of NP-Complete languages: SAT, VERTEX-COVER, CLIQUE, INDEPENDENT-SET, SET-COVER, HAMCYCLE, HAMPATH, SUBSET-SUM, KNAPSACK (and its variations), MAX- CUT, TSP Search-to-Decision Reductions α-approximations Probability, Expectation Markov’s Inequality, Algorithms, Union Bound Modular arithmetic, Extended Euclidean Algorithm One-time Pad Diffie- SA 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com