高中数学选修5-3(密码学算法基础)选修课密码学9课件

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