Foundations of Computer SecurityLecture 48: Public Key EncryptionDr. Bill YoungDepartment of Computer SciencesUniversity of Texas at AustinLecture 48: 1 Public Key EncryptionPublic Key EncryptionIn 1976, Whitfield Diffie and Martin Hellman proposed public keyencryption (asymmetric encryption) in which different keys areused for encryption and decryption.In 1997, it was disclosed that asymmetric key algorithms had beendeveloped in the early 1970’s by the British Government’sCommunication Headquarters (GCHQ). They referred to thetechnique as non-secret encryption.Lecture 48: 2 Public Key EncryptionPublic Key EncryptionUse a publicly disclosed key to encrypt and a secret key to decrypt.The requisite relationship is:P = {{P}Kpub}Kpriv.We’ll denote the public key for principal A by Kaand the privatekey will be denoted K−1a.Lecture 48: 3 Public Key EncryptionPublic Key SystemsAlso, for some public key systems, RSA in particular, encryptionand decryption commute and either key can be used in eitherfunction. That is:{{P}K}K−1= P = {{P}K−1}K.This is crucial in some uses of RSA. But is not true for most publickey cryptosystems.Lecture 48: 4 Public Key EncryptionPublic Key SystemsThe basis of any public key system is the identification of aone-way function: easily computed, but difficult to invert withoutadditional information.Example: It is easy to multiply two large primes p1and p2.However, it is very difficult to factor p1p2to recover p1and p2.But, given p1p2and either of p1or p2, it is straightforward torecover the other, simply by dividing.Lecture 48: 5 Public Key EncryptionEfficiency of EncryptionPublic key systems largely solve the key distribution problem.Why?A public key encryption may take 10,000 times as long to performas a symmetric encryption; the computation depends on morecomplex operations, not on simple bit-wise operations.Symmetric encryption remains the work horse of commercialcryptography, with asymmetric encryption playing some importantspecial functions.Lecture 48: 6 Public Key EncryptionLessonsDevising an asymmetric encryption algorithm depends onidentifying a one-way function, easy to compute but hard toinvert.Public key systems largely solve the key distribution problem.Asymmetric algorithms are generally much less efficient thansymmetric algorithms.Next lecture: Public Key Encryption IILecture 48: 7 Public Key
View Full Document