計算機(jī)安全與保密13

第五章重點(diǎn)5.2背包算法背包問題:已知M1,M2,…,Mn和S,求b1,b2,…,bn,bi{0,1},使S=b1M1+b2M2+…+bnMn

（1：表示物體放入背包，0：表示物體不放入背包）背包算法的思想:明文作為背包問題的解,對應(yīng)于bi,密文為重量和。例：明文：011010背包：25781317密文：5+7+13=25算法的關(guān)鍵：兩個不同的背包問題，一個在線性時間內(nèi)求解，一個不能在線性時間內(nèi)求解。超遞增序列：其中每個元素都大于前面所有元素的和例：1，3，6，13，27，52……超遞增背包：重量列表為一個超遞增序列超遞增背包的解法：對于i=n,n-1,…,1

bi=0當(dāng)1當(dāng)秘密密鑰：超遞增背包問題的重量序列公開密鑰：有相同解的一個一般背包問題的重量序列從秘密密鑰建立公開密鑰：選擇一個超遞增序列作為秘密密鑰，如：{2，3，6，13，27，52}；將其中每個值都乘以一個數(shù)n，對m求余，例如：n=31,m=105；得到的序列作為公開密鑰：{62，93，81，88，102，37}。加密：將明文分成長度與背包序列相同的塊，計算背包總重量。例如：背包{62，93，81，88，102，37}，明文011000，密文為：93+81=174解密：先計算n-1，為n關(guān)于模m的乘法逆元。將密文的值與n-1模m相乘用秘密的背包求解，得到明文例：n=31,m=105,n-1=61,174*61mod105=9=3+6,明文為011000例1：n=31,m=105,秘密密鑰為{2，3，6，13，27，52}，公開密鑰：{62，93，81，88，102，37}，密文C=280，求明文。解：n-1=61C*

n-1mod105=280*61mod105=7070=2+3+13+52根據(jù)秘密密鑰{2，3，6，13，27，52}明文：110101例2：設(shè)背包公開密鑰算法的公開密鑰為向量{17，34，2，21，41}，某消息M被加密后生成密文C=22，已知系統(tǒng)中模m=50，n=17，試對C解密求出M。解：根據(jù)公開密鑰{17，34，2，21，41}，求秘密密鑰1*17mod50=172*17mod50=346*17mod50=213*17mod50=2123*17mod50=41秘密密鑰為{1，2，6，13，23}n-1=3,C*

n-1mod50=22*3mod50=16=1+2+13明文為：110105.3RSA算法第一個成熟的公開密鑰算法，可以用作加密和數(shù)字簽名算法描述：RSA的安全性基于大整數(shù)的因數(shù)分解的困難性首先隨機(jī)選擇兩個大素數(shù)p和q，計算n=pq然后隨機(jī)選擇加密密鑰e，滿足e與(p-1)(q-1)互素。用擴(kuò)展的Euclid算法計算解密密鑰d，使得ed

1mod(p-1)(q-1)公開密鑰：e和n秘密密鑰：d

所有出現(xiàn)ed的地方都可以用1表示加密：C=Memodn解密：M=Cdmodn例：已知n=3337,e=79，M=6882326879666683求C=？解：n=pq=3337=47*71p=47q=71(p-1)(q-1)=46*70=3220d=e-1mod3220=79-1mod3220=1019將明文3位一組，m1=688,m2=232,m3=687,m4=966,m5=668,m6=003加密：c1=m1emodn=68879mod3337=1570同理：c2=2756，c3=2091，c4=2276，c5=2423，c6=158C=15702756209122762423158解密：m1=c1dmodn=15701019mod3337=688Feige-Fiat-Shamir身份驗(yàn)證體制：產(chǎn)生模n，為兩個大素數(shù)的乘積。產(chǎn)生密鑰：選擇k個不同的數(shù)v1,v2,…,vk，其中各個vi為一個模n的二次剩余即x2v(modn)，且vi-1存在。這串v1,v2,…,vk為公開密鑰。計算滿足si=sqrt(vi-1)modn的最小的si，這一串s1,s2,…,sk為秘密密鑰。協(xié)議：甲選擇一個隨機(jī)數(shù)r，r<n。計算x=r2modn，將x發(fā)送給乙；乙向甲發(fā)送一個隨機(jī)的k位串：b1,b2,…,bk；甲計算y=r*(s1b1*s2b2*…*skbk)modn，將y發(fā)送給乙；乙驗(yàn)證是否有x=y2*(v1b1*v2b2*…*vkbk)modn。甲乙將這個協(xié)議重復(fù)t次，每次用一個不同的隨機(jī)值r直到乙相信甲知道s1,s2,…,sk為止。甲能欺騙乙的機(jī)會為1/2kt。建議至少取k=5和t=4。舉例：設(shè)模n=35，k=4。公開密鑰：{4，11，16，29}，秘密密鑰：{3，4，9，8}。練習(xí)1.已知RSA密碼體制的公開密鑰為n=51，e=11，試加密明文M1=3。通過分解n破譯該密碼，并對密文C2=6解密。答案：

C1=24,

M2=12

51＝3×17

(p-1)(q-1）＝2×16＝32

e=

11,

d

=

11-1

mod

32

=

3

C1=

311

mod

51

=

24

M2=

63

mod

51

=

122.設(shè)n=35,公開密鑰為{9,4,11,29},秘密密鑰為{2,3,4,8},補(bǔ)充用Feige-Fiat-Shamir協(xié)議進(jìn)行一圈身份驗(yàn)證的過程。(1)甲選擇一個隨機(jī)數(shù)r=11，計算

112mod35=16

，并發(fā)送給乙；(2)乙向甲發(fā)送一個隨機(jī)的二進(jìn)制串：{1，0，1，0}；(3)甲計算

11*21*30*41*80mod35=18

發(fā)送給乙；(4)乙驗(yàn)證是否有

182*91*40*111*290mod35=16

3.設(shè)n=11,g=2,x=3,y=2，寫出甲乙雙方用Diffie-Hellman算法約定密鑰的過程。4.設(shè)p=11，甲的加密密鑰e1=3，乙的加密密鑰e2=9，寫出甲乙雙方用shamir的三次通過協(xié)議傳輸明文M=4的過程。5.已知：超遞增序列為{2，3，6，13，27，52}m=105,n=31,密文C=333，求明文。6.設(shè)背包公開密鑰算法的公開密鑰為向量(27,54,35,97,21)，某消息M被加密后生成密文C=10，已知系統(tǒng)中模m=100,n=27,試對C解密求出M。解：根據(jù)公開密鑰{27，54，