高中數(shù)學(xué)選修5-3(密碼學(xué)算法基礎(chǔ))-選修課密碼學(xué)9-省公開課一等獎(jiǎng)全國示范課微課金獎(jiǎng)

公鑰密碼體制

——背包公鑰密碼體制第1頁背包體制結(jié)構(gòu)公鑰體制原理主要內(nèi)容第2頁一、背包體制下面以背包問題為例來介紹怎樣結(jié)構(gòu)公鑰密碼體制。

背包問題：給定一堆物品，重量各不相同，能否將這些物品放入一個(gè)背包中，使之等于一個(gè)給定重量？例：這些物品重量分別為：1,5,6,11,14,20。問能否組成重量分別為22和24背包？第3頁

直觀上：

c表示背包大小，每個(gè)數(shù)字ai表示能裝到該背包中物品大小。問題是選擇一些物品，使得它們恰好填滿這個(gè)背包。其中xi為1表示物品在背包中，xi為0表示物品不在背包中。

1、背包問題數(shù)學(xué)描述給定n個(gè)正整數(shù)集合A={a1,a2,…,an}及正整數(shù)c，求0、1向量x=(x1,x2,…,xn)，使得：其中a=(a1,a2,…,an)稱為背包向量。第4頁標(biāo)準(zhǔn)上，只要搜索集合A={a1,a2,…,an}全部子集并檢驗(yàn)其元素之和是否為c，則總能夠決定此背包問題是否有解，若有解就一定能夠找到。但注意到A子集個(gè)數(shù)為：背包問題是NP完全問題。單向函數(shù)：由集合A和0、1向量x很輕易求得c；但由集合A和c卻極難求得0、1向量x1、背包問題數(shù)學(xué)描述第5頁背包密碼算法思想是將消息編碼為背包問題解。明文分組長度等于堆中物品個(gè)數(shù)，且明文位與0、1向量x相對(duì)應(yīng)，密文是計(jì)算得到和值。例：設(shè)背包向量為：A={1,5,6,11,14,20}明文：111001010110100101密文：1+5+6+205+11+141+11+20=32=30=32解密時(shí)，正當(dāng)接收者也必須解背包問題；且不一樣明文有可能加密成同一密文。這不符合公鑰密碼體制要求。1、背包問題數(shù)學(xué)描述第6頁定義：若對(duì)都有則稱向量A=(a1,a2,…,an)為超遞增背包向量，對(duì)應(yīng)背包問題稱為超遞增背包問題。2、利用超遞增背包結(jié)構(gòu)公鑰密碼體制超遞增背包問題是易解。超遞增背包中每一項(xiàng)都大于它之前全部項(xiàng)之和。第7頁給定超遞增背包向量A=(a1,a2,…,an),對(duì)任意n比特明文m=(x1,x2,…,xn),由a得到密文

任何用戶收到c后,都可輕易地求得m：首先比較c和an，若，則an不在該背包中xn=0；若，則an必在該背包中xn=1，因?yàn)槿科渌至亢蚢1+a2+…+an-1<an,記c’=c-an。對(duì)c’和an-1重復(fù)上述過程，當(dāng)?shù)诌_(dá)a1時(shí)，整個(gè)過程結(jié)束。若變?yōu)?，則有唯一解m

；不然無解。例：背包A=(2,3,6,13,27,52)，c=70該背包解為：1101012、利用超遞增背包結(jié)構(gòu)公鑰密碼體制第8頁普通背包問題是困難問題，而超遞增背包問題是易解。Merkle-Hellman公鑰密碼算法就利用這一性質(zhì)。保密密鑰是一個(gè)超遞增背包向量A，公開密鑰是A經(jīng)過“置亂”后普通背包向量。Merkle-Hellman公鑰密碼算法：(1)選取一個(gè)超遞增背包A=(a1,a2,…,an)和模M使M>a1+a2+…+an；(2)取w使(w,M)=1,并求滿足ww-1modM=1w-1；(3)結(jié)構(gòu)背包向量b=(b1,b2,…,,bn)且bi=waimodM;(4)公開密鑰：b=(b1,b2,…,bn)

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

w2、利用超遞增背包結(jié)構(gòu)公鑰密碼體制第9頁

(5)加密設(shè)明文m=(m1,m2,…,mn)；(mi=0,1)(6)脫密收到密文c后，計(jì)算s=w-1cmodM=m1a1+m2a2+……+mnan

收方由s利用A超遞增特征可求出明文m。因?yàn)閣是保密，非法用戶不能由c還原m。密文c=m1b1+m2b2+…+mnbn2、利用超遞增背包結(jié)構(gòu)公鑰密碼體制第10頁例：設(shè)M=89，A=(2，6，9，19，41)，取w=13求w-1，b，對(duì)明文m=(10101)加密并脫密。解：由Euclid算法可求出w-1=48mod89。則b=（26，78，28，69，88）加密：c=26+28+88=142脫密：計(jì)算s=cw-1mod89=52

52>41則m5=152-41=11<19則m4=011>9則m3=111-9=2<6則m2=02=2則m1=12、利用超遞增背包結(jié)構(gòu)公鑰密碼體制第11頁(1)選取一個(gè)困難問題P；(2)選擇困難問題P一個(gè)輕易子問題PEasy，它應(yīng)該是多項(xiàng)式時(shí)間問題，最好是線性時(shí)間問題；(3)“置亂”問題PEasy使所得問題PS

是困難問題；(4)公開PS

，并描述怎樣將它用作一個(gè)加密變換。將Ps逆回到PEasy信息作為秘密陷門；(5)結(jié)構(gòu)密碼系統(tǒng)細(xì)節(jié)，使得解密對(duì)密碼分析者(不得不解PS)和正當(dāng)接收者(可使用秘密陷門來解PEasy)有本質(zhì)區(qū)分。二、結(jié)構(gòu)公鑰密碼體制普通步驟第12頁三、現(xiàn)在流行公鑰密碼體制(1)基于大整數(shù)因子分解問題，其中最經(jīng)典代表是RSA公鑰密碼；(2)基于有限域上離散對(duì)數(shù)問題，如ElGamal公鑰密碼;另外，還有Rabin公鑰算法、McEliece公鑰算法和LUC公鑰算法等等。(3)基于橢圓曲線群上離散對(duì)數(shù)問題，如橢圓曲線公鑰密碼。第13頁（一）數(shù)學(xué)背景

介紹公鑰密碼學(xué)中用到基本數(shù)學(xué)知識(shí)：包含初等數(shù)論、有限域、計(jì)算復(fù)雜性。（二）RSA公鑰密碼

介紹RSA算法及其安全性，素性檢測(cè)、因子分解算法和RSA實(shí)現(xiàn)。（三）ElGamal公鑰密碼

講述ElGamal算法及其安全性分析和實(shí)現(xiàn),離散對(duì)數(shù)問題求解。四、本課程概要第14頁（五）橢圓曲線公鑰密碼

主要介紹橢圓曲線上基本運(yùn)算、橢圓曲線公鑰密碼算法及其實(shí)現(xiàn)。（七）公鑰密碼學(xué)應(yīng)用

介紹公鑰基礎(chǔ)設(shè)施(PKI)。（六）背包加密算法和其它公鑰密碼

介紹兩種背包加密算法并給出其破譯算法、Diffie-Hellman協(xié)議、Rabin公鑰