《北京交通大学密码学第9-10章公钥密码1》由会员分享，可在线阅读，更多相关《北京交通大学密码学第9-10章公钥密码1（62页珍藏版）》请在金锄头文库上搜索。
1、第9-10章 公钥密码 本章内容 公钥密码体制的基本原理 数论基础 RSA算法 Diffie-Hellman密钥交换算法 ElGamal密码体制 椭圆曲线密码体制ECC 公钥密码体制的基本原理 公钥密码体制的提出和起源 公钥密码的特点 公钥密码的应用 公钥密码的要求 公钥密码的理论基础 公钥密码体制的基本原理 公钥密码以前：所有的密码算法都是基于代换和置换这 两个基本工具。 而公钥密码体制为密码学的发展提供了新的理论和技术 基础 基本工具是数学函数 公钥密码算法是以非对称的形式使用两个密钥，两个 密钥的使用对保密性、密钥分配、认证等都有着深刻 的意义。 可以说公钥密码体制的出现在密码学史上是一
2、个最大的 而且是惟一真正的革命。 问题的提出 公钥密码体制的概念是在解决单钥密码体制中最难解决的两 个问题时提出的，这两个问题是密钥分配和数字签字。 密钥分配问题 通信双方要进行加密通信，需要通过秘密的安 全信道协商加密密钥，而这种安全信道可能很难实现； 密钥管理问题 ：两两分别用一对密钥时，则n个用户需要 C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增 大。如: n=100 时， C(100,2)=4,995 n=5000时， C(5000,2)=12,497,500 没有签名功能：当主体A收到主体B的电子文挡（电子数据 ）时，无法向第三方证明此电子文档确实来源于B，无
3、法实 现抗抵赖的需求。 起源 公钥密码又称为双钥密码和非对称密码，是1976年由 Stanford大学的Diffie和Hellman在其“密码学新方向” 一文中提出的，见划时代的文献： W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654 RSA公钥算法是由Rivest,Shamir和Adleman在1978年提 出来的, 见：Communitions of the ACM. Vol
4、.21.No.2. Feb. 1978, PP.120-126. 公钥密码的重要特性 加密与解密由不同的密钥完成 加密: XY: Y = EKU(X) 解密: YX: X = DKR(Y) = DKR(EKU(X) 知道加密算法,从加密密钥得到解密密钥在计算上是不可 行的 两个密钥中任何一个都可以用作加密而另一个用作解密 (不是必须的) X = DKR(EKU(X) = EKU(DKR(X) 基于公开密码的加密过程 用户拥有自己的密钥对(KU,KR)，公钥KU公开,私钥KR保密 Bob Alice: Y=EKUa(X) Alice: DKRb(Y)= DKRa(EKUa(X)=X 基于公开密码
5、的鉴别过程 条件: 两个密钥中任何一个都可以用作加密而另一个用作解密 鉴别: AilceALL: Y=EKRa(X) ALL: EKUa(Y)=DKUa(EKRa(X)=X 基于公开密码的鉴别过程 在实际应用中，特别是用户数目很多时，以上认证方法 需要很大的存储空间，因为每个文件都必须以明文形式 存储以方便实际使用，同时还必须存储每个文件被加密 后的密文形式即数字签字，以便在有争议时用来认证文 件的来源和内容。 改进的方法是减小文件的数字签字的大小，即先将文件 经过一个函数压缩成长度较小的比特串，得到的比特串 称为认证码。 认证码具有这样一个性质：如果保持认证码的值不变而 修改文件这在计算上是
6、不可行的。 用发送者的秘密钥对认证码加密，加密后的结果为原文 件的数字签字。 基于公开密码的鉴别+保密过程 鉴别+保密: A B: Z= EKUb(EKRa(X) B: DKUa(DKRb(Z)=X 公钥密码的应用范围 加密/解密（保密性） 数字签名(身份鉴别) 密钥交换（会话密钥） 基本思想和要求 涉及到各方：发送方、接收方、攻击者 涉及到数据：公钥、私钥、明文、密文 公钥算法的条件： 产生一对密钥是计算可行的 已知公钥和明文，产生密文是计算可行的 接收方利用私钥来解密密文是计算可行的 对于攻击者，利用公钥来推断私钥是计算不可行的 已知公钥和密文，恢复明文是计算不可行的 (可选)加密和解密的
7、顺序可交换 其中最后一条虽然非常有用，但不是对所有的算法都作要求。 公钥密码的理论基础 难解问题：没有有效算法，求解所需时间非常长。 易解问题：存在有效算法，求解所需时间短 一般来说计算一个难解的问题所需要的时间通常是所输 入数据长度的一个指数函数，因此计算时间是随着数据 长度的增加急剧增加的。 陷门单向函数 公钥密码是建立在陷门单向函数上的。 单向函数（one way function）： (1)给定x，计算y=fk(x)是容易的； (2)给定y, 计算x使y=fk-1(x)是不可行的。 陷门单向函数（trapdoor one way function）: (1)给定x，计算y=fk(x)是
8、容易的； (2)给定y, 计算x使y=fk-1(x)是不可行的。 (3)存在k，已知k 时,对给定的任何y，若相应的x存在， 则计算x使y=fk-1(x)是容易的。 研究公钥密码算法就是要找出合适的陷门单向函数。 公钥密码体制的安全性 像对称密码体制一样，密钥穷搜索攻击理论上是有效的 ； 但是使用的密钥太大 (512bits) 安全性依赖于难解问题； 一般难解问题是已知的，但是需要设计的足够难； 需要使用很大的数； 因此比对称密码算法要慢； 数论基础 1、素数 2、模运算 3、Euclid算法 4、费马定理和欧拉定理 5、素性测试 6、中国剩余定理 7、离散对数 见：第8章 数论入门.ppt
9、经典例子 RSA算法 Diffe-Hellman密钥交换算法 ElGamal密码体制 椭圆曲线密码体制ECC RSA公开密钥算法 RSA算法描述 RSA的实现问题 RSA的安全性 RSA公开密钥算法 1977年由Ron Rivest、Adi Shamir和Len Adleman发明，1978年公布 是一种分组加密算法 明文和密文在0n-1之间,n是一个正整数 用数论构造 迄今为止理论上最为成熟完善的公钥密码体制 应用最广泛的公钥密码算法 只在美国申请专利，且已于2000年9月到期 RSA公开密钥算法算法描述 算法的论证 RSA算法的论证 加密和解密运算的可交换性 D(E(M)=(Me)d=(M
10、d)e=E(D(M) mod n 所以,RSA密码可同时确保数据的秘密性和真实性 加解密算法的有效性 RSA密码的加解密运算是模幂运算，有比较有效的算法 RSA算法的论证 在计算上由公开密钥不能求出解密钥 小合数的因子分解是容易的，然而大合数的因子分解确 是十分困难的。关于大合数的因子分解的时间复杂度下 限目前尚没有一般的结果，迄今为止的各种因子分解算 法提示人们这一时间下限将不低于O(EXP(lnNlnlnN)1/2)。 根据这一结论，只要合数足够大，进行因子分解是相当 困难的。 RSA算法的论证 假设截获密文C, 从中求出明文M。他知道 MCd mod n， 因为n是公开的，要从C中求出明
11、文M，必须先求出d，而 d是保密的。但知道， ed1 mod (n)， E是公开的，要从中求出d，必须先求出(n)，而(n)是 保密的。 RSA算法的论证 在计算上由公开密钥不能求出解密密钥 但知道，(n)=(p-1)(q-1) 要从中求出(n)，必须先求出p和q，而p和q是保密的。 知道 n=pq，要从n求出p和q，只有对n进行因子分解。 而当n足够大时，这是很困难的。 只要能对n进行因子分解，便可攻破RSA密码。由此可以 得出，破译RSA密码的困难性=对n因子分解的困难性。 目前尚不能证明两者是否能确切相等，因为不能确知除了 对n进行因子分解的方法外，是否还有别的更简捷的破译 方法。 目前
12、只有Rabin密码具有： 破译Rabin密码的困难性=对n因子分解的困难性 RSA算法的论证 RSA的安全性是基于加密函数ek(x)=xe(mod n)是一个单 向函数，所以对的人来说求逆计算不可行。 而Bob能解密的陷门是分解n=pq，知 (n)=(p-1)(q-1)。从 而用扩展的Euclid算法解出解密私钥d。 密码分析者攻击RSA体制的关键点在于如何分解n。若分 解成功使n=pq，则可以算出(n)（p-1)(q-1)，然后由 公开的e，解出秘密的d。 猜想：攻破RSA与分解n是多项式等价的。然而，这个猜 想至今没有给出可信的证明！ 两个问题和两个假设 RSA的安全性是基于RSA假设，而
13、不是基于分解大整数的困难性假定 RSA算法举例 RSA密码体制的实现 实现的步骤如下：Bob为实现者 (1) Bob寻找出两个大素数p和q (2) Bob计算出n=pq和 (n)=(p-1)(q-1). (3) Bob选择一个随机数e(0e (n)，满足(e, (n)=1 (4) Bob使用辗转相除法计算d=e-1(mod (n) (5) Bob在目录中公开n和e作为她的公开钥。 选好这些参数后，将明文划分成块，使得每个明文报文P 长度m满足0mn。 加密P时，计算CPe(mod n)，解密C时计算PCd(mod n)。由于模运算的对称性，可以证明，在确定的范围内， 加密和解密函数是互逆的。
14、为实现加密，需要公开(e, n)，为实现解密需要(d, n)。 RSA的加、解密过程示例 RSA的实现参数选择 为了确保RSA密码的安全，必须认真选择密码参数： p和q要足够大： 一般应用：p和q应512b 重要应用：p和q应1024b p和q应为强素数 文献指出，只要(p-1)、(p+1)、(q-1)、(q+1)四个数之一 只有小的素因子，n就容易分解。 (p-1)和(q-1)的最大公因子要小 如果(p-1)和(q-1)的最大公因子太大，则易受迭代加密 攻击。 RSA的实现参数选择 e的选择 随机且含1多就安全，但加密速度慢。于是，有的学者 建议取e=216+1=65537 d的选择 d不能
15、太小，要足够大 不要许多用户公用一个模n：易受共模攻击 另外两个常用的e的选择是3和17.但是如果e=3。这时加密速 度一般比解密速度快10倍以上。但是易受低指数攻击。 注意：密钥产生要求（e, (n)）=1，因此如果用户选择了 e=65537，接着生成了素数p，q， 很有可能不能满足（e, (n)）=1，因此用户应该去掉那些模65537和1不同余的p和q。 RSA实现中的问题 （1）如何计算ab mod n 需要计算模 300 digits (or 1024+ bits) 的乘法 （2）如何判定一个给定的整数是素数？ （3）如何找到足够大的素数p和q ? 其中d是中间结果，d的终值即为 所求结果。c在这里的作用是表 示指数的部分结果，其终值即为 指数m，c对计算结果无任何贡 献，算法中完全可将之去掉。 快速加解密 加密很快，指数小 解密比较慢，指数较大 利用中国剩余定理CRT，分别计算mod p和m
