高中数学选修5-3(密码学算法基础)-选修课密码学9-省公开课一等奖全国示范课微课金奖

公钥密码体制

——背包公钥密码体制第1页背包体制结构公钥体制原理主要内容第2页一、背包体制下面以背包问题为例来介绍怎样结构公钥密码体制。

背包问题：给定一堆物品，重量各不相同，能否将这些物品放入一个背包中，使之等于一个给定重量？例：这些物品重量分别为：1,5,6,11,14,20。问能否组成重量分别为22和24背包？第3页

直观上：

c表示背包大小，每个数字ai表示能装到该背包中物品大小。问题是选择一些物品，使得它们恰好填满这个背包。其中xi为1表示物品在背包中，xi为0表示物品不在背包中。

1、背包问题数学描述给定n个正整数集合A={a1,a2,…,an}及正整数c，求0、1向量x=(x1,x2,…,xn)，使得：其中a=(a1,a2,…,an)称为背包向量。第4页标准上，只要搜索集合A={a1,a2,…,an}全部子集并检验其元素之和是否为c，则总能够决定此背包问题是否有解，若有解就一定能够找到。但注意到A子集个数为：背包问题是NP完全问题。单向函数：由集合A和0、1向量x很轻易求得c；但由集合A和c却极难求得0、1向量x1、背包问题数学描述第5页背包密码算法思想是将消息编码为背包问题解。明文分组长度等于堆中物品个数，且明文位与0、1向量x相对应，密文是计算得到和值。例：设背包向量为：A={1,5,6,11,14,20}明文：111001010110100101密文：1+5+6+205+11+141+11+20=32=30=32解密时，正当接收者也必须解背包问题；且不一样明文有可能加密成同一密文。这不符合公钥密码体制要求。1、背包问题数学描述第6页定义：若对都有则称向量A=(a1,a2,…,an)为超递增背包向量，对应背包问题称为超递增背包问题。2、利用超递增背包结构公钥密码体制超递增背包问题是易解。超递增背包中每一项都大于它之前全部项之和。第7页给定超递增背包向量A=(a1,a2,…,an),对任意n比特明文m=(x1,x2,…,xn),由a得到密文

任何用户收到c后,都可轻易地求得m：首先比较c和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该背包解为：1101012、利用超递增背包结构公钥密码体制第8页普通背包问题是困难问题，而超递增背包问题是易解。Merkle-Hellman公钥密码算法就利用这一性质。保密密钥是一个超递增背包向量A，公开密钥是A经过“置乱”后普通背包向量。Merkle-Hellman公钥密码算法：(1)选取一个超递增背包A=(a1,a2,…,an)和模M使M>a1+a2+…+an；(2)取w使(w,M)=1,并求满足ww-1modM=1w-1；(3)结构背包向量b=(b1,b2,…,,bn)且bi=waimodM;(4)公开密钥：b=(b1,b2,…,bn)

保密密钥：A=(a1,a2,…,an)、M和

w2、利用超递增背包结构公钥密码体制第9页

(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、利用超递增背包结构公钥密码体制第10页例：设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=52

52>41则m5=152-41=11<19则m4=011>9则m3=111-9=2<6则m2=02=2则m1=12、利用超递增背包结构公钥密码体制第11页(1)选取一个困难问题P；(2)选择困难问题P一个轻易子问题PEasy，它应该是多项式时间问题，最好是线性时间问题；(3)“置乱”问题PEasy使所得问题PS

是困难问题；(4)公开PS

，并描述怎样将它用作一个加密变换。将Ps逆回到PEasy信息作为秘密陷门；(5)结构密码系统细节，使得解密对密码分析者(不得不解PS)和正当接收者(可使用秘密陷门来解PEasy)有本质区分。二、结构公钥密码体制普通步骤第12页三、现在流行公钥密码体制(1)基于大整数因子分解问题，其中最经典代表是RSA公钥密码；(2)基于有限域上离散对数问题，如ElGamal公钥密码;另外，还有Rabin公钥算法、McEliece公钥算法和LUC公钥算法等等。(3)基于椭圆曲线群上离散对数问题，如椭圆曲线公钥密码。第13页（一）数学背景

介绍公钥密码学中用到基本数学知识：包含初等数论、有限域、计算复杂性。（二）RSA公钥密码

介绍RSA算法及其安全性，素性检测、因子分解算法和RSA实现。（三）ElGamal公钥密码

讲述ElGamal算法及其安全性分析和实现,离散对数问题求解。四、本课程概要第14页（五）椭圆曲线公钥密码

主要介绍椭圆曲线上基本运算、椭圆曲线公钥密码算法及其实现。（七）公钥密码学应用

介绍公钥基础设施(PKI)。（六）背包加密算法和其它公钥密码

介绍两种背包加密算法并给出其破译算法、Diffie-Hellman协议、Rabin公钥