第四章-公钥密码体制

1公钥密码技术习题1、设n=91，e=5,根据RSA算法加密明文m=3，计算出密文。给出计算详细步骤。2、设n=35，e=5,试设计一个具体的RSA公开密码体制,并求密文c=10的原文。习题3、在ElGamal密码体制中，设素数p=71，本原根g=7（1）如果接收方B的公开钥是yB=3，发送方A选择的随机整数为k=2,求明文m=30所对应的密文（2）如果用相同的k=2加密另外一个明文m，加密后的密文为C=（49，13），求m4、椭圆曲线y2modp=(x3+ax+b)modp，其中a=1,b=1,p=23。取曲线上的P=(3,10),Q=(9,7)，分别计算P+Q和2P主要内容基本思想1数论简介2RSA算法3椭圆曲线密码体制44.1基本思想对称密钥编码所面临的难题密钥分配：通信密钥太多，管理和分发困难。数字签名和认证。密码体制上的突破Diffie&Hellman,“NewDirectioninCryptography”,1976。首次公开提出了“公开密钥密码编码学”的概念。这是一个与对称密码编码截然不同的方案。提出公开密钥的理论时，其实用性并没有又得到证明：当时还未发现满足公开密钥编码理论的算法；直到1978年，RSA算法的提出。1.背景2.基本特征Bob的公钥Bob私钥因特网加密解密AliceBob加密和解密使用两个不同的密钥公钥PK：公开，用于加密，私钥SK：保密，用作解密密钥一个密钥加密的数据只能用另一个密钥解密3.优点密钥管理加密密钥是公开的；解密密钥需要妥善保存；在当今具有用户量大、消息发送方与接收方具有明显的信息不对称特点的应用环境中表现出了令人乐观的前景。新用户的增加只需要产生一对公共/私有密钥。数字签名和认证只有解密密钥能解密，只有正确的接收者才拥有解密密钥。缺点：公共密钥系统的主要弱点是加密和解密速度慢。实际应用中的加密方式混合加密技术对称密码体制：密钥分发困难公钥体制：加解密效率低将对称加密算法的数据处理速度和公钥算法对密钥的保密功能相结合利用对称加密算法加密传输数据利用非对称加密算法交换会话密钥举例：假设Alice与Bob进行保密通信，过程如下：实际应用中的加密方式密文传输因特网AliceBobBob的公钥Bob私钥会话密钥对称密码和公钥密码对称密码公钥密码一般要求一般要求安全性要求安全性要求①加密和解密使用相同的密钥②收发双方必须共享密钥①同一算法用于加密和解密，但加密和解密使用不同密钥②发送方拥有加密或解密密钥，而接收方拥有另一密钥①密钥必须是保密的②若没有其他信息，则解密消息是不可能或至少是不可行的③知道算法和若干密文不足以确定密钥①两个密钥之一必须是保密的②若没有其他信息，则解密消息是不可能或至少是不可行的③知道算法和其中一个密钥以及若密文干不足以确定另一密钥有关公钥密码的几种常见误解从密码分析的角度看，公钥密码比传统密码更安全。公钥密码是一种通用的方法，传统密码已经过时。传统密码中与密钥分配中心的握手是一件异常麻烦的事情，与之相比，用公钥密码实现密钥分配则非常简单。公钥密码学要解决的问题公钥密码学的概念是为了解决传统密码中最困难的两个问题而提出的：（1）密钥分配问题（2）数字签名问题4.公钥密码算法基础单向函数对于一个函数，如果对于其定义域上的任意x，都容易计算，同时，对于其值域中几乎所有的取值y，计算其逆函数都是不可行的，则函数被称为单向函数。常用单项函数大整数分解（简称IFP）；离散对数问题（简称DLP）；多项式求根菲-赫尔曼问题二次剩余问题)(xf)(xf)(1yf)(xf单向陷门函数对于一个单向函数，如果其逆函数在已知某些辅助信息的情况下容易求解得出，则称该单向函数为单向陷门函数。构造公钥密码系统的关键是如何在求解某个单向函数的逆函数的NP完全问题中设置合理的“陷门”。)(xf)(1yf)(xf单向函数举例例1：y=anxn+an-1xn-1+…+a1x+a0例2：设n是两个大素数p和q的乘积，b是一个正整数，对x∈Zn，令f(x)≡xb(modn)，即f(x)等于被n除所得的余数，人们认为f(x)是一个从Zn到Zn的单向函数5.公钥算法的特点公开密钥算法设计需要有以下基本要求：加密与解密由不同的密钥完成；知道加密算法，从加密密钥得到解密密钥在计算上是不可行的；两个密钥中任何一个都可以作为加密而另一个用作解密。6.公钥密码算法除RSA算法以外，建立在不同计算问题上的其他公钥密码算法有：基于因子分解问题的Rabin算法；椭圆曲线公钥算法；基于有限域中离散对数难题的ElGamal公钥密码算法基于代数编码系统的McEliece公钥密码算法；基于“子集和”难题的Merkle-HellmanKnapsack（背包）公钥密码算法；目前被认为安全的Knapsack型公钥密码算法Chor-Rivest。4.2数论简介最大公因子：任意有限个整数的公因子中的最大一个。必然存在并且惟一，记为。最小公倍数：任意有限个整数的公倍数中的最小一个。必然存在并且惟一，记为。同余式：设n是一个正整数，如果，则称a和b模n同余，记作：，称整数n为同余模。naaa,,,21),,,gcd(21naaanaaa,,,21),,,(21naaalcmZba,nbnamodmod)(modnba1.数论相关术语加法逆元：设，如果存在满足，则称x是a的模n加法逆元。乘法逆元：设，如果存在满足，则称x是a的模n乘法逆元，记为a-1(modn)。整除：设整数a和b，如果存在整数k，使b=ak，则说b能被a整除，记作：a|b。例：3|15，-15|60整除性质：对所有整数a≠0，a|0、a|a成立对任意整数b，1|b成立nZanZx)(mod0naxnZanZx)(mod1nax2.欧几里德（Euclidean）算法一个用于计算两个整数的最大公因子的有效算法，算法依据：。描述如下：（1）输入a和b，其中，，，；（2）如果则依次完成：，否则返回a；（3）输出。时间复杂度为。Zba,0,baba0brbbabar,,modrba),gcd())((lg2nO)mod,gcd(),gcd(babba用欧几里德算法求最大公约数。求：gcd(482,1180)1180=2*482+216482=2*216+50216=4*50+1650=3*16+216=8*2+0所以gcd(482,1180)=2扩展的欧几里德算法扩展欧几里德算法是用来在已知a,b。求解一组p，q，使得p*a+q*b=Gcd(a,b)。原理：Gcd(a,b)=Gcd(b,a%b)所以p*a+q*b=Gcd(a,b)=Gcd(b,a%b)=p*b+q*a%b=p*b+q*(a–a/b*b)=q*a+(p–a/b*q)*b这样它就将ab的线性组合就化简为b与a%b的线性组合。ab都在减小，当b减小到0时，我们就可以得出p=1,q=0然后递归回去就可以求出最终的p,q了扩展的欧几里德算法(s*n)+(b*t)=gcd(n,b)，如果b的乘法逆存在，则gcd(n,b)=1r1←n;r2←b;t1←0;t2←1;如果r20{q←r1/r2;r←r1-q*r2;r1←r2;r2←r;t←t1-q*t2;t1←t2;t2←t;}如果(r1=1)，那么b-1←t1用扩展的欧几里德算法求乘法逆元gcd(11111,12345)12345=1*11111+123411111=9*1234+51234=246*5+45=1*4+14=4*1+01=5-1*4=5-1*(1234-246*5)=247*5-1*1234=247*(11111-9*1234)-1*1234=247*11111-2224*1234=247*11111-2224*(12345-1*11111)=2471*11111-2224*1234511111x(mod12345)=1等价于求解二元一次不定方程11111x+12345y=1的整数解扩展欧几里德算法求乘法逆元11-1mod26qr1r2rt1t2t226111144331104011-2-255-7-726-223511-73026所以，11的乘法逆元是（-7）mod26=19素数(primenumber)定义：如果整数p(p1)只能被1或者它本身整除，而不能被其他整数整除，则其为素数，否则为合数。素数定理：在各种应用中，我们需要大的素数,如100位的素数素数是构成整数的因子，每一个整数都是由一个或几个素数的不同次幂相乘得来的。(),()(),,1lnlnxxxxxxxxx设是小于的素数的个数则且当设m，n是两个整数，如果正整数d满足：(1)d整除m和n，即d|m，d|n;(2)若d’|m且d’|n，则d’|d。则称d是m与n的最大公因数，记为d=(m，n)。若(m，n)=1，则称m与n互素。互素3.欧拉函数欧拉函数（Euler’stotientfunction）欧拉函数φ(n)：表示小于n且与n互素(包括公因子1)的正整数的个数；欧拉函数的性质：对任意素数p，有φ(p)=p–1；对任意两个素数p、q，则对n=pq有：φ(n)=φ(pq)=φ(p)φ(q)=(p–1)(q–1)欧拉定理如a和n是互素的整数，则有：等价形式：nanmod1)(fnanmoda)+1(f欧拉定理推论：有两个素数p和q,令n=pq,对任意整数t和a(0an),有下列等式成立：atφ(n)+1=amodn其中：φ(n)=(p-1)(q-1)。4.同余式性质（1）a≡b(modn)iffamodn=bmodn。（2）反身性：a≡a(modn)。（3）对称性：如果a≡b(modn)，则b≡a(modn)。（4）传递性：如果a≡b(modn)，b≡c(modn)，则a≡c(modn)。（5）如果a≡a1(modn)，b=b1(modn)，则a+b≡a1+b1(modn)，ab≡a1b1(modn)Fermat定理若p素数，a是整数且不能被p整除，则:ap-11modp推论:p素数，a是任意整数，则:apamodp例：计算718mod19a=7,p=1972=49≡11mod1974≡121≡7mod1978≡49≡11mod19716≡121≡7mod19ap-1=718=716*72≡7*11≡1mod19Diffie-Hellman密钥交换是第一个公钥方案Diffie&Hellmanin1976nowknowthatJamesEllis(UKCESG)secretlyproposedtheconceptin1970使用在一些商业产品中密钥交换方案不能用于交换任意信息允许两个用户可以安全地建立一个秘密信息，用于后续的通讯过程该秘密信息仅为两个参与者知道算法的安全性依赖于有限域上计算离散对数的难度在美国的专利1997年4月29日到期Diffie-Hellman密钥交换算法：双方选择素数p以及p的一个原根a用户A选择一个随机数Xap，计算Ya=aXamodp用户B选择一个随机数Xbp，计算Yb=aXbmodp每一方保密X值，而将Y值交换给对方用户A计算出K=YbXamodp用户B计算出K=YaXbmodp双方获得一个共享密钥(aXaXbmodp)素数p以及p的原根a可由一方选择后发给对方2.4RSA算法是第一个较为完善的公钥算法。能够同时用于加密和数字签名，且易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，被普遍认为是目前最优秀的公钥算法之一。目前仍然无法从理论上证明它的保密性能究竟如何，因为目前人们并没有从理论上证明破译RSA的难度与大整数分解问题的难度等价。算法原理