《高中数学选修53(密码学算法基础)选修课密码学9课件》由会员分享，可在线阅读，更多相关《高中数学选修53(密码学算法基础)选修课密码学9课件（16页珍藏版）》请在金锄头文库上搜索。
1、公钥密码体制公钥密码体制背包公钥密码体制背包公钥密码体制2 背包体制背包体制 构造公钥体制的原理构造公钥体制的原理主要内容主要内容3一、背包体制一、背包体制 下面以背包问题为例来介绍如何构造下面以背包问题为例来介绍如何构造公钥密码体制。公钥密码体制。 背包问题背包问题：给定一堆物品，重量各不相：给定一堆物品，重量各不相同，能否将这些物品放入一个背包中，使同，能否将这些物品放入一个背包中，使之等于一个给定的重量？之等于一个给定的重量？例：这些物品的重量分别为：例：这些物品的重量分别为：1,5,6,11,14,20。问能否组成重量分别为问能否组成重量分别为22和和24的背包？的背包？4 直观上：直
2、观上： c表示背包的大小，每个数字表示背包的大小，每个数字ai表表示能装到该背包中的物品的大小。问题是选择示能装到该背包中的物品的大小。问题是选择一些物品，使得它们正好填满这个背包。其中一些物品，使得它们正好填满这个背包。其中xi为为1表示物品在背包中，表示物品在背包中，xi为为0表示物品不在表示物品不在背包中。背包中。 1、背包问题的数学描述、背包问题的数学描述 给定给定 n个正整数的集合个正整数的集合A=a1, a2, ,an及及正整数正整数c，求，求0、1向量向量x=(x1, x2, ,xn)，使得：，使得： 其中其中a=(a1, a2, ,an)称为背包向量。称为背包向量。5 原则上，
3、只要搜索集合原则上，只要搜索集合A =a1, a2, ,an的所有子的所有子集并检验其元素之和是否为集并检验其元素之和是否为c，则总可以决定此背包，则总可以决定此背包问题是否有解，若有解就一定能够找到。问题是否有解，若有解就一定能够找到。 但注意到但注意到A的子集个数为：的子集个数为：背包问题是背包问题是NP完全问题。完全问题。单向函数：单向函数：由集合由集合A和和0、1向量向量x很容易求得很容易求得c；但由集合但由集合A和和c却很难求得却很难求得0、1向量向量x1 1、背包问题的数学描述、背包问题的数学描述6 背包密码算法的思想是将消息编码为背包问题背包密码算法的思想是将消息编码为背包问题的
4、解。明文分组长度等于堆中物品个数，且明文位的解。明文分组长度等于堆中物品个数，且明文位与与 0、1向量向量x相对应，密文是计算得到的和值。相对应，密文是计算得到的和值。例：设背包向量为：设背包向量为：A=1,5,6,11,14,20明文：111001 010110 100101密文：1+5+6+20 5+11+14 1+11+20 =32 =30 =32 解密时，合法接收者也必须解背包问题；且不解密时，合法接收者也必须解背包问题；且不同明文有可能加密成同一密文。这不符合公钥密码同明文有可能加密成同一密文。这不符合公钥密码体制的要求。体制的要求。1 1、背包问题的数学描述、背包问题的数学描述7定
5、义：若对定义：若对 均有均有 则则称称向向量量A=(a1, a2, ,an)为为超超递递增增背背包包向向量量，相应的背包问题称为超递增背包问题。相应的背包问题称为超递增背包问题。 2、利用超递增背包构造公钥密码体制、利用超递增背包构造公钥密码体制超递增背包问题是易解的超递增背包问题是易解的。超递增背包中的每一项都大于它之前所有项之和。超递增背包中的每一项都大于它之前所有项之和。8 给给定定超超递递增增背背包包向向量量A=(a1,a2,an),对对任任意意n比比特特明文明文m=(x1, x2, ,xn),由由a得到密文得到密文 任何用户收到任何用户收到c后后,都可容易地求得都可容易地求得m：首先
6、比较c和和an，若，若 ，则，则an不在该背包中不在该背包中xn=0；若；若 ，则an必在该背包中在该背包中xn=1，因为所有其，因为所有其它分量的和它分量的和a1+a2+an-1a1+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 和和 w2、利用超递增背包构造公钥密码体制、利用超递增背包构造公钥密码体制10 (5)加密加密设明文设明文m= (m1, m2, ,
7、mn)；(mi=0,1)(6)脱密脱密收到密文收到密文c后，计算后，计算s=w-1c modM= 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 =48 mod89。则b=（26，78，28，69，88）
8、加密：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=12、利用超递增背包构造公钥密码体制、利用超递增背包构造公钥密码体制12(1) 选取一个困难问题选取一个困难问题P；(2) 选择困难问题选择困难问题P一个容易子问题一个容易子问题PEasy，它应该，它应该是多项式时间问题，最好是线性时间问题；是多项式时间问题，最好是线性时间问题； (3) “置乱置乱”问题问题PEasy使所得问题使所得问题PS 是困难问题；是困难问题； (4) 公开公开PS ，并描述如何将它用作一
9、个加密变换。，并描述如何将它用作一个加密变换。将将Ps逆回到逆回到PEasy的信息作为秘密陷门；的信息作为秘密陷门；(5) 构造密码系统的细节，使得解密对密码分析者构造密码系统的细节，使得解密对密码分析者(不得不解不得不解PS )和合法接收者和合法接收者(可使用秘密陷门来解可使用秘密陷门来解PEasy )有本质区别。有本质区别。二、构造公钥密码体制的一般二、构造公钥密码体制的一般步骤步骤13三、现在流行的公钥密码体制三、现在流行的公钥密码体制(1) 基于大整数因子分解问题，其中最典型的代基于大整数因子分解问题，其中最典型的代表是表是RSA公钥密码；公钥密码；(2) 基于有限域上离散对数问题，如
10、基于有限域上离散对数问题，如ElGamal公公钥密码钥密码; 此外，还有此外，还有Rabin公钥算法、公钥算法、McEliece公钥公钥算法和算法和LUC公钥算法等等。公钥算法等等。(3) 基于椭圆曲线群上的离散对数问题，如椭圆基于椭圆曲线群上的离散对数问题，如椭圆曲线公钥密码。曲线公钥密码。14（一）（一） 数学背景数学背景 介绍公钥密码学中用到的基本数学知识：包括初等数论、有限域、计算复杂性。（二）（二） RSA公钥密码公钥密码 介绍RSA算法及其安全性，素性检测、因子分解算法和RSA的实现。（三）（三） ElGamal公钥密码公钥密码 讲述ElGamal算法及其安全性分析和实现,离散对数
11、问题的求解。四、本课程概要四、本课程概要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的乘法逆元。的乘法逆元。
