《信息网络安全-第5章密码学基础+-双钥密码体制(一)》由会员分享，可在线阅读，更多相关《信息网络安全-第5章密码学基础+-双钥密码体制(一)（35页珍藏版）》请在金锄头文库上搜索。
1、网络安全网络安全技术与技术与实践实践（第（第2版）版）刘建伟刘建伟 王育民王育民 编著编著 清华大学出版社清华大学出版社普通高等教育“十一五”国家级规划教材普通高等教育“十一五”国家级规划教材 教育部教育部2011年精品教材年精品教材课件制作人声明课件制作人声明 本课件总共有17个文件，版权属于刘建伟所 有，仅供选用此教材的教师和学生参考。 本课件严禁其他人员自行出版销售，或未经 作者允许用作其他社会上的培训课程。 对于课件中出现的缺点和错误，欢迎读者提 出宝贵意见，以便及时修订。课件制作人：刘建伟2016年10月11日电子商务：如何确保账户信息安全？双钥双钥密码密码体制（体制（一一）RSA公
2、钥密码算法公钥密码算法二三一ElGamal公钥签名算法公钥签名算法公钥密码体制的基本概念公钥密码体制的基本概念一四其它公钥密码其它公钥密码专题专题：双双钥钥密码密码体制（体制（一一）RSA公钥密码算法公钥密码算法二三一ElGamal公钥签名算法公钥签名算法公钥密码体制的基本概念公钥密码体制的基本概念一四其它公钥密码其它公钥密码1.1 公钥密码的历史公钥密码的历史 1968年，ARPA启动“资源共享计算机网络”建设项目，建成 了ARPANET，将4所大学的计算机联网。40年多来，随着因特 网的迅猛发展，其商业应用得到普及，迫切需要解决保密通信 问题。 1976年，美国斯坦福大学电气工程系的研究员
3、Diffie和Hellman 教授在奠基性论文 “密码学的新方向”中提出公开密钥密码体 制的概念，旨在解决网络通信的两大安全问题：保密与认证。 公钥密码体制的基础，是计算复杂度理论。 单向函数/单向陷门函数 计算上困难问题/NP完全问题为什么需要公钥密码单钥体制的不足回顾：对称（单钥）密码体制会话密钥K会话密钥K相同相同密钥密钥明文m1abc密文EK(m1)#&明文m1abc明文m2def密文EK(m2)$%#明文m2def7/221.2 公钥密码学公钥密码学Martin HellmanD-H算法的设计者Whitfield Diffie1976年，美国的两位著名的密码学家 W. Diffie和
4、M. Hellman提出了公钥密码体制，并尝试构造公钥密码算法，并用 他们的名字命名，称为Diffie-Hellman 算法。W.Diffie,M.Hellman.Newdirectionsin cryptography. IEEE Transactions on Information Theory, 1976, No. 6, Vol. 22, 644-654.D-H协议的核心思想公公钥钥公公钥钥私钥私钥私钥私钥第2步：计算共享密钥 = (,) = (,)Internet第1步：交换公钥公公钥钥公公钥钥Diffie-Hellman公公钥密码思想钥密码思想1.3 理论基础理论基础单向函数单向函
5、数定义1：令函数f是集A到集B的映射，用 f : AB表示。若对于任意x1x2，x1, x2A，有f (x1) f (x2)，则称 f为单射，或1-1映射，或可逆的函数。定义2：一个可逆函数 f : AB，若它满足：(1) 对所有x A，易于计算 f (x)；(2) 对“几乎所有 x A”，由 f (x)求 x 极为困难，以至于几乎是不可能的，则称 f 是一个单向函数。注意：定义中的“极为困难”是相对现有的计算机 资源和算法而言。1.4 理论基础理论基础陷门单向函数陷门单向函数定义3：陷门单向函数是一类满足下述条件的单向函数：fz: AzBz，zZ，Z是陷门信息集合。（1）对所有 zZ，在给定
6、 z 下容易找到一对算法 Ez和 Dz，使对所有xA，易于计算 fz及其逆，即：（2）对所有zZ，当只给定 Ez和 Dz时，对所有 xA，很难从y=fz(x)计算出 x 。区别：单向函数是求逆困难的函数，而陷门单向函数是在不知道陷门信息下求逆困难的函数。当知道陷门信息后，求逆易于实现。xxfDxExfzzzz )()()(1.5 用于构造双钥密码的单向函数用于构造双钥密码的单向函数大整数分解大整数分解FAC ( Factorization Problem ) 离散对数离散对数DL (Discrete Logarithm)多项式求根多项式求根背包问题背包问题 (Knapsack problem)
7、Diffie-Hellman问题问题DHP二次剩余问题二次剩余问题QR (Quadratic Residue) 模模n的平方根问题的平方根问题 (SQROOT) 1.6 公钥密码体制的原理公钥密码体制的原理公钥密码，又称非对称密码或双钥密码(Public-key / Two- key/Asymmetric)，其加密和解密数据使用不同的密钥。明文明文abc加密器加密器 密文密文#&解密器解密器不不同同明文明文abc1.7 公公钥密钥体制的密钥管理钥密钥体制的密钥管理公钥密钥体制解决了密钥的发布和管理问题通信双方可以公开其公开密钥，而保留私钥发方可以用收方公钥对发送的信息进行加密收方用自己的私钥对
8、收到的密文进行解密1.8 公钥密码体制的特点公钥密码体制的特点 每个用户都拥有两个密钥： 由私钥及其他密码信息容易计算出公开密钥 而由公钥及算法描述，计算私钥却非常困难。公钥(public-key)：可以被任何人知道，用于加密或验证签名私钥(private-key)：只能由持有者知道，用于解密或签名1.9 公钥加密方案公钥加密方案AliceAlice 消息消息M M加密机加密机 C=EC=EK1K1(M)(M)解密机解密机 M=DM=DK2K2(C)(C)BobBob 消息消息M MBob公钥 K1Bob私钥 K2EveEve 窃听者窃听者注意：当Alice给Bob发信息时，她必须采用Bob的
9、公钥K1对消 息加密，而不是采用Alice的公钥对消息加密。Bob采用自己的 私钥K2对密文解密。这是同学们最容易搞混的地方。公钥（双钥）密码体制公钥公钥公钥公钥私钥私钥(1)第1步：传递会话密钥 (2)1(1)第2步：消息加密传输2(2)17/22第1步：传递会话密钥第2步：消息加密传输1.9 公钥加密方案公钥加密方案1.10 公钥算法的用途公钥算法的用途用于消息加密用于对消息直接加密 用公钥加密，用私钥解密 公钥加密能够用于密钥分配用于数字签名用用户私钥对消息进行签名 接收方用公钥对签名进行验证用于交换秘密信息， 常用于交换对称加密密钥用于密钥分发1.11 公钥的安全性公钥的安全性 安全性
10、依赖于解数学上的困难问题。 穷搜索（exhaustive search）在理论上能够破解 公钥密码，当密钥足够长 时，破解极其困难。 目前，通常要求足够大的密钥长度 (1024 bits) 密钥太长会导致加密速度缓慢，因此公钥算法 仅用于密钥传递，而不用于实时的数据加密。双钥双钥密码密码体制（体制（一一）RSA公钥密码算法公钥密码算法二三一ElGamal公钥签名算法公钥签名算法公钥密码体制的基本概念公钥密码体制的基本概念一四其它公钥密码其它公钥密码二、二、RSA公钥密码算法公钥密码算法RSA算法, 于1978由Rivest, Shamir, Adleman三人共同提出。2.1 RSA公钥算法说
11、明公钥算法说明 Rivest, Shamir和Adleman 于1977年研制并且1978年首 次公开发表。 RSA是一种分组密码，其理论基础是一种特殊的可 逆模指数运算，其安全性基于分解大整数的困难性。 既可以用于消息加密，也可用于数字签名。 硬件实现时，比DES慢约1000倍。软件实现时比DES 慢约100倍。 已被许多标准化组织（如ISO、ITU、IETF和SWIFT 等)接纳，目前多使用RSA公司的PKCS系列标准； RSA-155（密钥长度512 bit）于1999年分别被分解。2.1 RSA公钥算法说明公钥算法说明 设 n 是两个不同奇素数之积，即 = ，计算其欧 拉函数值 = (
12、 1)( 1)。 随机选一整数, 1 , , = 1因而在模 ()下, 有逆元： = 1mod () 取公钥为, 私钥为 ( p, q不再需要，可以销毁，但 绝不可泄露) 加密变换为 解密变换为nmcmemod nmccdmod 模数大于1024bit，p, q为大素数 p-1，q-1有大的素因子 p+1，q+1也要有大的素因子 e不能太小，最常用的 e 值为3，17，65537 （216+1） 可以用软件/硬件实现 软件与硬件结合,可采用并行算法密钥密钥 选择选择算法算法 实现实现2.2 RSA算法的关键技术算法的关键技术 设Bob的公钥为(e , n)，私钥为 d, 明文为m Alice用
13、Bob的公钥计算：c=memod n，发给B Bob用Bob的私钥计算：m=cdmod n 特点:即使A和B从来不认识，都可进行保密通讯，只要知道B的公钥。速度慢，它不适用于对图像、话音等进行实时数据加密。 要求对公开密钥进行保护，防止修改和替换。2.3 RSA算法的使用算法的使用2.4 RSA算法的举例说明算法的举例说明1. 选p1=47, p2=71, 则n=4771=3337, (n)=4670=3220。若选 e=79，可计算d=e-1(mod 3220)=10192. 公开钥n=3337和e=79，秘密钥d=1019。销毁p1和p2。3. 另明文为x=688 232 687 966
14、668 3，分组得x1=688, x2=232, x3=687, x4=966, x5=668, x6=34. 对x1加密为：(688)79mod 3337=1570=C15. 同样可计算出其它各组密文：y=1570 2756 2714 2423 1586. 对C1解密：(1570) 1019mod 3337=668=x1类似地可解出其它各组密文，恢复出明文。2.5 RSA算法的安全性算法的安全性密钥长（密钥长（bit）所需所需MIPS年年116400129500051230000768200 000 0001024300 000 000 0002048300 000 000 000 000
15、2.6 等价密钥长度等价密钥长度与单钥体制比较与单钥体制比较单钥体制单钥体制RSA体制体制单钥体制单钥体制RSA体制体制56 b384 b112 b1792 b64 b512 b128 b2304 b80 b768 b双钥双钥密码密码体制（体制（一一）RSA公钥密码算法公钥密码算法二三一ElGamal公钥签名算法公钥签名算法公钥密码体制的基本概念公钥密码体制的基本概念一四其它公钥密码其它公钥密码ElGamal于1985年 基于离散对数问题 提出了一个既可用 于数字签名又可用 于加密的密码体制 ；(此数字签名方案 的一个修改被NIST 采纳为数字签名标 准DSS)ElGamal,Schnorr和 DSA签名算法都非 常类似。事实上， 它们仅仅是基于离 散对数问题的一般 数字签名的三个例 子。ElGamal方案未 申请专利。但受 到DH专利的制约 （DH专利已经在 1997年4月29日到 期）。三、三、ElGamal公钥算法公钥算法3.1 ElGamal公钥密码算法公钥密码算法其安全性依赖于离散对数问题（discrete logarithms problem） 参数： GF(p)上的
