《高中数学选修5-3（密码学算法基础） 选修课密码学》由会员分享，可在线阅读，更多相关《高中数学选修5-3（密码学算法基础） 选修课密码学（16页珍藏版）》请在金锄头文库上搜索。
1、公钥密码体制 背包公钥密码体制,背包体制 构造公钥体制的原理,主要内容,一、背包体制,下面以背包问题为例来介绍如何构造公钥密码体制。,背包问题：给定一堆物品，重量各不相同，能否将这些物品放入一个背包中，使之等于一个给定的重量？,例：这些物品的重量分别为：1,5,6,11,14,20。问能否组成重量分别为22和24的背包？,直观上： c表示背包的大小，每个数字ai表示能装到该背包中的物品的大小。问题是选择一些物品，使得它们正好填满这个背包。其中xi为1表示物品在背包中，xi为0表示物品不在背包中。,1、背包问题的数学描述 给定 n个正整数的集合A=a1, a2, ,an及正整数c，求0、1向量x
2、=(x1, x2, ,xn)，使得： 其中a=(a1, a2, ,an)称为背包向量。,原则上，只要搜索集合A =a1, a2, ,an的所有子集并检验其元素之和是否为c，则总可以决定此背包问题是否有解，若有解就一定能够找到。,但注意到A的子集个数为：,背包问题是NP完全问题。,单向函数： 由集合A和0、1向量x很容易求得c； 但由集合A和c却很难求得0、1向量x,1、背包问题的数学描述,背包密码算法的思想是将消息编码为背包问题的解。明文分组长度等于堆中物品个数，且明文位与 0、1向量x相对应，密文是计算得到的和值。,例：设背包向量为：A=1,5,6,11,14,20,明文：111001 01
3、0110 100101,密文：1+5+6+20 5+11+14 1+11+20 =32 =30 =32,解密时，合法接收者也必须解背包问题；且不同明文有可能加密成同一密文。这不符合公钥密码体制的要求。,1、背包问题的数学描述,定义：若对 均有 则称向量A=(a1, a2, ,an)为超递增背包向量，相应的背包问题称为超递增背包问题。,2、利用超递增背包构造公钥密码体制,超递增背包问题是易解的。,超递增背包中的每一项都大于它之前所有项之和。,给定超递增背包向量A=(a1,a2,an),对任意n比特明文m=(x1, x2, ,xn),由a得到密文 任何用户收到c后,都可容易地求得m：,首先比较c和
4、an，若 ，则an不在该背包中xn=0；若 ，则an必在该背包中xn=1，因为所有其它分量的和a1+a2+an-1 an ,记c=c-an 。对c和an-1重复上述过程，当到达a1时，整个过程结束。若变为0，则有唯一解m ；否则无解。,例：背包A=(2,3,6,13,27,52) ，c=70,该背包的解为：110101,2、利用超递增背包构造公钥密码体制,一般的背包问题是困难问题，而超递增背包问题是易解的。Merkle-Hellman公钥密码算法就利用这一性质。保密密钥是一个超递增背包向量A，公开密钥是A经过“置乱” 后的一般背包向量。,Merkle-Hellman公钥密码算法：,(1)选取一
5、个超递增背包A=(a1, a2, ,an)和模M 使Ma1+a2+an ；,(2)取w使(w,M)=1, 并求满足ww-1modM=1的w-1；,(3)构造背包向量b=(b1,b2,bn)且bi=waimod M ;,(4)公开密钥： b= (b1, b2, ,bn) 保密密钥： A=(a1, a2, ,an)、M 和 w,2、利用超递增背包构造公钥密码体制,(5)加密 设明文m= (m1, m2, ,mn)；(mi=0,1),(6)脱密,收到密文c后，计算,s=w-1c modM= m1a1+ m2a2+mnan,收方由s利用A的超递增特性可求出明文m。,由于w是保密的，非法用户不能由c还原
6、m。,密文c=m1b1+ m2b2+ +mnbn,2、利用超递增背包构造公钥密码体制,例：设M=89，A=(2，6，9，19，41)，取w=13求w-1，b，对明文 m=(10101)加密并脱密。,解：由Euclid算法可求出w-1 =48 mod89。,则b=（26，78，28，69，88）,加密：c=26+28+88 =142,脱密：计算s=cw-1mod89=52,5241 则 m5=1 52-41=119 则 m3=1 11-9=26 则 m2=0 2=2 则 m1=1,2、利用超递增背包构造公钥密码体制,(1) 选取一个困难问题P；,(2) 选择困难问题P一个容易子问题PEasy，它
7、应该是多项式时间问题，最好是线性时间问题；,(3) “置乱”问题PEasy使所得问题PS 是困难问题；,(4) 公开PS ，并描述如何将它用作一个加密变换。将Ps逆回到PEasy的信息作为秘密陷门；,(5) 构造密码系统的细节，使得解密对密码分析者(不得不解PS )和合法接收者(可使用秘密陷门来解PEasy )有本质区别。,二、构造公钥密码体制的一般步骤,三、现在流行的公钥密码体制,(1) 基于大整数因子分解问题，其中最典型的代表是RSA公钥密码；,(2) 基于有限域上离散对数问题，如ElGamal公钥密码;,此外，还有Rabin公钥算法、McEliece公钥算法和LUC公钥算法等等。,(3)
8、 基于椭圆曲线群上的离散对数问题，如椭圆曲线公钥密码。,（一） 数学背景 介绍公钥密码学中用到的基本数学知识：包括初等数论、有限域、计算复杂性。 （二） RSA公钥密码 介绍RSA算法及其安全性，素性检测、因子分解算法和RSA的实现。 （三） ElGamal公钥密码 讲述ElGamal算法及其安全性分析和实现,离散对数问题的求解。,四、本课程概要,（五） 椭圆曲线公钥密码 主要介绍椭圆曲线上的基本运算、椭圆曲线公钥密码算法及其实现。,（七）公钥密码学的应用 介绍公钥基础设施(PKI)。,（六） 背包加密算法和其他公钥密码 介绍两种背包加密算法并给出其破译算法、Diffie-Hellman协议、Rabin公钥算法、McEliece公钥算法和LUC公钥算法。,作业,2、在M-H背包型公钥体制中，设M=233，A=(3，5，11，23，49，103)，取w=29求w-1，b，对明文 m=(101110)加密并脱密。,1、求出使19s+28t=1成立的整数s、t。并由此得到19mod28的乘法逆元。,
