计算机安全与保密第章

计算机安全与保密第章第1页内容背包公钥系统MCELICE公钥密码系统NTRU公钥密码系统概率公钥密码系统计算机安全与保密第章第2页背包公钥系统1978年Merkle和HellmanMH背包公钥密码系统（Merkle-HellmanKnapsackSystem）背包问题是NP完全问题超递增性序列子集和问题计算机安全与保密第章第3页r=zfork=nto1doifr≥s(k)thenr=r-s(k)x(k)=1elsex(k)=0ifthenx=(x(1),x(2),……,x(n))就是背包问题解else该背包问题无解“贪心”算法(GreedyAlgorithm)计算机安全与保密第章第4页(2,5,9,21,45,103,215,450,946|1643)第1步： 1643>846 x(8)=1 z(1)=1643-946=697第2步： 697>450 x(7)=1 z(2)=247第3步： 450>215 x(6)=1 z(3)=32第4步： 32<103 x(5)=0 z(4)=32第5步： 32<45 x(4)=0 z(5)=32第6步： 32>21 x(3)=1 z(6)=11第7步： 11>9 x(2)=1 z(7)=2第8步： 2<5 x(1)=0 z(8)=2第9步： 2=2 x(1)=1 z(9)=0最终解为：x=(1,0,1,1,0,0,1,1,1)计算机安全与保密第章第5页MH背包公钥密码系统计算机安全与保密第章第6页实例计算机安全与保密第章第7页1978Berlekamp、McEliece和VanTilborg普通线性纠错码译码问题是NP完全问题McEliece公钥体制基于普通线性纠错码纠错编码奇偶校验码(n+1n)E(m)=m=m1m2…nmn+1

(3n,n)重复码E(m)=m=m1m2…mnm=m1m2…mnm=m1m2…mn

MCELICE公钥密码系统计算机安全与保密第章第8页设一次传输犯错概率为Pe=0.001则(3n,n)码传输正确概率为(1-0.001)3+3*0.001*(1-0.001)2=0.997003+0.002994=0.999997传输正确概率从单次传输0.999提升到0.999997付出代价是码文比明文扩大了3倍计算机安全与保密第章第9页纠错编码分类检错码和纠错码线性码与非线性码分组码与非分组码(卷积码)二进制码与多进制码m=m1m2…mn

Hamming重量Hamming距离计算机安全与保密第章第10页一组码能够检出k个错误充要条件是码间最短距离最少为k+1假如两个码字组之间最短距离为2k+1则能够纠正不超出k误码10010 01001 10101 01110

