中国科学技术大学：《现代密码学理论与实践》课程教学资源（PPT课件讲稿）第9章 公钥密码学与RSA

本章要点 15 ·非对称密码是一种密码体制，其加密算法和解密算法 使用不同的密钥，一个是公钥，一个是私钥。非对称 密码也称为公钥密码。 ●3 非对称密码用两个密钥中的一个以及加密算法将明文 转换为密文，用另一个密钥以及解密算法从密文恢复 出明文。 ·非对称密码可以用来保密、认证或者两者兼而有之。 应用最广泛的公钥密码体制是RSA,破解RSA的困难， 是基于分解大合数素因子的困难。 2022/10/9 现代密码学理论与实践-09 2/34

2022/10/9 现代密码学理论与实践-09 2/34 本章要点 ⚫ 非对称密码是一种密码体制，其加密算法和解密算法 使用不同的密钥，一个是公钥，一个是私钥。非对称 密码也称为公钥密码。 ⚫ 非对称密码用两个密钥中的一个以及加密算法将明文 转换为密文，用另一个密钥以及解密算法从密文恢复 出明文。 ⚫ 非对称密码可以用来保密、认证或者两者兼而有之。 ⚫ 应用最广泛的公钥密码体制是RSA，破解RSA的困难， 是基于分解大合数素因子的困难

9.1公开密钥密码体制的基本原理 15 。对称密码体制的问题 加密能力与解密能力是捆绑在一起的 密钥更换、传递和交换需要可靠信道，密钥分发困难 ● 如有N用户，则需要C=N(N-1)/2个密钥，n=1000时， C(1000,2)≈500000，密钥管理困难 无法满足不相识的人之间通信的保密要求 ● 不能实现数字签名 ● 非对称密码体制的基本特点 加密能力与解密能力是分开的 密钥分发简单 需要保存的密钥量大大减少，N个用户只需要N个密钥 可满足不相识的人之间保密通信 可以实现数字签名 2022/10/9 现代密码学理论与实践-09 3/34

2022/10/9 现代密码学理论与实践-09 3/34 9.1 公开密钥密码体制的基本原理 ⚫ 对称密码体制的问题 ⚫ 加密能力与解密能力是捆绑在一起的 ⚫ 密钥更换、传递和交换需要可靠信道，密钥分发困难 ⚫ 如有N用户，则需要C=N(N-1)/2个密钥，n=1000时， C(1000, 2)≈500000, 密钥管理困难 ⚫ 无法满足不相识的人之间通信的保密要求 ⚫ 不能实现数字签名 ⚫ 非对称密码体制的基本特点 ⚫ 加密能力与解密能力是分开的 ⚫ 密钥分发简单 ⚫ 需要保存的密钥量大大减少，N个用户只需要N个密钥 ⚫ 可满足不相识的人之间保密通信 ⚫ 可以实现数字签名

公开密钥密码体制 公钥算法依赖于一个加密密钥和一个与之相关的不 同的解密密钥，算法有如下特点： 仅根据密码算法和加密密钥来确定解密密钥在计算上是 不可行的 。两个密钥的任何一个都可用来加密，另一个用来解密 ·公钥密码体制的组成 。明文：算法的输入，可读信息或数据 ● 加密算法：对明文进行各种转换 公钥和私钥：算法的输入，分别用于加密和解密 密文：算法的输出，依赖于明文和密钥 解密算法：根据密文和密钥，还原明文 2022/10/9 现代密码学理论与实践-09 4/34

2022/10/9 现代密码学理论与实践-09 4/34 公开密钥密码体制 ⚫ 公钥算法依赖于一个加密密钥和一个与之相关的不 同的解密密钥，算法有如下特点： ⚫ 仅根据密码算法和加密密钥来确定解密密钥在计算上是 不可行的 ⚫ 两个密钥的任何一个都可用来加密，另一个用来解密 ⚫ 公钥密码体制的组成 ⚫ 明文：算法的输入，可读信息或数据 ⚫ 加密算法：对明文进行各种转换 ⚫ 公钥和私钥：算法的输入，分别用于加密和解密 ⚫ 密文：算法的输出，依赖于明文和密钥 ⚫ 解密算法：根据密文和密钥，还原明文

公钥算法的主要步骤 每个用户产生密钥，用来加密和解密消息 每个用户将其中一个密钥（公钥）存于公开的寄存器或其 他可访问的文件中，另一密钥私有，每个用户可以拥有 若干其他用户的公钥 若Bob要发消息给Alice,则要用Alice的公钥对消息加密 Alice收到消息后，用其私钥对消息解密，由于只有Alice 知道其自身的私钥，所以其他的接收者均不能解密消息 需要认证时示证方用自己的私钥加密消息（签名） ● 验证方用示证方的公钥解密消息（验证），如果结果证实 公钥与示证方的私钥相吻合，则可以确认示证方确为合 法的用户（认证） 加密和认证可以结合起来，同时实现保密性和认证 2022/10/9 现代密码学理论与实践-09 5/34

