《北京交通大学密码学第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