XXX•公钥密码体制 公钥密码体制 1、现有密码体制的主要问题： 基本原理 加密变换E 解密变换D 明文m 密钥源 密码分析员 明文 保密通信模型 安全通道 普通通道 源 （1）陌生人之间保密通信的问题 （2）密钥管理的困难 传统的密钥管理为每个用户使用一对密钥时，n个用户需要C(n,2)=n(n-1)/2把密钥，当用户数增多时，密钥空间急剧增加，如： n=100 C(100,2)=4,995 n=5000, C(5000,2)=12,497,500 （3）数字签名的问题 对称加密算法难以达到不可否认的安全要求，对称密码体制不能满足信息安全需要的发展。 公钥加密模型：加密变换E解密变换D明文m密钥源密码分析员明文m公钥Ke普通通道秘密密钥Kd公钥加密模型源公钥密码体制又称双密钥密码体制和非对称密码体制，是由和于1976年在其《密码学新方向》中提出的，参见划时代的文献：W..E.,raphy,,V.IT-22.No.6,,PP.644-654 两种密码体制的比较 对称密码体制不能提供抗否认服务。
公钥密码体制 椭圆曲线密码体制（ECC） 7/59 公钥密码体制之一 8/59 背包问题由和于1978年提出，其主要思想是假设某人拥有大量不同重量的物品，通过秘密选择其中的一些物品放入背包中来加密消息。背包中物品的重量是公开的，所有可能的物品也是公开的，但是背包中的物品是秘密的。在一定的限制条件下，背包问题是一个众所周知的不可计算问题。给定重量，列出可能的物品在计算上是不可能的。 什么是背包问题？ 【例子】书包里有一支钢笔30克，一把尺子25克，一块橡皮37克，一本数学书504克，一本词汇书799克，一个钱包711克。 现在，给定任意重量，你能从书包里拿出一些东西，使得重量之和等于我给出的重量吗？数学书 504g 尺子 25g 钢笔 30g 词汇书 799g 橡皮擦 37g 钱包 711g9/59866 克？因为这个例子只有 6 件物品，所以很容易看出答案：866g = 799g（词汇书）+ 30g（钢笔）+ 37g（橡皮擦）0*25g + 1*30g + 1*37g + 0*504g + 0*711g + 1*799g = 克？我们可以看到，没有办法拿出一些物品，使得总重量等于 700 克。当物品数量相当多时，计算就没那么简单了。 10/59 数学表示 给定n个物品，它们的重量分别为a1，a2，...，an，现在将其中一些放入重量为b的背包中。
这个问题导向寻找满足下列方程的xi，xi=0或1，i=1,2,…,n。11/59背包问题有有效的解吗？一般来说，解决背包问题在计算上是困难的，目前还没有有效的算法来解决这类问题。理论上只能使用穷举搜索。需要多少次穷举搜索？以n=100为例：2100=1., 用每秒搜索107个解的超高速计算机进行穷举搜索，一年只能完成3次。要完成所有的穷举搜索，需要：4., 背包问题很容易解。例如，超递增背包问题的解很容易找到。如果a是正整数，则称为超递增序列。 例如1，3，6，13，27，52是一个超增序列，而1，3，4，9，15，25不是一个超增序列。 超增序列的解很容易找，将总质量和序列中最大的书进行比较，如果总质量小于这个数，则不在背包中；如果总质量大于这个数，则在背包中。用背包的质量减去这个数，转动检查序列中的下一个最大数。重复此过程，直到结束。 超增背包问题 【例】 检查一个总质量为70kg的背包，质量序列为2，3，6，13，27，52，可见，（2，3，6，13，27，52）是一个超增序列。 按照超递增序列解：=，所以52kg在背包里。 (ii)70kg-52kg=18kg，an-1=所以27kg不在背包里。
（三）重复上述步骤，得到解决方案：选取一组正整数a=77。明文为=加密后的密文为=20+28+31+38+55+77=249。利用密文和已知密钥a，解背包问题即可得到明文。背包加密的实现。公钥的选择。背包公钥体制选取的背包序列a是通过对超增序列进行变换得到的。设bi-1,i=2,3,…,n。 选取模数m2b-1满足ww-11(mod.需要注意几个条件：（1）模数m需要大于数列中所有数之和（2）乘数w应该和数列中任何一个数都没有共同因子。变换：解密过程中背包的安全性以及提议：谁能破译这个新的背包公钥体制，将获得50美元的奖励。两年后，这个模式被发现，并遭到了破译攻击。攻击主要抓住MH背包公钥密码中公钥序列和生成它的超增序列之间的关系作为突破口，攻击陷阱是在某个体制或文件中设置的“机制”。如果考虑a=131，则u/m进一步减小为（0.05353，0.05354），（0.52676，0.52677）。如果考虑a=318， u/m进一步降为(0.05353, 0.05354)。如何确定整数u和m使得u/m落入区间?对于这个例子，至少有两种方法:(1)u=53，m=990，通过变换b()，i=1,2，…，8，得到超递增序列1，5，13，24，49，123，225，505。
例如53*467=24751=1()，53*355=18815=5()，等等。（2）u=28，m=523，可得1，3，7，13，26，65，119，269。两位创始人将经过多次变换后的序列作为公钥公布，并再次悬赏100美元。两年后，-和几乎同时提出攻击方法，给MH型背包公钥密码体制以致命打击。总结：Mekle-加密方案具有重要的历史意义，因为它是第一个具体实现的公钥加密方案。随后人们提出了很多变体，大多数(包括原方案)都被证明是不安全的，只有一个例外，那就是Chor-方案。 Rabin公钥密码体制抵御多重MH变换攻击2 Rabin密码体制简介1978年RSA公钥密码体制被Rabin提出之后，Rabin对RSA提出了巧妙的修改，该修改借鉴了RSA中加密指数e平方根算法的理论基础，更进一步，它利用了大数n因式分解的难度。已经证明，破译Rabin密码等同于分解大数因式。1976年图灵奖获得者n公钥密码Rabin公钥密码是可证明安全的，如果将n因子分解为n=pq，则可以破译RSA。
也就是说RSA抵抗攻击的能力不超过大数的因式分解，但尚未证明其等价于大整数的因式分解。Rabin密码体制是RSA的一种修改，它有以下两个特点：（1）它不是基于一一对应的单向陷门函数，对于同一密文，可能有两个以上的对应明文。（2）破译此体制等价于大整数的因式分解。性质：因式分解问题与平方根问题在计算上等价，Rabin公钥加密算法就是基于此性质实现的。Rabin加密算法的实现过程（）公钥的选取是通过素数测试法随机选取两个mod pq作为公钥，（p，q）作为私钥。 （）加密算法 假如实体B将信息加密给A，A解密，则加密步骤如下： （2）将信息表示为{0，1，…，n-1}中的整数m （3）计算c= 。 由于A知道p和q，因此可以进行如下计算： 利用扩展算法找出满足ap+bq=1的整数a和b。 计算（p+1）/4mod（q+1）/4mod 计算y=（a*p*sb*q*r）mod分别为x和-xmod （）解密算法： 由于接收方知道p和q，因此可以利用中国剩余定理解两个同余式。 计算：（p+1）/4mod（p+1）/4）mod（q+1）/4mod（q+1）/4）mod -1mod p）和整数b -1mod