公钥加密-西安交通大学计算机教学试验中心.ppt

HPMS HPMS 活动18 Kid Krypto  ——公钥加密 西安交通大学 高效能建模与仿真研究小组 2011年10 本PPT的材料改编自csunplugged.org项目 Sharing Secrets and fighting Crime-Cryptography 主要内容 基本思想 具体活动 问题扩展 现状与研究进展 进一步应用 结论 进一步问题思考 参考文献 基本思想 一个消息发送者通过公钥对信息进行加密，而信息接收者通过自己的私钥对其解密。 每个人拥有一把自己的锁，在锁上写上我们自己的名字，然后再把锁打开并放到一个公用的桌子上让别人使用。只有锁的主人才有锁的钥匙 Bill的公钥 Bill的私钥 Amy Bill 具体活动 假定Amy要给Bill发送消息 Amy利用Bill的公钥使Amy的消息成为密文， Bill利用自己的私钥对密文解密，得到明文。 密钥的实例 Bill的公有图---公钥 Bill的私有图---私钥 消息发送者加密 Amy利用Bill的公有图加密明文，假定明文是66 1）放置随机数，总数是66 2）相邻点求和（图中括号内） 3）去掉最初的随机数 （进行信息隐藏） 这个图相当于密文 消息接受者解密 1）根据私钥的放大点位置，找到密图对应点 2）将所有对应点的值求和，得到明文66 13+13+22+18=66 Bill收到Amy发给自己的图（密文），如左图 Bill的私有图---私钥 问题扩展 放大点的作用 Bill私有图中的放大点将公有图进行划分 划分：放大点与放大点相连的所有点 这几个区域已经完全覆盖了整副图中的每一个点，并且只覆盖一次 这种划分不唯一 问题扩展 如何破解该加密 使用方程组来解，如果使用高斯消去法，时间复杂度为n的3次方（n为总的节点个数）。 问题扩展-公钥密码体制的安全性 是指计算上的安全性 安全性的理论基础：复杂性理论 问题是需要回答的一般性提问，通常含有若干个未定参数或自由变量。问题的描述包括 （1）给定所有的未定参数的一般性描述 （2）陈述“答案”或“解”必须满足的性质 算法是求解某个问题的一系列具体步骤，通常可理解为求解某个问题的通用计算机程序。 一个算法的复杂性由该算法所需求的最大时间（T）和存储空间（S）度量。 由于算法用于同一问题的不同规模实例所需求的时间和空间往往不同，所以总是将他们表示成问题实例的规模n的函数，n表示描述该实例所需的输入数据长度。 现状与研究进展 RSA( Rivest, Shamir Adleman ，1977 ） 基于数论中大素数分解的困难性 ElGamal (1984) 一种基于离散对数问题的困难性 ECC(Neal Koblitz, Victor Miller,1985) 基于椭圆曲线点群上的离散对数问题的难解性。 Paillier(Pascal Paillier,1999) 基于计算和判断 上的n次剩余问题的困难性假设 RSA算法描述 加密： C=Me mod N, where 0≤MN 解密： M=Cd mod N 公钥为（e，N）， 私钥为（d，N） 必须满足以下条件： Med = M mod N 计算Me和Cd是比较容易的 由e和n确定d是不可行的 RSA 密钥产生过程 随机选择两个大素数 p, q 计算 N=p.q 注意 ?(N)=(p-1)(q-1) 选择 e使得1e?(N),且gcd(e,?(N))=1 解下列方程求出 d e.d=1 mod ?(N) 且 0≤d≤N 公布公钥: KU={e,N} 保存私钥: KR={d,p,q} 为什么RSA 可以加解密 因为 Euler 定理的一个推论: Mk*?(n)＋1 = M mod N RSA 中: N=p*q ?(N)=(p-1)(q-1) 选择 e d 使得e*d＝1 mod ?(N) 因此 存在k使得e*d=1+k*?(N) 因此Cd = (Me)d = M1+k*?(N) = M mod N 简单的例子 1. 选择素数: p=17 q=11 2. 计算n = pq =17×11=187 3. 计算?(n)=(p–1)(q-1)=16×10=160 4. 选择e : gcd(e,160)=1; 选择e=7 5. 确定d: de=1 mod 160 and d 160， d=23 因为23×7=161= 1×160+1 6. 公钥KU={7,187} 7. 私钥KR={23,17,11} 简单的例子2 RSA的加解密为: 给定消息M = 88 ( 88187) 加密:C = 887 mod 187 = 11 解密:M = 1123 mod 187 = 88 RAS商用程序中的大整数