公钥加密法RSA与EIGamal.ppt

公钥加密法 Cipher Classification Public Key Systems 公钥体系又称为非对称加密体系 加密原理主要依赖数学理论而不是替换、置换操作 加密和解密使用不用的密钥 已知某一个，不能推出另一个 Public Key Process 对称（单）密钥面临的最大问题是密钥管理 有权访问明文的人都必须具有该密钥 一旦有人泄露密钥，等于泄露了所有密文 非对称（双）密钥体系里，加密密钥公开，解密密钥必威体育官网网址不公开 Public Key Transaction 举例：Alice 使用一个公开密钥发信息给Bob Public Key Requirements 很容易生成公钥和私钥 很容易加密和解密 从公钥很难得出私钥 利用密钥和公钥很难得出明文 RSA算法原理 Exponentiation Ciphers（指数加密） RSA算法基于指数加密概念，即利用乘法生成密钥； 密钥生成过程： 将明文字符转换成整数M 使用如下的指数+取模运算得到密文C (e 和n 为公开密钥) Decipher 要解密密文C得到明文M，必须使用私钥d : RSA Cipher 具体过程（e ,n ,d的确定）： 选择两个大素数 p and q，相乘得到 n = pq； 选取一个整数 d （介于min（p，q）和(p-1)(q-1) 之间）： d 要满足与? (n)=(p-1)(q-1) 互质 ，即两者之间没有公因子 计算数字e ed mod ? (n) = 1 公开n和 e ，对于 p, q, 和 d 必威体育官网网址 RSA Operation 加密过程： 将明文分成若干个信息块，每块用一个整数来表示，比如第一块对应的整数位M 根据m,e和n计算得到密文c c = Me mod n 解密过程： 计算M= cd mod n 只有 d 的拥有者才能解开密文，要想找出d，必须知道 p 与q，找出p 与q的唯一方法是将n分解因子 因此RSA的安全性依赖于n分解因子的难度 RSA 实例 选取两个素数 p 与 q : p = 41, q = 53； 计算 n = pq = 2173 ， (p-1)(q-1) = 40*52 = 2080； 选取 与2080互素的d （取值介于 42 ~ 2079 ), d = 623； 根据 ed = 1 mod 2080计算 e ； 结果 e = 207 加密 加密明文：Hi H—72，i—105 n = 2173， e = 207 加密72得到597，加密105得到2013 将597，2013发送 解密 收到597，2013 n = 2173， d = 623 解密597得到72，解密2013得到623 El Gamal 公钥加密方案 Diffie-Hellman key distribution scheme 的变形 能够用于安全交换密钥 published in 1985 by ElGamal: T. ElGamal, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Trans. Information Theory, vol IT-31(4), pp469-472, July 1985. 安全性是基于离散对数 缺点：增加了消息长度（2倍） 13 密钥建立 密钥生成： 选取一个大素数p及本原元a mod p 接收者 Bob有一个密秘钥 xB 计算 yB = axB mod p 14. El Gamal 加密 为加密 M 发送者选择随机数k, 0=k=p-1 计算消息密钥 K : K = yBk mod p 计算密文对: C = {C1,C2} C1 = ak mod p C2 = K.M mod p 发送到接收者 k 需要永久必威体育官网网址 15. El Gamal 解密 首先计算 message key K K = C1xB mod p = ak.xB mod p 计算明文: M = C2.K-1 mod p 16. El Gamal Example 选择 p=97 及本原根 a=5 recipient Bob 选择 秘密钥xB=58 计算并发布公钥yB=558=44 mod 97 Alice 要加密 M=3 to Bob 首先得到 Bob的公开密钥 yB=44 选择随机 k=36 计算:K=4436=75 mod 97 计算密文对: C1 = 536 = 50 mod 97 C2 = 75.3 mod 97 = 31 mod 97 发送 {50,31} to