第10讲--公钥加密算法-(续).ppt

1 公钥加密 公钥加密算法 用于加密任何消息常能用于签名和密钥交换eg RSA ElGamal基于不同有限域的指数运算 galois整数域 ellipticcurvesetc 其它问题的公钥体制 ErrorCorrectingCodes 大多数都被攻破 2 RSA Rivest Shamir Adleman 使用最广泛的公钥加密算法Rivest Shamir Adleman RSA in1977RLRivest AShamir LAdleman OnDigitalSignaturesandPublicKeyCryptosystems CommunicationsoftheACM vol21no2 pp120 126 Feb1978 3 RSASetup 每个用户生成自己的公钥 私钥对 选择两个随机大素数 100digit p q计算模数N p q选择一个随机加密密钥匙e e N gcd e N 1解下列同余方程 求解密密钥d e d 1mod N and0 d N公开加密密钥 Kr er Nr 保存其解密似钥 K 1r d p q 4 RSA参数选择 需要选择足够大的素数p q通常选择小的加密指数e 且与 N 互素e对所有用户可以是相同的最初建议使用e 3现在3太小常使用e 216 1 65535解密指数比较大 5 RSAUsage 要加密消息M 发送者要得到接收者的公钥Kr er Nr 计算 C MermodNr where0 M N为解密C 接收者使用私钥K 1r d p q 计算 M CdmodNr 6 RSA理论 RSA基于Fermat sTheorem ifN pqwherep qareprimes then X N 1modNforallxnotdivisiblebyporq iegcd x N 1where N p 1 q 1 但在RSA中 e d是特殊选择的iee d 1mod N 或e d 1 R N hencehave M Cd Me d M1 R N M1 M N R M1 1 R M1modN 8 RSA举例 例子 1 选素数p 47和q 71 得n 3337 n 46 70 3220 2 选择e 79 求得私钥d e 1 1019 mod3220 3 公开n 3337和e 79 4 现要发送明文688 计算 68879 mod3337 15705 收到密文1570后 用私钥d 1019进行解密 15701019 mod3337 688 9 RSA安全性 RSA安全性基于计算 N 的困难性要求分解模N 10 RSA的实现问题 需要计算模300digits or1024 bits 的乘法计算机不能直接处理这么大的数 计算速度很慢 需要考虑其它技术 加速RSA的实现 11 RSA 的快速实现 加密很快 指数小解密比较慢 指数较大利用中国剩余定理CRT CRT对RSA解密算法生成两个解密方程 利用M CdmodR 即 M1 Mmodp Cmodp dmod p 1 M2 Mmodq Cmodq dmod q 1 解方程M M1modpM M2modq具有唯一解 利用CRT M M2 q M1 umodq p M1其中p umodq 1 12 ElGamal公钥加密方案 Diffie Hellmankeydistributionscheme的变形能够用于安全交换密钥publishedin1985byElGamal T ElGamal APublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms IEEETrans InformationTheory volIT 31 4 pp469 472 July1985 安全性是基于离散对数缺点 增加了消息长度 2倍 13密钥建立 密钥生成 选取一个大素数p及本原元amodp接收者Bob有一个密秘钥xB计算yB axBmodp 14 ElGamal加密 为加密M发送者选择随机数k 0 k p 1计算消息密钥K K yBkmodp计算密文对 C C1 C2 C1 akmodpC2 K Mmodp发送到接收者k需要永久保密 15 ElGamal解密 首先计算messagekeyKK C1xBmodp ak xBmodp计算明文 M C2 K 1modp 16 ElGamalExample 选择p 97及本原根a 5recipientBob选择秘密钥xB 58 计算并发布公钥yB 558 44mod97Alice要加密M 3toBob首先得到Bob的公开密钥yB 44选择随机k 36计算 K 4436 75mod97计算密文对 C1 536 50mod97C2 75 3mod97 31mod97发送 50 31 toBobBob恢复messagekeyK 5058 75mod97Bob计算K 1 22mod97Bob恢复明文M 31 22 3mod97 17 公钥密码现状 已知的安全算法是有限域上指数运算素数域GF p 上的整数运算多项式运算GF 2 n 椭圆曲线上的运算 ellipticcurves hardertocomputesousesmallersizes 基于其它困难问题的体制 18 公钥密码方案的实际应用 实现速度通常用于交换对称算法的加密密钥数字签名算法 下节内容 19小结 RSA算法ElGamal算法实现问题 Exercises IllustratetheoperationofRSA giventhefollowingparameters Systemmodulusn 119 7x17 encryptionexpe 11Determinethe