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

195 3 现代密码学理论与实践 第9章公钥密码学与RSA 苗付友 mfy@ustc.edu.cn 2018年11月 网络视频：http://wlkt.ustc.edu.cn/video/detail.3363_0.htm

苗付友 mfy@ustc.edu.cn 2018年11月 网络视频：http://wlkt.ustc.edu.cn/video/detail_3363_0.htm

本章要点 丶 Diffie- Hellmanη秘钥交换 〉非对称密码是一种密码体制,其加密算法和解密算法 使用不同的密钥,一个是公钥,一个是私钥。非对称 密码也称为公钥密码。 非对称密码用两个密钥中的一个以及加密算法将明文 转换为密文,用另一个密钥以及解密算法从密文恢复 出明文。 非对称密码可以用来保密、认证或者两者兼而有之。 〉应用最广泛的公钥密码体制是RSA,破解RSA的困难, 是基于分解大合数的素因子的困难。 ash mfy@ustc.edu.cn 现代密码学理论与实践 2/54

mfy@ustc.edu.cn 现代密码学理论与实践 2/54  Diffie-Hellman秘钥交换  非对称密码是一种密码体制，其加密算法和解密算法 使用不同的密钥，一个是公钥，一个是私钥。非对称 密码也称为公钥密码。  非对称密码用两个密钥中的一个以及加密算法将明文 转换为密文，用另一个密钥以及解密算法从密文恢复 出明文。  非对称密码可以用来保密、认证或者两者兼而有之。  应用最广泛的公钥密码体制是RSA，破解RSA的困难， 是基于分解大合数的素因子的困难

本章目录 >9.1 Diffie- Hellman密钥交换 >9.2公开密钥密码体制的基本原理 09,2.1基本概念 092.2应用方法 09.23功能 09,2.4对公开密钥密码编码系统的要求 9.3RSA公钥系统 93.1RSA密码体制基本原理 0932RSA的安全性 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 3/54

mfy@ustc.edu.cn 现代密码学理论与实践 3/54  9.1 Diffie-Hellman密钥交换  9.2 公开密钥密码体制的基本原理 ◦ 9.2.1基本概念 ◦ 9.2.2 应用方法 ◦ 9.2.3 功能 ◦ 9.2.4 对公开密钥密码编码系统的要求  9.3 RSA公钥系统 ◦ 9.3.1 RSA密码体制基本原理 ◦ 9.3.2 RSA的安全性

Whitfield Diffie and martin Hellman Whitfield diffie Martin hellman Born in 1944/ fascinated in math/ Prof of Stanford Univ /Born in 1945/ to be Graduated from MIT 1965/ freethinking different->cipher with The Coderbreakers independent cryptographer in 1970s /1974, 9 Diffie insightful in the significance of Key Distribution in then rising arpanet/ visit to iBM lab in Setp. 1974> Martin Hellman ash mfy@ustc.edu.cn 现代密码学理论与实践

mfy@ustc.edu.cn 现代密码学理论与实践 4/54 Whitfield Diffie Martin Hellman Born in 1944/ fascinated in Math/ Graduated from MIT 1965/ freethinking independent cryptographer in 1970s/ insightful in the significance of Key Distribution in then rising ARPAnet / visit to IBM lab in Setp.1974 → Martin Hellman Prof. of Stanford Univ./Born in 1945/ to be different->cipher with The Coderbreakers /1974,9 Diffie

Ralph, like us, was willing to be a fool. and the way to get to the top of the heap in terms of developing original research is to be a fool, because only fools keep trying. You have idea number 1, you get excited, and it flops. Then you have idea number 2, you get excited, and it flops. Then you have idea number 9, you get excited, and it flops. Only a fool would be excited by the 100th idea, but it might take 100 ideas before one really pays off. Unless you're foolish enough to be continually excited, you won't have the motiva- tion, you won't have the energy to carry it through. God rewards fools Martin hellman Finding a one-way function ash mfy@ustc.edu.cn 现代密码学理论与实践 5/54

mfy@ustc.edu.cn 现代密码学理论与实践 5/54  Finding a one-way function --Martin Hellman

9.1 Diffie- Hellman密钥交换 Dfle和 Hellman在1976年首次提出了公钥算法, 给出了公钥密码学的定义,该算法通常被称为 Dffe- Hellman密钥交换算法 丶 Diffie- Hellman密钥交换算法是一种公钥分发机制 它不是用来加密消息的 所生成的是通信双方共享的会话密钥,必须保密,其 值取决于通信双方的私钥和公钥信息 Diffie- Hellman密钥交换算法是基于有限域GF中 的指数运算的(模一素数或多项式) 丶 Diffie- Hellmanη密钥交换算法的安全性依赖于求解 离散对数问题DLP ash NolL. edu.cn 现代密码學港学理奖践-10

