高中數(shù)學(xué)選修5-3(密碼學(xué)算法基礎(chǔ))選修課密碼學(xué)課件

1、公鑰密碼體制公鑰密碼體制背包公鑰密碼體制背包公鑰密碼體制高中數(shù)學(xué)選修高中數(shù)學(xué)選修5-3(5-3(密碼學(xué)算法基礎(chǔ)密碼學(xué)算法基礎(chǔ)) )選修課密碼學(xué)選修課密碼學(xué)2 背包體制背包體制 構(gòu)造公鑰體制的原理構(gòu)造公鑰體制的原理主要內(nèi)容主要內(nèi)容3一、背包體制一、背包體制 下面以背包問題為例來介紹如何構(gòu)造下面以背包問題為例來介紹如何構(gòu)造公鑰密碼體制。公鑰密碼體制。 背包問題背包問題：給定一堆物品，重量各不相：給定一堆物品，重量各不相同，能否將這些物品放入一個背包中，使同，能否將這些物品放入一個背包中，使之等于一個給定的重量？之等于一個給定的重量？例：這些物品的重量分別為：例：這些物品的重量分別為：1,5,6,1

2、1,14,20。問能否組成重量分別為問能否組成重量分別為22和和24的背包？的背包？4 直觀上：直觀上： c表示背包的大小，每個數(shù)字表示背包的大小，每個數(shù)字ai表表示能裝到該背包中的物品的大小。問題是選擇示能裝到該背包中的物品的大小。問題是選擇一些物品，使得它們正好填滿這個背包。其中一些物品，使得它們正好填滿這個背包。其中xi為為1表示物品在背包中，表示物品在背包中，xi為為0表示物品不在表示物品不在背包中。背包中。 1、背包問題的數(shù)學(xué)描述、背包問題的數(shù)學(xué)描述 給定給定 n個正整數(shù)的集合個正整數(shù)的集合A=a1, a2, ,an及及正整數(shù)正整數(shù)c，求，求0、1向量向量x=(x1, x2, ,xn

3、)，使得：，使得： 其中其中a=(a1, a2, ,an)稱為背包向量。稱為背包向量。1 122nnx ax ax ac5 原則上，只要搜索集合原則上，只要搜索集合A =a1, a2, ,an的所有子的所有子集并檢驗其元素之和是否為集并檢驗其元素之和是否為c，則總可以決定此背包，則總可以決定此背包問題是否有解，若有解就一定能夠找到。問題是否有解，若有解就一定能夠找到。 但注意到但注意到A的子集個數(shù)為：的子集個數(shù)為：012nnnnnccc背包問題是背包問題是NP完全問題。完全問題。單向函數(shù)：單向函數(shù)：由集合由集合A和和0、1向量向量x很容易求得很容易求得c；但由集合但由集合A和和c卻很難求得卻很

4、難求得0、1向量向量x1 1、背包問題的數(shù)學(xué)描述、背包問題的數(shù)學(xué)描述6 背包密碼算法的思想是將消息編碼為背包問題背包密碼算法的思想是將消息編碼為背包問題的解。明文分組長度等于堆中物品個數(shù)，且明文位的解。明文分組長度等于堆中物品個數(shù)，且明文位與與 0、1向量向量x相對應(yīng)，密文是計算得到的和值。相對應(yīng)，密文是計算得到的和值。例：設(shè)背包向量為：設(shè)背包向量為：A=1,5,6,11,14,20明文：111001 010110 100101密文：1+5+6+20 5+11+14 1+11+20 =32 =30 =32 解密時，合法接收者也必須解背包問題；且不解密時，合法接收者也必須解背包問題；且不同明文有

5、可能加密成同一密文。這不符合公鑰密碼同明文有可能加密成同一密文。這不符合公鑰密碼體制的要求。體制的要求。1 1、背包問題的數(shù)學(xué)描述、背包問題的數(shù)學(xué)描述7定義：若對定義：若對 均有均有 則稱向量則稱向量A=(a1, a2, ,an)為為超遞增背包向量超遞增背包向量，相應(yīng)的背包問題稱為超遞增背包問題。相應(yīng)的背包問題稱為超遞增背包問題。 nkk1,121kkaaaa2、利用超遞增背包構(gòu)造公鑰密碼體制、利用超遞增背包構(gòu)造公鑰密碼體制超遞增背包問題是易解的超遞增背包問題是易解的。超遞增背包中的每一項都大于它之前所有項之和。超遞增背包中的每一項都大于它之前所有項之和。8 給定超遞增背包向量給定超遞增背包向

