公钥密码学和消验证.ppt

网络与信息安全 Information and Network Security （公钥密码学和消验证） 常规加密的简单模式 公钥密码学和消验证 公钥密码学的简单模型 基于公开密钥的鉴别过程 网络通信的攻击威胁 1. 暴露：把消息内容发布给任何人或没有合法密钥的进程； 2. 流量分析：发现团体之间信息流的结构模式。在一个面向连接的应用中，可以用来确定连接的频率和持续时间长度。 3. 伪造：用一个假冒信息源向网络中插入消息。 4. 内容修改：消息内容被插入、删除、变换、修改。 5. 顺序修改：插入、删除或重组消息序列。 6. 时间修改：消息延迟或重放。 7. 否认：接受者否认收到消息；发送者否认发送过消息。 公钥密码学的历史 76年Diffie和Hellman在“密码学的新方向”一文中提出了公钥密码的新概念，奠定了公钥密码学的基础 公钥技术是二十世纪最伟大的思想之一 改变了密钥分发的方式 可以广泛用于数字签名和身份认证服务 78年，RSA算法 基本思想和要求 涉及到各方：发送方、接收方、攻击者 涉及到数据：公钥、私钥、明文、密文 公钥算法的条件： 产生一对密钥是计算可行的 已知公钥和明文，产生密文是计算可行的 接收方利用私钥来解密密文是计算可行的 对于攻击者，利用公钥来推断私钥是计算不可行的 已知公钥和密文，恢复明文是计算不可行的 (可选)加密和解密的顺序可交换 传统加密：保密性 数论基础 Fermat定理: p素数,a是整数且不能被p整除,则: ap-1 ? 1 (mod p)(证明略) Euler函数?(n)定义为小于n且与n互素的正整数个数 p是素数, 则：?(p)=p-1 若n的因子分解为n=? Piai, ai0,Pi互不相同, 则 ?(n)= ? Piai?(1-1/Pi) 若gcd (m ,n)=1 (m、n的最大公因素是一，既互素), 则： ?(mn)=?(m)?(n) 特别地,若p?q且都是素数, 则 ?(pq)=(p-1)(q-1) 数论基础(续) Euler定理: 若a与n为互素的正整数,则 a?(n) ? 1 （mod n）既 a?(n)+1 ? a（mod n） 推论: 若n=pq, p?q都是素数, k是任意整数,对任意0? m ?n ,有 m?(n)+1 ? m （mod n） 从而 m k?(n)+1 ? mk(p-1)(q-1)+1 ? m（mod n）, （ m?(n) ? 1 （mod n） ；[m?(n) ] k ? 1 （mod n） m k?(n) ? 1 （mod n）；m k?(n)+1 ? mk(p-1)(q-1)+1?m（mod n）） RSA密钥生成原理 n=pq, p?q都是素数,?(n)=(p-1)(q-1)是n的Euler数 Euler定理推论: 若n=pq, p?q都是素数, k是任意整数,则 m k? (n)+1 ? mk(p-1)(q-1)+1 ? m （mod n）, 对任意0? m ?n 只要选择e,d, 满足ed=k?(n)+1,即 ed ? 1 （mod ?(n)） ? d ? e-1 （mod ?(n)） 则： med ? m k? (n)+1 ? m （mod n） 加密：Me ? C （mod n） 解密： Cd =Med =M （mod n） 公钥: KU={e,n}, 私钥: KR={d,n} RSA密钥生成与使用 产生密钥对 选择两个大素数100位以上的十进制数p,q , p?q，(保密) 计算n=pq, ?(n) =(p-1)(q-1) (只有知道p,q才可算出?(n) ，陷门为p,q ) 随机选择整数e, 使得gcd(e,?(n))=1 (两个随机数互素概率~0.6) 用殴几里得算法求出 d ? e-1 mod ?(n) ， 既 ed=k?(n)+1 （ed ? 1 mod ?(n) , 即ed与?(n) 互素) 参考书：《计算机密码应用基础》 四川大学数学学院 组编 P114 例5.9 公钥: KU={e,n}, 私钥: KR={d,n} 使用 分组大小为k, 2k n ? 2k+1 M和C分别为明文块和密文块 加密: C = Me mod n 解密: M = Cd mod n （M = Cd =Med =M mod n ） RSA密钥产生 产生两个素数 由于n = pq是公开的，所以，为了防止攻击者利用n获得p和q，必须选择足够大的素数p和q