2022/10/9 现代密码学理论与实践-09 5/34 公钥算法的主要步骤 ⚫ 每个用户产生密钥，用来加密和解密消息 ⚫ 每个用户将其中一个密钥(公钥)存于公开的寄存器或其 他可访问的文件中，另一密钥私有，每个用户可以拥有 若干其他用户的公钥 ⚫ 若Bob要发消息给Alice，则要用Alice的公钥对消息加密 ⚫ Alice收到消息后，用其私钥对消息解密，由于只有Alice 知道其自身的私钥，所以其他的接收者均不能解密消息 ⚫ 需要认证时示证方用自己的私钥加密消息(签名) ⚫ 验证方用示证方的公钥解密消息(验证)，如果结果证实 公钥与示证方的私钥相吻合，则可以确认示证方确为合 法的用户(认证) ⚫ 加密和认证可以结合起来，同时实现保密性和认证

公开密钥加密过程 ◆季 15 Bobs's public key ring Joy Ted Mike Alice Alice's public Alice's private key key Transmitted ciphertext Plaintext Plaintext input Encryption algorithm Decryption algorithm output (e.g.,RSA) (reverse of encryption algorithm) (a)Eneryption 2022/10/9 现代密码学理论与实践-09 6/34

2022/10/9 现代密码学理论与实践-09 6/34 公开密钥加密过程

线衣 公开密钥认证过程 1950 Alice's public key ring Joy Mike Bob Bob's private Bob's public key key Transmitted ciphertext Plaintext Plaintext input Encryption algorithm Decryption algorithm output (e.g.,RSA) (reverse of encryption algorithm) (b)Authentication Figure 9.1 Public-Key Cryptography 2022/10/9 现代密码学理论与实践-09 7134

2022/10/9 现代密码学理论与实践-09 7/34 公开密钥认证过程

常规和公开密钥加密的重要特征 Table 9.1 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 used for 1. One algorithm is used for encryption and decryption with a encryption and decryption. pair of keys,one for encryption and one for decryption. 2.The sender and receiver must share the algorithm and the 2.The sender and receiver must each have one of the matched key. pair of keys(not the same one). Needed for Security: Needed for Security: 1.The key must be kept secret. 1.One of the two keys must be kept secret. 2.It must be impossible or at least impractical to decipher a 2.It must be impossible or at least impractical to decipher a message if no other information is available. message if no other information is available. 3. Knowledge of the algorithm plus samples of ciphertext must 3. Knowledge of the algorithm plus one of the keys plus be insufficient to determine the key. samples of ciphertext must be insufficient to determine the other key. 2022/10/9 现代密码学理论与实践-09 8/34

2022/10/9 现代密码学理论与实践-09 8/34 常规和公开密钥加密的重要特征

因海冷K大 公开密钥密码系统：保密性 1950 C=KUp(M) Cryptanalyst M=KRp(C) KRb Source A Destination B Message X Encryption Decryption X Destination Source Algorithm Algorithm KUb KRb Key Pair Source Figure 9.2 Public-Key Cryptosystem:Secrecy 2022/10/9 现代密码学理论与实践-09 9/34

2022/10/9 现代密码学理论与实践-09 9/34 公开密钥密码系统：保密性 C = KUb (M) M = KRb (C)

公开密钥密码系统：认证 车不 105 S=KRa(M) M=KUa(S) Cryptanalyst Source A Destination B Message Encryption Y Decryption Source Destination Algorithm Algorithm KRa KUa Key Pair Source Figure 9.3 Public-Key Cryptosystem:Authentication 甲 2022/10/9 现代密码学理论与实践-09 10/34

2022/10/9 现代密码学理论与实践-09 10/34 公开密钥密码系统：认证 S = KRa (M) M = KUa (S)

公开密钥密码系统：保密和认证 15 C=KR(KUp(M)) M=KRp(KU(C)) Source A Destination B Z Message Encryption Encryption Decryption Decryption Message Source Algorithm Algorithm Algorithm Algorithm Dest. KUb KRb Key Pair Source KRa KUa Key Pair Source Figure 9.4 Public-Key Cryptosystem:Secrecy and Authentication 2022/10/9 现代密码学理论与实践-09 11/34

2022/10/9 现代密码学理论与实践-09 11/34 公开密钥密码系统：保密和认证 C = KRa (KUb (M)) M = KRb (KUa (C))