《公钥加密》精选课件.ppt

应用密码学 第八章：公钥加密 本章主要内容 1.引言 2.公钥密码的理论基础 3. RSA公钥密码 4. Rabin公钥加密 5. ElGamal公钥密码 1. 引言 1976年，W. Diffie和M. E. Hellman发表论文“New Directions in Cryptography”，提出公钥密码学（public-key cryptography）的思想。 在公钥密码体制（public-key cryptosystem）中，加密密钥 和解密密钥是不一样的，加密密钥的公开传播不危及密码 体制的安全性。 ? 公钥密码体制的概念是在解决单钥密码体制中最难解决的 两个问题时提出的： – 问题一，密钥分配问题 – 问题二，数字签名问题 ? 公钥密码的优点：加密密钥可以公开传播； ? 公钥密码的缺点：运算速度较慢； RSA公钥密码体制的安全性基于大整数的素分解问题的安全性； ElGamal公钥密码体制的安全性基于有限域上的离散对数问题的困难性； Rabin公钥加密方案是第一个被证明了的安全公钥加密方案。 2.公钥密码的理论基础 ? 两个密钥： – 加密密钥简称公钥（public key）； – 解密密钥简称私钥（private/secret key）； – 加密密钥可以公开，解密密钥必威体育官网网址； – 从加密密钥计算解密密钥是难解的； ? 难解问题： – 所谓一个问题是难解的，就是不存在一个计算该问题的 有效算法，否则就是可解的； – P问题与NP问题； – 对于一个安全的密码体制来说，进行破译应该是一个难解问题； 公钥密码原理 每个用户拥有一对公私钥对(PK , SK) 公钥PK公开，私钥SK必威体育官网网址； 已知公钥算法，公钥PK，得不到SK的值。 用于加解密 ?? 加密C=EPK[M] ??解密M=DSK[C] 用于数字签名 ??签名M || SigSK[M] ??验证M=VerPK[SigSK[M]] ? 公钥密码的理论基础是陷门单向函数； 定义2.1 设f 是一个函数，如果对任意给定的x，计算y 使得y = f (x)是容 易的，但对任意给定的y，计算x 使得f (x) = y是难解的，即求f的逆函数 是难解的，则称f 是一个单向函数（one-way function）。 例2.1：有限域上的指数函数 – f (x) = a x，x, a∈GF(q)； – 对任意x，计算a x 有快速有效的算法； – 对任意y，还没有发现计算loga y 的有效算法； – 目前，我们认为f (x) = a x是一个单向函数； 定义2.2 设f 是一个函数， t 是与f 有关的一个参数。对任意给定的x，计 算f (x)是容易的。如果当不知参数t 时，计算f 的逆函数是难解的，但当 知道参数t 时，计算f 的逆函数是容易的，则称f 是一个陷门单向函数 （trapdoor one-way function），参数t 称为陷门。 在公钥密码中，加密变换是一个陷门单向函数。知道陷门的人可以容易 地进行解密变换，而不知道陷门的人则无法有效地进行解密变换。 公钥加密解密过程 公钥的非对称性 非对称性是公钥最为重要的性质，可以用来保证“真实”性，“不可否认”性 3.RSA公钥密码 3.1 基本的数论知识* 3.2 RSA公钥密码体制* 3.3 RSA的安全性讨论 3.4 RSA的实现 3.5 RSA公钥加密体制的攻击* 3.6 RSA用于数字签名 3.1 基本的数论知识 ? 定义3.1 设a, b, m都是整数，如果m | (a-b)，则称a和b 模m 同余，记为： a ≡ b (mod m) ? 定理3.1（素分解定理）对任意正整数n，存在唯一的正素数p1 p2 … ps 及正整数 ，使得： ? 例3.1： – 15＝3×5 – 120＝23×3×5 ? 定义3.2 设n是一个正整数，φ(n) = |{x | 1≤ x ≤n-1, gcd(x,n)=1}|称为Euler函数。（Leonhard Euler (1707－1783)，欧拉，瑞士数学家） ? 如果p 是一素数，则φ(p) = p－1 。 ? 定理3.2 如果n1和n2互素，则φ(n