南京大学：《网络安全与入侵检测 Network Security and Intrusion Detection》课程教学资源（课件讲稿）05 Asymmetric Key Cryptography

Asymmetric Key Cryptography Haipeng Dai haipengdai@nju.edu.cn 313 CS Building Department of Computer Science and Technology Nanjing University

Asymmetric Key Cryptography Haipeng Dai haipengdai@nju.edu.cn 313 CS Building Department of Computer Science and Technology Nanjing University

Problems of Symmetric key Cryptosystems In symmetric key cryptosystems,before any ciphertext can be transmitted between two parties,a prior secure transmission of the key k is required. -In practice,this is often very difficult to achieve. Can we design an asymmetric key cryptosystem such that: -An entity has two key:a public key PUa and a private key PRa -X=D(PR,E(PU,X))for confidentiality -X=D(PUa E(PRa,X))for authentication(non-repudiation) The idea of a public-key cryptosystem was proposed by Diffie and Hellman in 1976. RSA Cryptosystem was first invented in 1977 by Rivest, Shamir,and Adleman. 2

2 Problems of Symmetric key Cryptosystems  In symmetric key cryptosystems, before any ciphertext can be transmitted between two parties, a prior secure transmission of the key k is required. ─ In practice, this is often very difficult to achieve.  Can we design an asymmetric key cryptosystem such that: ─ An entity has two key: a public key PUa and a private key PRa ─ X = D(PRa, E(PUa, X)) for confidentiality ─ X = D(PUa, E(PRa, X)) for authentication (non-repudiation)  The idea of a public-key cryptosystem was proposed by Diffie and Hellman in 1976.  RSA Cryptosystem was first invented in 1977 by Rivest, Shamir, and Adleman

Misconceptions Concerning Public-Key Encryption Public-key encryption is more secure from cryptanalysis than symmetric encryption Public-key encryption is a general-purpose technique that has made symmetric encryption obsolete There is a feeling that key distribution is trivial when using public-key encryption,compared to the cumbersome handshaking involved with key distribution centers for symmetric encryption 3

3 Misconceptions Concerning Public-Key Encryption  Public-key encryption is more secure from cryptanalysis than symmetric encryption  Public-key encryption is a general-purpose technique that has made symmetric encryption obsolete  There is a feeling that key distribution is trivial when using public-key encryption, compared to the cumbersome handshaking involved with key distribution centers for symmetric encryption

Principles of Public-Key Cryptosystems The concept of public-key cryptography evolved from an attempt to attack two of the most difficult problems associated with symmetric encryption: Key distribution How to have secure communications in general without having to trust a KDC with your key Digital signatures How to verify that a message comes intact from the claimed sender Whitfield Diffie and Martin Hellman from Stanford University achieved a breakthrough in 1976 by coming up with a method that addressed both problems and was radically different from all previous approaches to cryptography 4

4  The concept of public-key cryptography evolved from an attempt to attack two of the most difficult problems associated with symmetric encryption:  Whitfield Diffie and Martin Hellman from Stanford University achieved a breakthrough in 1976 by coming up with a method that addressed both problems and was radically different from all previous approaches to cryptography Principles of Public-Key Cryptosystems • How to have secure communications in general without having to trust a KDC with your key Key distribution • How to verify that a message comes intact from the claimed sender Digital signatures

Public-key Cryptography (1/2) Encryption Bobs's public key ring Joy Mike Alice Alice's public Alice 's private key key Transmitted ciphertext Plaintext Plaintext input Encryption algorithm Decryption algorithm (e.g.,RSA) output (reverse of encryption algorithm) (a)Encryption 5

5 Public-key Cryptography (1/2)  Encryption

Public-key Cryptography (2/2) Authentication Alice's public key ring Joy 9e1 必 Ted Mike Bob Bob's private Bob's public key key Transmitted ciphertext Plaintext Plaintext Decryption algorithm input Encryption algorithm output (e.g.,RSA) (reverse of encryption algorithm) (b)Authentication 6

6 Public-key Cryptography (2/2)  Authentication

Conventional and Public-Key Encryption Conventional Encryption Public-Key Encryption Needed to Work: Needed to Work: 1.The same algorithm with the same key is 1.One algorithm is used for encryption and used for encryption and decryption. a related algorithm for decryption with a pair of keys,one for encryption and one 2.The sender and receiver must share the for decryption. algorithm and the key. 2. The sender and receiver must each have Needed for Security: one of the matched pair of keys (not the same one). 1.The key must be kept secret. Needed for Security: 2.It must be impossible or at least impractical to decipher a message if the 1.One of the two keys must be kept secret. key is kept secret. 2.It must be impossible or at least 3.Knowledge of the algorithm plus impractical to decipher a message if one samples of ciphertext must be of the keys is kept secret. insufficient to determine the key. 3. Knowledge of the algorithm plus one of the keys plus samples of ciphertext must be insufficient to determine the other key. 7

7 Conventional and Public-Key Encryption

Public-Key Cryptosystem:Secrecy Cryptanalyst PRb Source A Destination B Message X Encryption Decryption Destination Source Algorithm Y=EPUb,X灯 Algorithm X= DPRb,Y门 PUb PRb Key Pair Source 8

8 Public-Key Cryptosystem: Secrecy

Public-Key Cryptosystem:Authentication Cryptanalyst PRa Source A Destination B Message X Encryption Decryption Destination Source Algorithm Y=EPRa,X灯 Algorithm X= D[PU,Y] PRa PUa Key Pair Source 9

9 Public-Key Cryptosystem: Authentication

Public-Key Cryptosystem:Authentication and Secrecy Source A Destination B Message X Encryption Y Encryption Z Decryption Decryption X Message Source Algorithm Algorithm Algorithm Algorithm Dest. PUb PRb Key Pair Source PRa PUa Key Pair Source 10

10 Public-Key Cryptosystem: Authentication and Secrecy