Foundations of Computer SecurityLecture 49: Public Key Encryption IIDr. Bill YoungDepartment of Computer SciencesUniversity of Texas at AustinLecture 49: 1 Public Key Encryption IIRSA AlgorithmThe Rivest-Shamir-Adelman (RSA) algorithm relies on thedifficulty of factoring large numbers.Two keys, e and d, are used for encryption and decryption. Thealgorithm is such that:{{P}d}e= P = {{P}e}d.A plaintext block P is encrypted as (Pemod n). d is chosen sothat:(Pe)dmod n = P.An interceptor would have to factor Peto recover the plaintext.The legitimate receiver knows d and merely computes(Pe)dmod n = P, which is much easier.Lecture 49: 2 Public Key Encryption IIOther Public Key AlgorithmsA public key system can be based on any one-way function. A richsource is the set of NP-complete problems. These are infeasible tosolve, but a solution can be checked in polynomial time.Merkle and Hellman proposed a public key system based on theknapsack problem: given a set of integers and a target sum, find asubset of the integers that sum to the target.The algorithm is theoretically very secure, but has practicalweaknesses.Lecture 49: 3 Public Key Encryption IIAuthentication with Public KeysAssume Kais A’s public key. Suppose B sends the followingmessage to A: {M}Ka. What assurances does A have?1No-one intercepting the message could read it. Why?2He can’t be sure it actually came from B. Why not?Thus, encryption with the public key is a privacy transformation,but not an authenticity transformation.Lecture 49: 4 Public Key Encryption IIAuthentication with Public KeysUsing RSA, B send {M}K−1bto A. If A can decrypt it using Kb,what assurance is gained?1A is sure it originated with B. Why?2But, someone intercepting the message might read it. Why?Thus, encryption with the private key is an authenticitytransformation, not a privacy transformation.Note this only works in RSA, because:{{P}d}e= P = {{P}e}d.In other public key systems, you typically need two pairs of keys:one pair for privacy and the other pair for “signing” (authenticity).Lecture 49: 5 Public Key Encryption IILessonsRSA is the most widely used public key cryptosystem.RSA is symmetric in the use of keys; most public key schemesare not.A public key encryption can be used for authenticity or forprivacy but not both at once.Next lecture: Cryptographic Hash FunctionsLecture 49: 6 Public Key Encryption
View Full Document
Unlocking...