信息安全原理与应用第四章-公钥密码

电子工业出版社，《信息安全原理与应用》1信息安全原理与应用第四章公钥密码电子工业出版社，《信息安全原理与应用》2内容提要•公开密钥密码算法的基本思想•公开密钥密码算法的数学基础•一些经典算法电子工业出版社，《信息安全原理与应用》3公开密钥密码的重要特性①加密与解密由不同的密钥完成加密:XY:Y=EKU(X)解密:YX:X=DKR(Y)=DKR(EKU(X))②知道加密算法，从加密密钥得到解密密钥在计算上是不可行的③两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的)X=DKR(EKU(X))=EKU(DKR(X))电子工业出版社，《信息安全原理与应用》用公钥密码实现保密•用户拥有自己的密钥对(KU,KR)•公钥KU公开，私钥KR保密•AB:Y=EKUb(X)•B:DKRb(Y)=DKRb(EKUb(X))=X4电子工业出版社，《信息安全原理与应用》用公钥密码实现鉴别•条件:两个密钥中任何一个都可以用作加密而另一个用作解密•鉴别:AALL:Y=DKRa(X)ALL:EKUa(Y)=EKUa(DKRa(X))=X•鉴别+保密:AB:Z=EKUb(DKRa(X))B:EKUa(DKRb(Z))=X5电子工业出版社，《信息安全原理与应用》公钥密钥的应用范围•加密/解密•数字签名（身份鉴别）•密钥交换6电子工业出版社，《信息安全原理与应用》7基本思想和要求•涉及到各方：发送方、接收方、攻击者•涉及到数据：公钥、私钥、明文、密文•公钥算法的条件：–产生一对密钥是计算可行的–已知公钥和明文，产生密文是计算可行的–接收方利用私钥来解密密文是计算可行的–对于攻击者，利用公钥来推断私钥是计算不可行的–已知公钥和密文，恢复明文是计算不可行的–(可选)加密和解密的顺序可交换电子工业出版社，《信息安全原理与应用》8陷门单向函数•单向陷门函数是满足下列条件的函数f：(1)给定x，计算y=fk(x)是容易的；(2)给定y,计算x使x=fk-1(y)是不可行的。(3)存在k，已知k时,对给定的任何y，若相应的x存在，则计算x使fk-1(y)是容易的。电子工业出版社，《信息安全原理与应用》9内容提要•公开密钥密码算法的基本思想•公开密钥密码算法的数学基础•一些经典算法电子工业出版社，《信息安全原理与应用》10公钥密码基于的数学难题•背包问题•大整数分解问题（TheIntegerFactorizationProblem,RSA体制）•离散对数问题−有限域的乘法群上的离散对数问题(TheDiscreteLogarithmProblem,ElGamal体制）−定义在有限域的椭圆曲线上的离散对数问题（TheEllipticCurveDiscreteLogarithmProblem,类比的ElGamal体制）电子工业出版社，《信息安全原理与应用》11算术基本定理•任意大于1的整数a都能被因式分解为如下的唯一形式：•其中都是素数而且每一个。ttPPPa2121tPPP21,3,2,10ii电子工业出版社，《信息安全原理与应用》12中国剩余定理•中国剩余定理：设自然数m1,m2,…,mr两两互素，并记N=m1m2…mr，N=miMi（i=1,…r）则同余方程组•在模N同余的意义下有唯一解。电子工业出版社，《信息安全原理与应用》Fermat定理•Fermat定理:p素数，a是整数且不能被p整除，则:ap-11modp•推论:p素数，a是任意整数，则:apamodp13电子工业出版社，《信息安全原理与应用》Euler定理•Euler函数(n)定义为小于n且与n互素的正整数个数–n是素数，(n)=n-1–若n的因子分解为n=Piai,ai0,Pi互不相同，则(n)=Piai(1-1/Pi)=n(1-1/p1)(1-1/p2)…(1-1/pn)p1,p2,…,pn是r的素数因子–若gcd(m,n)=1，则(mn)=(m)(n)，特别地，若pq且都是素数，(pq)=(p-1)(q-1)•Euler定理:若a与n为互素的正整数，则：a(n)1modn•推论:若n=pq，pq都是素数，k是任意整数，则mk(p-1)(q-1)+1mmodn，对任意0mn14电子工业出版社，《信息安全原理与应用》离散对数难题•设G是一个阶为p的有限循环群，g是它的生成元，则G的元素可表示为：G={1，g，g2，…，pp-1}，由此可见，对G的任何元素y，一定存在某一个正整数x，0≤x≤p-1，使得y=gxmodp，这里，称整数x是群G上元素y关于生成元g的离散对数。•离散对数难题（DiscreteLogarithmProblem，DLP）是：在G上，对于方程y=gxmodp，–已知g，x，p，计算y是容易的，–已知y，g，p，计算x是困难的。•密码学中常用的主要有三个群的离散对数有限域GF（p）的乘法群有限域GF（2n）上的乘法群有限域F上的椭圆曲线群15电子工业出版社，《信息安全原理与应用》有限域GF(p)上的离散对数•如果a是素数p的原根，则数amodp，a2modp，…，ap-1modp是不同的并且包含1到p-1的整数的某种排列，也即{amodp，a2modp，…，ap-1modp}={1，2，…，p-1}=Zp*•因此，乘法群Zp*是一个有限循环群。•取p＝13，有限域GF(13)={0,1,2,…,12}上非零元组成的乘法群：Z13*={1,2,…,12}。1617整数的幂，模13电子工业出版社，《信息安全原理与应用》18公钥方案的安全性•和对称方案一样，强力攻击是计算上不可行的，但使用的密钥更大(512bits)•安全性基于一些陷门单向函数，只是计算上不可行–要求使用非常大的数–因此比对称方案计算速度慢•选择明文攻击–通过对报文附加随机比特来实现电子工业出版社，《信息安全原理与应用》19内容提要•公开密钥密码算法的基本思想•公开密钥密码算法的数学基础•一些经典算法电子工业出版社，《信息安全原理与应用》20内容提要•公开密钥密码经典算法–Diffie-Hellman密钥交换算法–背包算法–RSA算法–ElGamal算法–椭圆曲线密码算法ECC电子工业出版社，《信息安全原理与应用》21Diffie-Hellman密钥交换•是第一个公钥方案•Diffie&Hellmanin1976–nowknowthatJamesEllis(UKCESG)secretlyproposedtheconceptin1970•使用在一些商业产品中•密钥交换方案不能用于交换任意信息允许两个用户可以安全地建立一个秘密信息，用于后续的通讯过程该秘密信息仅为两个参与者知道•算法的安全性依赖于有限域上计算离散对数的难度•在美国的专利1997年4月29日到期电子工业出版社，《信息安全原理与应用》22Diffie-Hellman密钥交换•算法：–双方选择素数p以及p的一个原根a–用户A选择一个随机数Xap，计算Ya=aXamodp–用户B选择一个随机数Xbp，计算Yb=aXbmodp–每一方保密X值，而将Y值交换给对方–用户A计算出K=YbXamodp–用户B计算出K=YaXbmodp–双方获得一个共享密钥(aXaXbmodp)•素数p以及p的原根a可由一方选择后发给对方电子工业出版社，《信息安全原理与应用》23Diffie-Hellman密钥交换的攻击•中间人攻击–1双方选择素数p以及p的一个原根a(假定O知道)–2A选择Xap,计算Ya=aXamodp,AB:Ya–3O截获Ya,选Xo,计算Yo=aXomodp,冒充AB:Yo–4B选择Xbp,计算Yb=aXbmodp,BA:Yb–5O截获Yb,冒充BA:Yo–6A计算:(Yo)Xa(aXo)XaaXoXamodp–7B计算:(Yo)Xb(aXo)XXbaXoXbmodp–8O计算:(Ya)XoaXaXomodp,(Yb)XoaXbXomodp•O无法计算出aXaXbmodp•O永远必须实时截获并冒充转发，否则会被发现电子工业出版社，《信息安全原理与应用》24内容提要•公开密钥密码经典算法–Diffie-Hellman密钥交换算法–背包算法–RSA算法–ElGamal算法–椭圆曲线密码算法ECC电子工业出版社，《信息安全原理与应用》25背包问题•背包问题描述：给定重量分别为a1,a2,…an的n个物品,装入一个背包中,要求重量等于一个给定值那么，究竟是那些物品？•0-1背包问题：–给定一个正整数S和一个背包向量A=(a1,…,an)，其中ai是正整数，求满足方程S=∑aixi的二进制向量X=(x1,…,xn)。–这是一个NP完全问题，因为对于给定的子集易于验证其和是否为S。然而，找到一个子集使其和为S要困难得多，因为有2n个可能的子集，试验所有子集的时间复杂性为T=O（2n），解决这个问题所需要的时间与n呈指数增长电子工业出版社，《信息安全原理与应用》26背包问题用于公钥密码学•做法：明文为X，S为密文•奥妙在于有两类背包，一类可以在线性时间内求解，另一类则不能•把易解的背包问题修改成难解的背包问题–公开密钥使用难解的背包问题–私钥使用易解的背包问题电子工业出版社，《信息安全原理与应用》27易解的背包问题——超递增背包•满足下列条件的背包ai∑aj(j=1,…,i-1)•这样的背包也被称为简单背包•求解–从最大的ai开始，如果S大于这个数，则减去ai,记xi为1，否则记xi为0–如此下去，直到最小的ai•例如背包序列{2,3,6,13,27,52}–求解70的背包•结果为{2,3,13,52}•所以，密文70对应的明文为110101电子工业出版社，《信息安全原理与应用》28转换背包•简单背包用作私钥•如何产生相应的公钥——转换–做法：选择一个整数m∑ai(i=1,…,n)然后选择一个与m互素的整数w，然后ai'=wai(modm)(i=1,…,n)这里的ai'是伪随机分布的这样得到的背包是非超递增背包电子工业出版社，《信息安全原理与应用》29基于背包问题的公钥密码系统——MH公钥算法•加密–将明文分为长度为n的块X=(x1,…,xn)–然后用公钥A'=(a1',…,an')，将明文变为密文S=E(X)=∑ai'xi•解密–先计算S'=w-1Smodm–再求解简单背包问题S'=∑aixi电子工业出版社，《信息安全原理与应用》30Eaxmple-从私钥计算公钥•私钥{2,3,6,13,27}•w=31,m=105231mod105=62331mod105=93631mod105=811331mod105=882731mod105=102•公钥{62,93,81,88,102}电子工业出版社，《信息安全原理与应用》31Eaxmple-加密•消息=011001101010111•01100对应于93+81=174•11010对应于62+93+88=243•10111对应于62+81+88+102=333电子工业出版社，《信息安全原理与应用》32Eaxmple-解密•解密者知道{2,3,6,13,27},w,m•计算w(w-1)=1mod(m)•w-1=61•17461mod105=9=3+6，对应于01100；•24361mod105=18=2+3+13，对应于11010；•33361mod105=48=2+6+13+27，对应于10111。•因此，消息=011001101010111电子工业出版社，《信息安全原理与应用》33背包密码算法的意义•是第一个推广的公钥加密算法•安全性基于背包问题•在实践过程中，大多数的背包方案都已被破解，或者证明存在缺陷•它表示了如何将NP完全问题用于公开密钥算法电子工业出版社，《信息安全原理与应用》34内容提要•公钥密码经典算法–Diffie-Hellman密钥交换算法–背包算法–RSA算法–ElGamal算法–椭圆曲线密码算法ECC电子工业出版社，《信息安全原理与应用》35RSA算法•RSA算