6、量A=(a1,a2,an),對任意對任意n比特比特明文明文m=(x1, x2, ,xn),由由a得到密文得到密文 任何用戶收到任何用戶收到c后后,都可容易地求得都可容易地求得m：1 122nncxax ax a首先比較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)構(gòu)造背包向量構(gòu)造背包向量b=(b1,b2,bn)且且bi=waimod M ;(4)公開密鑰公開密鑰： b= (b

7、1, b2, ,bn) 保密密鑰保密密鑰： A=(a1, a2, ,an)、M 和和 w2、利用超遞增背包構(gòu)造公鑰密碼體制、利用超遞增背包構(gòu)造公鑰密碼體制10 (5)加密加密設(shè)明文設(shè)明文m= (m1, m2, ,mn)；(mi=0,1)(6)脫密脫密收到密文收到密文c后，計算后，計算s=w-1c modM= m1a1+ m2a2+mnan 收方收方由由s利用利用A的超遞增特性的超遞增特性可求出明文可求出明文m。 由于由于w是保密的，非法用戶不能由是保密的，非法用戶不能由c還原還原m。 密文密文c=m1b1+ m2b2+ +mnbn2、利用超遞增背包構(gòu)造公鑰密碼體制、利用超遞增背包構(gòu)造公鑰密碼體

8、制11例：設(shè)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=12、利用超遞增背包構(gòu)造公鑰密碼體制、利用超遞增背包構(gòu)造公鑰密碼體制12(1) 選取一個困難問題選取一個困難問題P；(2) 選擇困難問題選擇困難問題P一個容易子問題一個容易子問題PEasy，它應(yīng)該，它應(yīng)該

9、是多項式時間問題，最好是線性時間問題；是多項式時間問題，最好是線性時間問題； (3) “置亂置亂”問題問題PEasy使所得問題使所得問題PS 是困難問題；是困難問題； (4) 公開公開PS ，并描述如何將它用作一個加密變換。，并描述如何將它用作一個加密變換。將將Ps逆回到逆回到PEasy的信息作為秘密陷門；的信息作為秘密陷門；(5) 構(gòu)造密碼系統(tǒng)的細(xì)節(jié)，使得解密對密碼分析者構(gòu)造密碼系統(tǒng)的細(xì)節(jié)，使得解密對密碼分析者(不得不解不得不解PS )和合法接收者和合法接收者(可使用秘密陷門來解可使用秘密陷門來解PEasy )有本質(zhì)區(qū)別。有本質(zhì)區(qū)別。二、構(gòu)造公鑰密碼體制的一般二、構(gòu)造公鑰密碼體制的一般步驟步

10、驟13三、現(xiàn)在流行的公鑰密碼體制三、現(xiàn)在流行的公鑰密碼體制(1) 基于大整數(shù)因子分解問題，其中最典型的代基于大整數(shù)因子分解問題，其中最典型的代表是表是RSA公鑰密碼；公鑰密碼；(2) 基于有限域上離散對數(shù)問題，如基于有限域上離散對數(shù)問題，如ElGamal公公鑰密碼鑰密碼; 此外，還有此外，還有Rabin公鑰算法、公鑰算法、McEliece公鑰公鑰算法和算法和LUC公鑰算法等等。公鑰算法等等。(3) 基于橢圓曲線群上的離散對數(shù)問題，如橢圓基于橢圓曲線群上的離散對數(shù)問題，如橢圓曲線公鑰密碼。曲線公鑰密碼。14（一）（一） 數(shù)學(xué)背景數(shù)學(xué)背景 介紹公鑰密碼學(xué)中用到的基本數(shù)學(xué)知識：包括初等數(shù)論、有限域、

11、計算復(fù)雜性。（二）（二） RSA公鑰密碼公鑰密碼 介紹RSA算法及其安全性，素性檢測、因子分解算法和RSA的實現(xiàn)。（三）（三） ElGamal公鑰密碼公鑰密碼 講述ElGamal算法及其安全性分析和實現(xiàn),離散對數(shù)問題的求解。四、本課程概要四、本課程概要15（五）（五） 橢圓曲線公鑰密碼橢圓曲線公鑰密碼 主要介紹橢圓曲線上的基本運算、橢圓曲線公鑰密碼算法及其實現(xiàn)。（七）公鑰密碼學(xué)的應(yīng)用（七）公鑰密碼學(xué)的應(yīng)用 介紹公鑰基礎(chǔ)設(shè)施(PKI)。（六）（六） 背包加密算法和其他公鑰密碼背包加密算法和其他公鑰密碼 介紹兩種背包加密算法并給出其破譯算法、Diffie-Hellman協(xié)議、Rabin公鑰算法、McEliece公鑰算法和LU