1001001001101010111010010—1101100111111000100111011—1110000111101010011111100—1101101110111000011111011—模2加运算表任意两个码字最小距离是3，所以能纠正1个错误计算机安全与保密第章第11页w10010010011010101110r0001011001001011111011010000011110100110101100110110001010101000001011101110110010011010001010001111纠错译码表计算机安全与保密第章第12页引入生成矩阵来规范编码过程编码过程可经过矩阵运算实现计算机安全与保密第章第13页信息110信息码字000000000001001101010010011011011110100100110101101011110110101111111000计算机安全与保密第章第14页计算机安全与保密第章第15页此方程又称校验方程H称为校验矩阵计算机安全与保密第章第16页恰好是H矩阵中第2列，所以可判定第2位犯错于是将第2位由0改为1，得到W=110101信息位是110，110就是正确译码(7,4)汉明码(HammingCode)计算机安全与保密第章第17页设G是二元Goppa码生成矩阵(k×n阶)，校验矩阵是(n-k)×n阶矩阵H。随机选取一个GF(2l)上k×k阶非奇异矩阵S及n×n阶置换矩阵P，计算G′=SGP。将G′公开作为公钥，S、G和P是私钥。由G′代表码字与由G代表码字组合等价，G′代表是普通线性分组码。c=mG′+e1.计算y1=cP-1.2.由y1=m1+e1，m0G=m1，译码求得m0.3.计算m=m0S-1.加密算法解密算法McEliece公钥密码体制计算机安全与保密第章第18页利用Goppa码结构公钥算法方法能够推广到其它普通线性码，如汉明码和BCH码等等(7,4)汉明码计算机安全与保密第章第19页e=(0,0,0,0,1,0,0)加密解密计算机安全与保密第章第20页计算机安全与保密第章第21页NTRU公钥密码系统美国数学家Hoffstein博士CRTPTO’96IEEEP1363最短向量问题(Shortestvectorproblem，简称SVP)NTRU特点速度快系统需求低密钥生成快计算机安全与保密第章第22页(A,+,×)称作一个环(A,+)是一个加法群(A,×)是一个乘法半群乘法对于加法左、右分配率都成立，即a(b+c)=ab+ac(b+c)a=ba+ca计算机安全与保密第章第23页截尾多项式环乘法运算(卷积，CyclicConvolutionProduct)加法运算截尾多项式环也能够用多项式商环来定义计算机安全与保密第章第24页N=3计算机安全与保密第章第25页N=7,q=11计算机安全与保密第章第26页设(R,+,*)是N-1次截尾多项式环，首先选取参数是大模数q和小模数pp普通为奇素数，p和q要求互素。然后选取两个多项式f和g，要求f在环R上有模p和模q逆元，并定义：fq：是多项式f在环R上模q时逆元，即确定公钥是：fp：是多项式f在环R上模p时逆元，即私钥是f和g.fp*f=1(modp)fq*f=1(modq)NTRU公钥密码算法计算机安全与保密第章第27页c=mm,r,b,c系数取自区间(-p/2,p/2]a系数取自区间(-q/2,q/2]计算机安全与保密第章第28页N=11，p=3，q=32计算机安全与保密第章第29页概率公钥密码系统1986年M.Blum和S.GoldwasserBlum-Goldwasser概率公钥密码体制BBS随机序列生成器产生密钥流结合中国剩下定理传递BBS密钥种子计算机安全与保密第章第30页Blum-Blum-Shub(BBS)随机序列发生器设n=pq，p,q是两个k/2位素数，满足：p=q=3mod4记QR(n)表示n平方剩下，种子s0是QR(n)中一个元素。对于1≤i≤t，定义

产生随机序列为f(s0)=(z1,z2,…,zt)其中：zi=simod2计算机安全与保密第章第31页n=503×607=305321s0=1234562mod305321=64937s1=25638 z1=0s2=256252 z2=0s3=5355 z3=1s4=281172 z4=0s5=11091 z5=1s6=271239 z6=1s7=141640 z7=0s8=162653 z8=1s9=239080 z9=0s10=101990 z10=0s11=284272 z11=0s12=39630 z12=0s13=270997 z13=1s14=208558 z14=0s15=104383 z15=1s16=125483 z16=1s17=273998 z17=0s18=133956 z18=0s19=189445 z19=1

f(s0)=“0010110100001011001”计算机安全与保密第章第32页Blum-Goldwasser概率公钥系统n=pqp=q=3mod4明文x用(x1,x2,…,xm)表示利用种子r，经过BBS随机序列发生器产生随机序列z1,z2,…,zm加密算法zi=simod2yi=(xi+zi)mod2y=(y1,y2,…,ym,sm+1)就是密文计算机安全与保密第章第33页解密算法由r=s0经过BBS随机序列发生器产生序列z1,z2,…,zmxi=(yi+zi)mod2得到明文x=(x1,x2,…,xm)计算机安全与保密第章第34页n=719×839=603241s0=5456012mod603241=321413t=20z=“11101001011010001100”

x=“10011010110100100011”

y=“01110011101110101111”

s21=463488(p+1)/4=(719+1)/4=180(q+1)/4=(839+1)/4=210a1=((p+1)/4)21mod(p-1)=18021mod718=510

a2=((q+1)/4)21