mfy@ustc.edu.cn 2021/1/31 现代密码学理论与实践 现代密码学理论与实践-10 66/54 /57  Diffie和Hellman在1976年首次提出了公钥算法， 给出了公钥密码学的定义，该算法通常被称为 Diffie-Hellman密钥交换算法  Diffie-Hellman密钥交换算法是一种公钥分发机制 ◦ 它不是用来加密消息的 ◦ 所生成的是通信双方共享的会话密钥，必须保密，其 值取决于通信双方的私钥和公钥信息  Diffie-Hellman密钥交换算法是基于有限域GF中 的指数运算的(模一素数或多项式)  Diffie-Hellman密钥交换算法的安全性依赖于求解 离散对数问题DLP

9.1.1离散对数问题回顾 如果a是素数p的一个原根(本原元素),则 a mod p,a2modp,……,ap- mod p,生成模p的完全剩余集 {1,2 ·"■··· 对于所有素数,其原根必定存在,即 对于一个整数b和素数p的一个原根,可以找到唯一的指数,使得 b= a' mod p,其中0<=i<=p-1 指数i为b的以a为基数的模p的离散对数或者指数。 〉离散对数密码体制的安全性基于DLP问题,在下式中已知C和P 的情况下,由d求M很容易,由M求d很困难, d= log M in GF(P), 最快的算法需要T=eXp(n(Pnn(P)/2)次运算。当P是200 位时,T=2.7×101,如果1us解一次,需要2~3天;如果P 664位,则T=12×1023,约1012天或2.739X109年,约2.7亿 年只要P是够大可以达到足够安年 mfy@ustc.edu.cn 现代密码学理论与实践 7/54

mfy@ustc.edu.cn 现代密码学理论与实践 7/54  如果a是素数p的一个原根(本原元素)，则 a mod p, a2 mod p, ......, ap-1 mod p，生成模p的完全剩余集 {1, 2, ......, p-1} 对于所有素数，其原根必定存在，即 对于一个整数b和素数p的一个原根，可以找到唯一的指数i, 使得 b = a i mod p, 其中 0<= i <= p-1 指数i称为b的以a为基数的模p的离散对数或者指数。  离散对数密码体制的安全性基于DLP问题, 在下式中已知C和P 的情况下, 由d求M很容易, 由M求d很困难, d = logCM in GF(P),  最快的算法需要T=exp((ln(P)lnln(P)1/2)次运算。当P是200 位时, T = 2.7x1011 , 如果1μs解一次, 需要2~3天；如果P = 664位, 则T = 1.2x1023 , 约1012天或2.739x109年, 约2.7亿 年. 只要P足够大,可以达到足够安全

DLP与DHP DLP Given p, a and b, find x such that b=a- mod p DHP g is the generator of Fp, given g mod p and g modp, find gry moa p DLP→DHP DLP=?DHP 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 8/54

mfy@ustc.edu.cn 现代密码学理论与实践 8/54  DLP ◦ Given p, a and b, find x such that b=ax mod p.  DHP ◦ g is the generator of Fp , given g x mod p and g y mod p, find g xy mod p.  DLP→DHP,  DLP=?DHP

9.1.2 Diffie-Hellman Key Exchanges 通信双方约定一个大素数(或多项式)p,和模p的一个素根 各方产生公开密钥 选择一个秘密钥数值),如ⅹA<p,XB<p 计算公钥,如yA= a a mod p,yg= a mod p,并相互交换 双方共享的会话密钥KA可以如下算出 aB mod yA mod p(which B can compute yB mod p(which A can compute KAB是双方用对称密码通信时共享的密钥 〉如果双方继续通信,可以继续使用这个密钥,除非他们 要选择新的密钥 攻击者如果想要获得KAB=a,则必须解决DHP问题 ash mfy@ustc.edu.cn 现代密码学理论与实践 9/54

mfy@ustc.edu.cn 现代密码学理论与实践 9/54  通信双方约定一个大素数(或多项式)p, 和模p的一个素根 α  各方产生公开密钥 ◦ 选择一个秘密钥(数值)，如xA< p， xB< p ◦ 计算公钥, 如yA = α xA mod p, yB = α xB mod p, 并相互交换  双方共享的会话密钥KAB可以如下算出 KAB = α xA·xB mod p = yA xB mod p (which B can compute) = yB xA mod p (which A can compute)  KAB是双方用对称密码通信时共享的密钥  如果双方继续通信，可以继续使用这个密钥，除非他们 要选择新的密钥  攻击者如果想要获得KAB = α xA·xB , 则必须解决DHP问题

Key exchange构造条件 条件 单向性 例如:离散对数的单向性 gx modp-\→X 交换性 例如:离散对数的单向性:(g×)y=(gy) X mod p 复用性 私有密钥可复用(量子计算环境下可能不满足 〉椭圆曲线上的离散对数问题也可以构造 Diffie- Hellmen Key Exchange 尝试其他可交换单向函数构造 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 10/54

mfy@ustc.edu.cn 现代密码学理论与实践 10/54  条件 ◦ 单向性  例如：离散对数的单向性 gx modp-\→x ◦ 交换性  例如：离散对数的单向性: (gx) y=(gy ) x mod p ◦ 复用性  私有密钥可复用（量子计算环境下可能不满足）  椭圆曲线上的离散对数问题也可以构造Diffie￾Hellmen Key Exchange  尝试其他可交换单向函数构造…