第3讲公钥密码学.ppt

* * * * 网络与信息安全技术第三讲公钥密码 华中科技大学软件工程硕士课程 公钥密码学的历史 76年Diffie和Hellman发表了“密码学的新方向”, 奠定了公钥密码学的基础 公钥技术是二十世纪最伟大的思想之一 改变了密钥分发的方式 广泛用于数字签名和身份认证服务 78年, RSA算法 对称算法的不足 密钥管理量的困难！ 传统密钥管理: 两两分别用一个密钥时, 则n个用户需要C(n,2)=n(n-1)/2个密钥, 当用户量增大时,密钥空间急剧增大, 如: n=100 时, C(100,2)=4,995 n=5000时, C(5000,2)=12,497,500 对传输信道安全性的要求！ 密钥必须通过某一信道协商传输，对这个信道的安全性的要求比正常的传送消息的信道的安全性要高 数字签名问题！ 传统加密算法无法实现抗抵赖的需求 公钥体制加密的框图 公钥体制认证的框图 公钥体制认证必威体育官网网址的框图 公钥密码基于的数学难题 ? 背包问题 ? 大整数分解问题 ( RSA体制 ) ? 离散对数问题 有限域的乘法群上的离散对数问题 (ElGamal体制) 定义在有限域的椭圆曲线上的离散对数问题 (类比的ElGamal体制) 公钥密码主要算法 Diffie-Hellman密钥交换算法 背包算法 RSA算法 EIGamal算法 椭圆曲线密码算法ECC Diffie-Hellman密钥交换 RSA算法 1977年由Ron Rivest、Adi Shamir和Len Adleman发明, 1978年公布; ? 是一种分组加密算法; – 明文和密文在0~n-1之间, n是一个正整数 ? 应用最广泛的公钥密码算法; ? 只在美国申请专利, 且已于2000年9月到期; RSA算法 RSA密钥生成与使用 产生密钥对 选择两个大素数p,q, p?q 计算n=pq,?(n)=(p-1)(q-1) 选择整数e,使得gcd(e,?(n))=1 计算d ? e-1 mod ?(n) 公钥: KU={e,n}, 私钥: KR={d,n} 使用: 将明文划分成块, 使得每个明文报文P长度m满足0mn 加密: C = me mod n 解密: m = Cd mod n RSA算法中的计算问题 ① 如何计算ab mod n ② 密钥产生 ① 如何计算ab mod n ? 中间结果非常大 6677 mod 119, 先求6677再取模, 则中间结果就已远远超出了计算机允许的整数取值范围 (a x b) mod n = [(a mod n) x (b mod n)] mod n] ? 幂运算的效率 求x16, 直接计算的话需做15次乘法. 然而如果重复对每个部分结果做平方运算即求x, x2, x4, x8, x16则只需4次乘法。 求am可如下进行, 其中a，m是正整数： 将m表示为二进制形式bk bk-1…b0，即 m=bk2k+bk-12k-1+…+b12+b0 因此 例: 19=1×24+0×23+0×22+1×21+1×20，所以a19=((((a1)2a0)2a0)2a1)2a1 从而可得以下快速指数算法： c=0; d=1； for i=k downto 0 d0 { c=2×c; d=(d×d) mod n; if bi=1 then { c=c+1; d=(d×a) mod n } } return d. d是中间结果, d的终值即为所求结果. c在这里的作用是表示指数的部分结果, 其终值即为指数m c对计算结果无任何贡献, 算法中完全可将之去掉 密钥产生 ? 如何找到足够大的素数p和q? ? 选择e或d计算另外一个? 选取满足1eφ(n)和gcd(φ(n),e)=1的e, 并计算满足d·e≡1 mod φ(n)的d, 可由推广的Euclid算法完成. 大素数产生 素数生成过程: ?随机选择一个奇数n(如通过伪随机数发生器) ?随机选择a, 使an ?进行素性测试(例如用Miller-Rabin算法),若n没有通过测试,抛弃n,转到? ?如果通过了足够次数的测试,认为n是素数,否则转到?. 素性测试 Miller-Rabin算法：用来测试一个整数p是否是素数 基于fermat定理：ap-1=1 mod p 欧几里得算法 欧几里得(Euclid)算法:求两个正整数的最大公因子的简化过程 对任意非负整数a和正整数b, 有gcd(a, b)=gcd(b, a mod b). 例如: gcd(55, 22)=gcd