密码学(复习)

1、加密加密解密解密明文明文密文密文原始明文原始明文加密加密密钥密钥解密解密密钥密钥kI 安安 全全 信信 道道 kI KG KG ki ki mi ci ci mi Eki(mi) Eki(mi) 线性反馈移位寄存器线性反馈移位寄存器 f(x)为线性函数，输出序列满足下式为线性函数，输出序列满足下式 knknknknkknacacacaafa22111),(n若敌手得到一段长为若敌手得到一段长为2n的密钥序列的密钥序列由此可推出线性反馈移位寄存器连续的由此可推出线性反馈移位寄存器连续的n+1个状态：个状态：1 22nzz zz11 21222312311122122nnnnnnnnnnnSz z

2、za aaSz zza aaSzzzaaa记为记为记为l做矩阵l而l若X可逆，则12nXSSS122311221112111nnnnnnnnnnnnaaaaaaaaacccaaacccX111122nnnnncccaaaX解密算法加密算法密钥k=(k0, k1, kt-1 )密钥k=(k0, k1, kt-1 )明文明文x=(x0, x1, xm-1)明文明文x=(x0, x1, xm-1)密文密文x=(y0, y1, ym-1)Feistel加密结构加密结构输入是分组长为输入是分组长为2w的明文和一个密钥的明文和一个密钥K。将每组明。将每组明文分成左右两半文分成左右两半L0和和R0，在进行完

3、，在进行完n轮迭代后，左轮迭代后，左右两半再合并到一起以产生密文分组。其第右两半再合并到一起以产生密文分组。其第i轮迭轮迭代的输入为前一轮输出的函数：代的输入为前一轮输出的函数：其中其中Ki是第是第i轮用的子密钥，由加密密钥轮用的子密钥，由加密密钥K得到。一得到。一般地，各轮子密钥彼此不同而且与般地，各轮子密钥彼此不同而且与K也不同。也不同。111,iiiiiiLRRLF RKxykDESyxkDES-1xiyikDESyixkDES-1+64 bit存储64 bit存储y i-1 + +xixiyiyikkXi 64bitXi 64bitYi 64bitYi 64bitDES DES-1 选

4、最左边 k 位 选最左边 k 位k bitk bityi-Lyi-2yi-1 +xiyik64bit64bitDES 选最左边选最左边 k 位位ki64 bit 寄存寄存器器k bitk bit +xiyik64bit64bit DES-1 选最左边选最左边 k 位位k bit64 bit 寄存寄存器器k bitki 输入输入 64 bit明文明文数据数据 初始置换初始置换IP 乘积变换乘积变换 （16轮迭代）轮迭代） 逆初始置换逆初始置换IP-1 64 bit密文数据密文数据 输出输出 标准数据加密算法标准数据加密算法(y3 , y2, y1 , y0)=(0,0,1,0) 00112233

5、44556677100011111110001111111000110111100010111110000011111001001111101000111110yxyxyxyxyxyxyxyx 定理定理3.1 系数在系数在GF(28)上的多项式上的多项式a3x3+a2x2+a1x+a0是模是模x4+1可逆的，当且仅当矩阵可逆的，当且仅当矩阵在在GF(28)上可逆。上可逆。0321103221033210aaaaaaaaaaaaaaaa将以上关系写成矩阵形式即得（证毕）032103211032103221032103321032101000010000100001aaaahhhhaaaahhhh

6、aaaahhhhaaaahhhh SMS4概况l SMS4分组密码算法是国家密码管理局于分组密码算法是国家密码管理局于2006年年1月月6日日公布的无线局域网产品使用的密码算法，是国内官方公公布的无线局域网产品使用的密码算法，是国内官方公布的第一个商用密码算法。布的第一个商用密码算法。l SMS4是一个分组密码算法，分组长度和密钥长度均为是一个分组密码算法，分组长度和密钥长度均为128比特。加密算法与密钥扩展算法都采用比特。加密算法与密钥扩展算法都采用32轮非线性迭轮非线性迭代结构。代结构。非线性变换中所使用的非线性变换中所使用的S盒是一个具有很好密码学特性盒是一个具有很好密码学特性的、由的、

7、由8比特输入产生比特输入产生8比特输出的置换，在设计原理上，比特输出的置换，在设计原理上，SMS4比比AES的的S盒设计多了一个仿射变换。盒设计多了一个仿射变换。SMS4有很高的灵活性，所采用的有很高的灵活性，所采用的S盒可以灵活地被替换，盒可以灵活地被替换，以应对突发性的安全威胁。算法的以应对突发性的安全威胁。算法的32轮迭代采用串行处轮迭代采用串行处理，这与理，这与AES中每轮使用代换和混淆并行地处理整个分中每轮使用代换和混淆并行地处理整个分组有很大不同。组有很大不同。l 它的解密算法与加密算法的结构相同，只是轮密钥的使它的解密算法与加密算法的结构相同，只是轮密钥的使用顺序相反，解密轮密钥

8、是加密轮密钥的逆序。用顺序相反，解密轮密钥是加密轮密钥的逆序。 SMS4算法的术语说明 在在SMS4算法中，用算法中，用 表示比特的向量集，表示比特的向量集， 中的元素称为字节，中的元素称为字节， 中的元素称为字。中的元素称为字。SMS4算法中构造了一个与算法中构造了一个与AES类似的类似的S盒，盒，该该S盒是一个固定的盒是一个固定的8比特输入比特输入8比特输出的置比特输出的置换，记为换，记为 SMS4中的采用了两个基本运算：中的采用了两个基本运算： ，32比特异比特异或；或； ，32比特循环左移比特循环左移 i i 位位。eZ282Z322Z(.)SboxiSMS4算法的术语说明（续）算法的

9、术语说明（续）lSMS4算法的加密密钥长度为算法的加密密钥长度为128比特，表比特，表示为，示为， 其中，其中， 为字。为字。l轮密钥为，轮密钥为， ， 为字。轮密钥为字。轮密钥由加密密钥通过密钥扩展算法生成。由加密密钥通过密钥扩展算法生成。l 为系统参数，为系统参数，l 为固定参数，用于密钥为固定参数，用于密钥扩展算法。扩展算法。),(3210MKMKMKMKMK iMK3 , 2 , 1 , 0i),(3110rkrkrkirk),(3210FKFKFKFKFK ),(3110CKCKCKCKSMS4 的轮函数的轮函数l设输入为设输入为 ，轮密钥为，轮密钥为 ，则轮函数为：则轮函数为：l其

10、中其中 称为合成置换，是一个由非线称为合成置换，是一个由非线性变换和线性变换复合而成的可逆变换，即性变换和线性变换复合而成的可逆变换，即 43223210)(),(ZXXXX322Zrk)(),(32103210rkXXXTXrkXXXXF322322:ZZT(.)(.)LTXiXi+1Xi+2Xi+3rkia0a1a2a3b0b1b2b3ssssB2B10B18B1，如果，如果gcd(a, n) = 1,则则:a?(n) 1mod n. eg: 求求3801的后两位数字的后两位数字 解：解： 3801（mod 100）的结果）的结果 ?(100) = 100(1-1/2)(1-1/5) =

11、40， 有有3801 (340)2031 3 (mod 100)例例 使用使用RSA算法计算：如果算法计算：如果p=11，q=17，选取，选取e=7，求解密密钥，求解密密钥d。若令明文为若令明文为m=5，求密文，求密文c。验证。验证加解密的正确性。加解密的正确性。解：解：p=11，q=17，那么，那么n=pq=187 加密密钥加密密钥e=7，与，与 互素，互素，那么，通过扩展的欧几里德算法，可以那么，通过扩展的欧几里德算法，可以求得解密密钥求得解密密钥公开公开e和和n，将，将d作为私钥保密，舍弃作为私钥保密，舍弃p和和q。当当m=5，则加密为，则加密为验证解密正确性验证解密正确性 所以，使用所

12、以，使用RSA可以正确进行公开密钥加可以正确进行公开密钥加解密。解密。(1)(1)160pq1mod16023de7mod1875 mod187146ecm232 1111mod187146 mod187(146 )146mod187( 2)146mod1875dmc 是否有不通过分解大整数的其他攻击途径？下面证明由n直接确定(n)等价于对n的分解。设n=pq中，pq，由(n)=(p-1)(q-1)，则有 p+q=n-(n)+1以及由此可见，由p、q确定(n)和由(n)确定p、q是等价的。nnnnqpqp41)(422 1212ppqpqqpqpql 解密过程解密过程：l计算明文计算明文: l

13、 这是因为这是因为21modxCMpC21modmodmodmodkkxkxkCy My MpppMpCgyElGamal 解密解密椭圆曲线密码体制的优点椭圆曲线密码体制的优点l 安全性高安全性高攻击有限域上的离散对数可用指数积分法，运算复杂度攻击有限域上的离散对数可用指数积分法，运算复杂度为为 。 对对ECCECC上离散对数攻击并不上离散对数攻击并不有效。有效。攻击攻击ECCECC上离散对数问题的方法只有大步小步法，复杂上离散对数问题的方法只有大步小步法，复杂度为度为 。p pmaxmax是是ECCECC形成的交换群的阶形成的交换群的阶的最大素因子，因此的最大素因子，因此ECCECC上的密码

14、体制比基于有限域上上的密码体制比基于有限域上离散对数问题的公钥体制更安全离散对数问题的公钥体制更安全32)log)(log(log(expppO)(exp(logmaxpOfffY0Y1YL-1bbbnnnnnIV=CV0CV1CVL-1CVL明文M被分为L个分组Y0,Y1,YL-1b:明文分组长度n:输出hash长度CV：各级输出，最后一个输出值是hash值无碰撞压缩函数f是设计的关键x ElGamal数字签名体制数字签名体制 ElGamal数字签名体制是数字签名体制是T.ElGamal在在1985年发表关于年发表关于ElGamal公开密钥密公开密钥密码时给出的两个体制之一，该体制中重要码时

15、给出的两个体制之一，该体制中重要的有的有NIST于于1991年公布的数字签名标准年公布的数字签名标准中所使用的数字签名算法（中所使用的数字签名算法（DSA），专），专门用于数字签名，它的安全性主要基于求门用于数字签名，它的安全性主要基于求解离散对数问题的困难性。解离散对数问题的困难性。ElGamal数字签名l 1参数与密钥生成参数与密钥生成 选取大素数选取大素数p, 是一个本原元。是一个本原元。p和和g公开。公开。 随机选取整数随机选取整数x,1xp 2，计算，计算 。 公钥为公钥为y，私钥为，私钥为x。l 2签名签名 对于消息对于消息m，首先随机选取一个整数，首先随机选取一个整数k, 1kp

16、 2 ，然后计算：然后计算： , 则则m的签名为的签名为(r, s)，其中，其中h为为Hash函数。函数。l 3验证验证 对于消息签名对对于消息签名对(m, (r, s)，如果：，如果： 则则(r, s)是是m的有效签名。的有效签名。*pgZmodxygpmodkrgp1( ( )mod(1)sh mxr kp()modrsh my rgp因为因为s = (h (m) xr) k 1 mod (p 1)我们有我们有sk+xr =h(m)mod(p 1)所以所以()()modh mskxrskxrrsggg gy rp签名合理性证明签名合理性证明2. ElGamal签名的安全性分析签名的安全性分

17、析 ElGamal数字签名可能存在以下三数字签名可能存在以下三种攻击方式。种攻击方式。第一种攻击方法第一种攻击方法：由于私钥：由于私钥 是保密的，是保密的，所以，攻击者要得到这个密钥，必须求解所以，攻击者要得到这个密钥，必须求解离散对数问题离散对数问题 ，这是一个困难问，这是一个困难问题。但是，秘密随机数题。但是，秘密随机数 一旦暴露，则一旦暴露，则解：解： ，即可求得密，即可求得密钥钥 ，方案被攻破。，方案被攻破。xloggyk1( ( )mod(1)xh msk rpx第二种攻击方法第二种攻击方法：关于秘密随机数：关于秘密随机数K的另一个问题是：不可用同一个的另一个问题是：不可用同一个K作

18、作两次签名。但若两次签名。但若A利用相同利用相同K签名两签名两次，即次，即 的签名为的签名为 及及 ，则攻击者可以由联立方程式则攻击者可以由联立方程式 可得：可得： ，同时可以求得同时可以求得K。因此，同一个。因此，同一个K不不可重复使用。可重复使用。12,m m1( ,)r s2( ,)r s1122()mod(1)()mod(1)h mxrksph mxrksp11122121 ()() ()mod(1)xh m sh m sssrp5.4 DSS数字签名标准l1参数与密钥生成参数与密钥生成l 选取大素数选取大素数p，满足，满足 p ，其中，其中512L1024且且L是是64的倍数。显然，

19、的倍数。显然，p是是L位长的素位长的素数，数，L从从512到到1024且是且是64的倍数。的倍数。l 选取大素数选取大素数q，q是是p 1的一个素因子的一个素因子且且 ，即，即q是是160位的素数且是位的素数且是p 1的的素因子。素因子。l 选取一个生成元选取一个生成元 ，其中，其中h是一是一个整数，满足个整数，满足1hp 1并且并且 。l 随机选取整数随机选取整数x，0 xq，计算，计算 。l p、q和和g是公开参数，是公开参数，y为公钥，为公钥，x为私钥。为私钥。12L2L15916022q(1)/modpqghp(1)/mod1pqhpmodxygpl2签名签名 对于消息对于消息m，首先

20、随机选取一个整数，首先随机选取一个整数k , 0kq，然后计算：然后计算： , 则则m的签名为的签名为(r, s)，其中，其中h为为Hash函数，函数，DSS规规定定Hash函数为函数为SHA-1。l3验证验证 对于消息签名对对于消息签名对(m, (r, s)，首先计算：，首先计算： 然后验证：然后验证： 如果等式成立，则如果等式成立，则(r, s)是是m的有效签名；否则签的有效签名；否则签名无效。名无效。(mod )modkrgpq1( ( )modskh mxrq11mod , ( ) modwsquh m wqvr122mod , ( mod )moduuurwqvg ypq算法合理性证

21、明算法合理性证明l因为： s=k1 (h (m)+ xr)mod q所以： ks = (h (m)+ xr)mod ql于是我们有：121()()( () (mod )mod =(mod )mod =(mod )mod =(mod )mod =(mod )mod =(mod )mod =(mod )mod =uuh m wrwh m wxrwh mxr wkswksskvg ypqgypqggpqgpqgpqgpqgpqr第七章 密码协议复习要点复习要点lDiffie-Hellman密钥交换原理及安全性lShamirShamir门限方案门限方案lKerberos认证协议认证协议用户B用户ADi

22、ffie-Hellman密钥交换lW.DiffieW.Diffie和和M.Hellman1976M.Hellman1976年提出年提出l算法的安全性基于求离散对数的困难性算法的安全性基于求离散对数的困难性选择随机数xp计算YA= gx mod p选择随机数yp计算YB= gy mod pYAYB计算K=YA y = gxy mod p计算K=YB x = gxy mod p中间人攻击用户B选择随机数yp计算YB= gy mod p计算KBC =YCy = gyz mod p用户A选择随机数xp计算YA= gx mod p计算KAC=YC x = gxz mod p敌手C选择随机数zp计算YC=

23、 gz mod p计算KBC =YB z = gyz mod pYAYCYC计算KAC =YA z = gxz mod pYB端到端协议l1992年，Diffie、Oorschot和Wiener提出了一个端到端协议（station-to-station protocol） A B ga C（B）, gb, Ek（SigB（ga, gb） ） C（A）, Ek（SigA（ga, gb） ） 隐式密钥认证l Matsumoto-Takashima-Imai密钥协商l 可抵抗中间人攻击BABAbrarBCAC),(),(),(,),()(aSayAIDSigyAIDAC门限方案的一般概念门限方案的一

24、般概念l 秘密秘密s s被分为被分为n n个部分个部分, ,每个部分称为每个部分称为shadow,shadow,由一个参与由一个参与者持有，使得者持有，使得l 由由k k个或多于个或多于k k个参与者所持有的部分信息可重构个参与者所持有的部分信息可重构s s。l 由少于由少于k k个参与者所持有的部分信息则无法重构个参与者所持有的部分信息则无法重构s s。l 称为称为(k,n)(k,n)秘密分割门限方案，秘密分割门限方案，k k称为门限值。称为门限值。l 少于少于k k个参与者所持有的部分信息得不到个参与者所持有的部分信息得不到s s的任何信息称的任何信息称该门限方案是完善的。该门限方案是完善

25、的。ShamirShamir门限方案门限方案l基于多项式基于多项式LagrangeLagrange插值公式插值公式设设(x(x1 1,y,y1 1), ),(x,(xk k,y,yk k) )是平面上是平面上k k个点构成的点集，个点构成的点集，其中其中x xi i(i=1,(i=1,k,)k,)各不相同，那么在平面上存在唯各不相同，那么在平面上存在唯一的一的k-1k-1次多项式次多项式f(x)f(x)通过这通过这k k个点个点. .若把秘密若把秘密s s取做取做f(0)f(0)，n n个个shadowshadow取做取做f(xf(xi i)(i=1,)(i=1,n),n),那么利用其那么利用

26、其中任意中任意k k个个shadowshadow可以重构可以重构f(x)f(x)，从而可以得到，从而可以得到秘密秘密s sShamirShamir门限方案门限方案l 有限域有限域GF(q),qGF(q),q为大素数，为大素数，qn+1qn+1。秘密。秘密s s是是GF(q)0GF(q)0上均匀选取的随机数，表示为上均匀选取的随机数，表示为ssR RGF(q)0.k-1GF(q)0.k-1个系个系数数a a1 1,a ,a2 2, ,a ak-1k-1选取选取a ai i R RGF(q)0.GF(q)0.在在GF(q)GF(q)上构造一个上构造一个k-1k-1次多项式次多项式f(x)=af(x

27、)=a0 0+a+a1 1x+x+a+ak-1k-1x xk-1k-1l NN个参与者个参与者P P1 1, ,P,Pn n,P,Pi i的的ShadowShadow为为f(i)(i)。任意。任意k k个参与个参与者得到秘密，可使用者得到秘密，可使用(i(il l,f(i,f(il l)|l=1,)|l=1,k,k构造方程组构造方程组)()()()()()(11101111110kkkkkkkifiaiaaifiaiaaShamirShamir门限方案门限方案l 由由LagrangeLagrange插值公式插值公式)(mod)()()(11qiiixifxfkjkjllljlj)(mod)() 1(111qiiiifskjkjllljljkShamirShamir门限方案门限方案l如果如果k-1k-1个参与者想获得个参与者想获得s s，可构造，可构造k-1k-1个方程，个方