最新传统经典故事教学讲义ppt课件.ppt 41页

传统经典故事 名人背景孔融(153年-208年9月26日)，字文举。东汉末年文学家，“建安七子”之一，家学渊源，是孔子的二十世孙，太山都尉孔宙之子。少有异才，勤奋好学，与平原陶丘洪、陈留边让并称俊秀。汉献帝在任六年，修城邑，立学校，举贤才，表儒术，经刘备表荐兼领青州刺史。建安元年(196年)，袁谭攻北海，孔融与其激战数月，最终败逃山东。不久，被朝廷征为将作大匠，迁少府，又任太中大夫。性好宾客，喜抨议时政，言辞激烈，后因触怒曹操而为其所杀。孔融能诗善文，曹丕称其文“扬(扬雄)、班(班固)俦也。” 读后感我们这些孩子在家里都是父母围绕着我们转，我们还老是不听话，一点都不为父母着想，其实父母也是为了我们好，看了这个故事我觉得我们要向孔融学习，做一个孝顺父母长辈的孩子。 5公开密钥算法概述背包算法RSA算法其他公开密钥算法公开密钥数字签名算法身份验证体制密钥交换算法 5.1概述成对密钥的思想：一个加密密钥和一个解密密钥，而从其中一个密钥推导出另外一个是不能的。混合密码系统：对称算法用于加密消息，公开密钥算法用于加密密钥。结论：公开密钥算法是不安全的，那些被认为是安全的算法中，又有许多是不实用的。 5.2背包算法背包问题:已知M1,M2,…,Mn和S,求b1,b2,…,bn,bi{0,1},使S=b1M1+b2M2+…+bnMn（1：表示物体放入背包，0：表示物体不放入背包）背包算法的思想:明文作为背包问题的解,对应于bi,密文为重量和。例：明文：011010背包：25781317密文：5+7+13=25算法的关键：两个不同的背包问题，一个在线性时间内求解，一个不能在线性时间内求解。超递增序列：其中每个元素都大于前面所有元素的和例：1，3，6，13，27，52……超递增背包：重量列表为一个超递增序列 超递增背包的解法：对于i=n,n-1,…,1bi=0当1当秘密密钥：超递增背包问题的重量序列公开密钥：有相同解的一个一般背包问题的重量序列从秘密密钥建立公开密钥：选择一个超递增序列作为秘密密钥，如：{2，3，6，13，27，52}；将其中每个值都乘以一个数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关于模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，求明文。例2：设背包公开密钥算法的公开密钥为向量{17，34，2，21，41}，某消息M被加密后生成密文C=22，已知系统中模m=50，n=17，试对C解密求出M。 例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根据秘密密钥{2，3，6，13，27，52}明文：110101 例2：设背包公开密钥算法的公开密钥为向量{17，34，2，21，41}，某消息M被加密后生成密文C=22，已知系统中模m=50，n=17，试对C解密求出M。解：根据公开密钥{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明文为：11010 实际实现：元素个数少的背包序列易解，实际的背包应该包括至少250个元素，超递增背包中每项应该有100到200位长，模200至400位长，不易解。 5.3RSA算法第一个成熟的公开密钥算法，可以用作加密和数字签名算法描述：RSA的安全性基于大整数的因数分解的困难性首先随机选择两个大素数p和q，计算n=pq然后随机选择加密密钥e，满足e与(p-1)(q-1)互素。用扩展的Euclid算法计算解密密钥d，使得ed1mod(p-1)(q-1)公开密钥：e和n秘密密钥：d加密：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=688 RSA算法用于数字签名：(见148页7.1.6)签名：S=MdmodnM:要签名的消息验证签名：M=Semodne:公开密钥d:秘密密钥 5.4其他公开密钥算法Rabin体制：安全性基于求模一个合数的平方根的困难性，等价于因数分解。ElGamal：安全性基于有限域内计算离散对数的困难性。数字签名加密 ElGamal产生密钥：一个素数p和两个随机数g，x，使g和x都小于p。计算y=gxmodp公开密钥：y,g和p，g和p由一群用户共享秘密密钥：x ElGamal签名产生签名：选择一个随机数k，使k与p-1互素。计算a=gkmodp用扩展的Euclid算法求b，使M=(xa+kb)mod(p-1)数字签名为a和b，k要保密。验证签名：确认是否有yaabmodp=gMmodp 例：选择p=11,g=2,秘密密钥x=8,M=5则y=gxmodp=28mod11=3公开密钥为：y=3,g=2,p=11产生签名：选择一个随机数k=9gcd(k,p-1)=gcd(9,10)=1互素计算：a=gkmodp=29mod11=6用扩展Euclid算法求b:M=(xa+kb)mod(p-1)5=(6*8+9b)mod105=8+9bmod107=9bmod10b=7*9-1mod10=7*9mod10=3签名为：a=6,b=3 验证签名：确认yaabmodp=gMmodp是否相等yaabmodp=3663mod11=10gMmodp=25mod11=10等式成立 ElGamal加密加密M：选择随机数k，使k与p-1互素计算a=gkmodp,b=ykMmodp,a和b为密文解密：计算M=b/axmodpb/axmodp=ykM/axmodp=gkxM/gkxmodp=M上例：y=3,g=2,p=11,x=8,M=5,k=9加密：a=gkmodp=29mod11=6b=ykMmodp=39*5mod11=9解密：M=b/axmodp=9/68mod11=9/4mod11=9*3mod11=5 5.5公开密钥数字签名算法数字签名算法（DSA）DSA变体GOST数字签名算法离散对数签名体制 数字签名算法（DSA）算法描述参数：p：一个L位长的二进制素数，L从512到1024，是64的整数倍；q：一个160位的p-1的素数因子；g=h(p-1)/qmodp，其中h是小于p-1的任意数，且h(p-1)/qmodp>1；x：一个小于q的数；y=gxmodp。p,q和g公开，可由一群用户共享秘密密钥：x，公开密钥：y 一个单向哈希函数H(M)，为安全哈希算法（SHA）签名：A产生一个比q小的随机数k；A计算r=(gkmodp)modq,s=(k-1(H(M)+xr))modq,r和s为签名。A向B发送r和s；B验证签名：w=s-1modq,u1=(H(M)*w)modq,u2=(r*w)modq,v=((gu1*yu2)modp)modq,如果v=r，则签名有效。用预先计算加快速度DSA的素数产生使用DSA的ElGamal加密用DSA进行RSA加密 5.6身份验证体制Feige-Fiat-ShamirGuillou-QuisquaterSchnorr Feige-Fiat-Shamir简化的Feige-Fiat-Shamir身份验证体制：仲裁人选择一个随机模n，为两个大素数的乘积产生密钥：仲裁人选择一个数v，令v为模n的一个二次剩余即x2v(modn)，且v-1也存在。v为甲的公开密钥。计算s=sqrt(v-1)modn的最小的s，为甲的秘密密钥。 协议：甲方随机选取一个r，使r