第四讲-非对称密码体制.pptVIP

* 非对称密码体制 第四讲 * 非对称密码算法又称公开密钥算法或双密钥体制，即密钥分为公钥和私钥，公钥可以公开，私钥需必威体育官网网址。 RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来 公钥算法的出现，给密码的发展开辟了新的方向。公钥在鉴别系统和密钥交换等安全技术领域起着关键的作用 一、概述 * 对称密码体制的问题 加密能力与解密能力是捆绑在一起的 密钥更换、传递和交换需要可靠信道 密钥管理量的困难：传统密钥管理：两两分别用一个密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如: n=100 时， C(100,2)=4,995 n=5000时， C(5000,2)=12,497,500 无法满足不相识的人之间通信的必威体育官网网址要求 对称密码至少两人共享，不带个人特征，不能实现数字签名，实现抗抵赖的需求。 一、概述 * 非对称密码体制特点： 加密能力与解密能力是分开的：数据加密和解密使用不同的密钥，从而构成了不对称体制。加密密钥可以公开，算法也可以公开，只要求解密密钥必威体育官网网址 知道加密算法,从加密密钥得到解密密钥在计算上是不可行的 两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的)：X = DKR(EKU(X)) = EKU(DKR(X)) 密钥分发简单 需要保存的密钥量大大减少，N个用户只需要N对 可满足不相识的人之间必威体育官网网址通信 可以实现数字签名 基于数学函数（数论）而不是基于替换和置换， 一、概述 * 公钥密码体制： 假设明文为X，密文为Y, 加密密钥为ke（公钥），解密密钥为kd（私钥），加密算法为E(ke, X) ，解密算法为D(kd, Y) ，则非对称密码体制应满足以下条件： ①已知ke，不难计算E(ke, X)； ②不知道kd，即使知道ke, E, D及Y，计算X也不可行；或者说利用公钥来推断私钥是计算不可行的 ③存在并已知kd，不难计算D(kd, Y) ④对明文X, E(ke, X)有定义，且D(kd, E(ke, X))=X ⑤对密文Y, D(kd, Y)有定义，且E(ke, D(kd, Y))=Y 说明：－满足条件①、 ②的函数为单向函数 －满足条件①、②、③的函数为单向陷门函数（trapdoor) 条件③表示陷门性，kd是陷门信息。 －防治陷门信息的破译要依靠计算难的问题 －条件④和⑤表明加密和解密是互逆的，且无操作顺序约束，即 (可选)加密和解密的顺序可交换。 一、概述 * 公钥密码的应用范围： ?加密/解密 ?数字签名 ?密钥交换 二、公钥密码的应用模式 * 用公钥密码实现加解密 每个用户拥有自己的密钥对（ ， ） 公钥 公开，私钥 必威体育官网网址 加密： 解密： 二、公钥密码的应用模式 * 基于公开密钥的鉴别（数字签名） 用户A把自己的公钥发给B( 如需要，可发给所有相关的人） 鉴别： A→B(或所有的人）: B(或所有的人): 二、公钥密码的应用模式 * 鉴别+必威体育官网网址 A用其私钥加密，得到数字签名，然后，再用B的公钥加密 二、公钥密码的应用模式 * 三、公开密钥密码体制 公钥算法的安全性完全建立在计算复杂性理论基础上，或者说建立在对一个特定的数学难题求解的困难上（NP问题）。 背包问题 又称子集合问题（subsetsum)，属于NP问题。 大整数分解问题 （The Integer Factorization Problem, RSA体制） 离散对数问题 有限域的乘法群上的离散对数问题 (The Discrete Logarithm Problem, ElGamal体制） 椭圆曲线上的离散对数问题 （The Elliptic Curve Discrete Logarithm Problem,类比的 ElGamal体制） * 四、若干数论基础 设a、b为整数，且不全为0， 则gcd(a,b)表示a和b的最大公因子。 如果gcd(a,b)=1，称a和b互为素数（互素）。 模运算： 如果a是一个整数，而n 是一个正整数，则定义 a mod n 为a 除以n 的余数。例如，30 mod 7 = 2。 因为在模n 运算下，余数一定在0到(n- 1)之间。因此，模n 运算将所有整数映射到整数集合{0, 1. …, (n – 1)