公钥密码算法RSA

第6讲公钥密码算法《信息安全概论》课程幻灯片主要内容•RSA公钥密码算法•Diffie-Hellman密钥交换协议•EIGamal公钥加密算法一、传统加脱密方式分析加密的目的：(1)不让窃听者读懂----信道上是密文!(2)收方能够正常脱密----有脱密密钥即可！发方收方密钥破译者不知道结论:(1)发方可以不具有脱密的能力！(2)加密密钥可与脱密密钥不同，可以公开一、传统加脱密方式分析(续)传统加密的缺点：1.密钥必须通过可靠信道在脱密前分发完毕!2.密钥的分配、存储与管理非常棘手！3.互不信任的收发双方的抵赖与否认无法判决解决方案:加密密钥公开,脱密密钥保密--非对称的要求：由公开的密钥在实际上求不出保密的密钥发方收方密钥绝对可靠的信道二、公钥密码体制的基本思想（Diffie-Hellman在1977年提出)密码算法有一对密钥：一个用于加密，称为加密密钥；另一个用于脱密，称为脱密密钥。加密密钥是公开的，而脱密密钥是保密的，且加密密钥的公开不会危及脱密密钥的安全。此时，加密消息不受限制(加密密钥公开)，但只有能够脱密者只有一个！二、公钥密码体制的基本思想此时，如果一个用户使用秘密密钥处理信息，其它用户都可使用公开密钥解读处理过的信息。数字签名该方法可实现数字签名。识别签名公开密钥秘密密钥难求出用作加密密钥用作脱密密钥用作签名密钥用作签名识别密钥依赖于特殊的数学难题基于公钥密码的保密通信和数字签名三、RSA密码算法作者：R.Rivest；A.Shamir；L.Adlman（美国麻省理工学院）提出时间：1977年研制，1978发表。数学难题：大合数分解是计算上不可行的。大合数分解问题的困难性已知p和q，很容易计算出p×q＝？；但是，如果已知p×q＝n，由n计算p＝？和q＝？却是十分困难的。这就是因式分解问题。例如：345677×135317=46775974609计算46773080681=？×？困难！解决该问题的一种最直接的方法就是利用每个可能的p试除n（穷举p）。但当n很大时，该方法的计算量太大。最多需试除n次RSA密码算法：Step1用户Bob首先选取两个不同的大素数p,q,并计算出N＝pq和φ(N)＝(p-1)(q-1)。公开密钥：(e,N)秘密密钥：(d,N)明文空间和密文空间：Z/(N)＝{0,1,…,N-1}加密算法：Step2选加密密钥e:0＜e＜φ(N),使得e与(p-1)(q-1)互素。Step3求出满足0＜d＜φ(N)和edmodφ(N)＝1的dc＝memodNAliceBob秘密参数：p,q,φ(N),d最大的公因子是1ed被φ(N)除后所得的余数脱密算法：m＝cdmodN例:设RSA体制中p=3,q=11,取加密密钥e=7因e=7与φ(N)＝20互素,故可解模方程得到d＝3。加密算法：c＝m7mod33脱密算法：m＝c3mod33(1)求脱密密钥d;(2)写出相应的加密算法和脱密算法解:此时N＝p×q＝33,且φ(N)＝(p-1)(q-1)即7dmod20＝1明、密文空间:Z/(33)加密密钥：(e,n)=(7,33)脱密密钥：(d,n)=(3,33)＝(3-1)(11-1)＝20edmodφ(N)＝1故RSA体制为：加密实例:设RSA算法为:当明文m＝8时，密文为：明、密文空间:Z/(33)加密密钥：(e,n)=(7,33)脱密密钥：(d,n)=(3,33)加密算法：c＝m7mod33脱密算法：m＝c3mod33c＝m7mod33＝87mod33＝221mod33＝(210)2×2mod33＝(1024)2×2mod33＝(1024mod33)2×2mod33＝[(31×33＋1)mod33]2×2mod33＝2mod33＝2对密文c＝2的脱密：m＝c3mod33＝8mod33＝8＝23mod33有关RSA公钥密码的几个问题（1）RSA的脱密算法为何正确？N＝pq和φ(N)＝(p-1)(q-1)公开密钥：(e,N)秘密密钥：(d,N)明文空间和密文空间：Z/(N)＝{0,1,…,N-1}加密算法：0＜e,d＜φ(N),使得e与(p-1)(q-1)互素,且edmodφ(N)＝1c＝memodN脱密算法：m＝cdmodNcdmodN＝(memodN)dmodN＝medmodNm＝?问题：现证：当0≤x＜N时，有xedmodN＝xFermat小定理设p是素数，则任意非零整数m，都有xp-1modp＝1首先：由edmodφ(N)＝1和φ(N)＝(p-1)(q-1)存在整数k，使得ed＝k(p-1)(q-1)＋1xk(p-1)(q-1)modp＝1对所有整数x，都有xk(p-1)(q-1)＋1modp＝xmodp即：xedmodp＝xmodp对所有x都成立同理可证：xedmodq＝xmodp对所有x都成立现证：medmodN＝m已证：对所有x，都有qxqxpxpxededmodmodmodmodpqxpqxedmodmod当0≤x＜N时，有xNxedmod孙子定理p与q互素（2）RSA的改进----e和d可以更小将φ(N)＝(p-1)(q-1)由p-1和q-1最小公倍数λ(N)＝lcm(p-1,q-1)代替，就可得到改进后的RSA体制。N＝pq和λ(N)＝lcm(p-1,q-1)公开密钥：(e,N)秘密密钥：(d,N)明文空间和密文空间：Z/(N)＝{0,1,…,N-1}加密算法：0＜e,d＜λ(N),使得e与λ(N)互素,且edmodλ(N)＝1c＝memodN脱密算法：m＝cdmodN改进的RSA：λ(N)整除φ(N)（3）RSA的安全特征①已知p和q、已知φ(N)＝(p-1)(q-1)、或者已知λ(N)＝lcm(p-1,q-1)，都可由公开密钥求出秘密密钥，还可分解n。edmodλ(N)＝1原因：此时，由于e和λ(N)＝lcm(p-1,q-1)已知，通过解方程就可求出秘密参数d。已知证明，即使只知道λ(N)＝lcm(p-1,q-1)的一个倍数，也可分解n，从而破解RSA。（3）RSA的安全特征（续1）②已知一对公、私钥(e,n)和(d,n)，就可分解n原因：此时，由edmodλ(N)＝1可推知ed–1是λ(N)的一个倍数，因而可分解n。意义：只要掌握一个模数n对应的一对密钥，就可破解基于该模数n设计的所有RSA算法。因此，不同的RSA用户，应配发不同的模数n。（3）RSA的安全特征（续2）③公开指数e太小（如e=3），通播信息不安全向用户A1发送密文:memodn1=c1向用户A2发送密文:memodn2=c2………………向用户At发送密文:memodnt=ct如果e很小,可由密文c1,c2,…,ct求出消息m不妨设n1,n2,…,nt互素，则由孙子定理可求出y=memodn1n2…nt如果e很小,就有men1n2…nt,从而memodn1n2…nt=me,在实数域中可求出emy④两个素数p和q不能选择的太接近。⑤p±1和q±1应当有大的素因子。一般取p-1=2p*是素数p*的2倍，这样的素数称为安全素数。⑥脱密密钥不能选择的太小:当脱密指数的位数小于模数N的位数的4分之一时，就可利用连分数方法或L3算法求出秘密指数d.（3）RSA的安全特征（续3）（3）RSA的安全特征（续4）不动点：（A）m=0c＝memodN＝0（B）m=1c＝memodN＝1（C）m=N-1c＝memodN＝(N-1)emodN＝(-1)emodN＝(-1)modN＝N-1（3）RSA的安全特征（续5）)(3231)ln(ln))(ln1(92.1(nnoeO目前分解大合数的最好算法是数域筛法，其计算复杂性是n的二进制位数log2n的亚指数时间:关键参数：1/3穷举攻击的计算复杂性是log2n的指数时间：01)ln(ln)(lnlnnnneen关键参数：1注意：能分解n未必不能破解RSA。(没有证明)（4）RSA的安全界限①当log2n≤512时可分解n(已有实验报道）②当log2n≤512+256时，已证明分解n的计算量可以实现。③密码学界普遍认为，要使RSA安全，log2n至少要大于1024，一般应取2048；更保守的选择是取log2n=4096。N＝pq和λ(N)＝lcm(p-1,q-1)公开密钥：(e,N)秘密密钥：(d,N)加密算法：0＜e,d＜λ(N),使得e与λ(N)互素,且edmodλ(N)＝1c＝memodN脱密算法：m＝cdmodN改进的RSA：（5）RSA的实现方法从随机数中挑选素数，计算量是(log2p)4欧几里德算法求d和检测e:欧几里德算法平方乘算法，计算量是1.5(log2d)次模乘法（6）RSA的应用情况公钥密码主要用于密钥分配和数字签名，很少用于加密。主要是因为运行太慢。前些年一直使用RSA，但最近几年，大多趋向选择椭圆曲线公钥密码。主要原因是破解椭圆曲线公钥密码的最好算法的计算复杂性是N88.0远比破解RSA的计算量大。因此，在安全性相同时，椭圆曲线公钥密码的规模N可以取得更小，因而实现时所需的资源更少，运行速度可以更快。Diffie-Hellman密钥交换协议由W.Diffie和M.Hellman于1976年提出，是至今仍在广泛使用的一种公钥密码技术。一、群F上的离散对数问题定义1设G是一个群，则在已知G中的元a和b，求解整数x，使得ax＝b在群G中成立的问题，称为群G上的离散对数问题。如果G是实数域，则x＝logab，故由a和b求x的问题是求对数问题。在密码学中，由于群G是有限群，因而称之为离散对数问题。二、离散对数问题的求解难度（1）n元域上的离散对数问题最好的求解算法是数域筛法，其计算复杂性与分解同样位数的大合数n的时间相同。（2）椭圆曲线群上的离散对数问题由ax＝b在a和b已知时求x的最好求解算法是ρ算法，其计算复杂性是)(88.0aord其中ord(a)是a的阶----使at＝1的最小正整数t定义设GF(q)是有q个元素的有限域，则存在a∈GF(q)，使得GF(q)＝{0,a,a2,a3,a4,…,aq-1=1}我们称a是有限域GF(q)的一个本原元。三、域GF(q)中本原元的概念备注：（1）一个有限域的本原元有很多；（2）找出给定的有限域的一个本原元不困难。四、Diffie-Hellman密钥交换协议Step4用户U算出uvxxk)(Step6将k作为双方协商的密钥，并销毁xu和xvuxuxStep2用户U随机选取整数xu：1≤xu≤q-2，并算出后,将明传给用户V,并暂时保留xu;Step1选取有限域GF(q)，再选取有限域GF(q)的一个本原元a,并将GF(q)和a公开，全网公用。vxvxStep3用户V随机选取整数xv：1≤xv≤q-2，并算出后,将明传给用户U,并暂时保留xv;Step5用户V算出vuxxk)((1)任何两个人都可协商出会话密钥，不需事先拥有对方的公开或秘密的信息；(2)每次密钥交换后不必再保留秘密信息，减少了保密的负担。前提条件:必须进行身份认证,确保不是与假冒的用户进行密钥交换,否则不能抵抗中间人攻击.中间人攻击:攻击者W在信道中间:假冒U,与V进行密钥交换;同时假冒V,与U进行密钥交换.致使看似U与V交换的密钥,实际上都是与攻击者交换的密钥.五、Diffie-Hellman密钥交换协议的优点:EIGamal公钥密码体制Step1选取有限域GF(q)，再选取有限域GF(q)的一个本原元a,并将GF(q)和a公开；Step2随机选取整数d:1≤d≤q-2,并计算出β＝adStep3将β作为公开的加密密钥，将d作为保密的脱密密钥。EIGamal公钥加密算法与D-H密钥分配的过程一样与D-H协议的差异：（1）D-H将β发给对方，这里将它公开（广播出去）；（2）d都是秘密的。EIGamal公钥加密算法加密算法:对m∈GF(q)\{0},秘密选择一个随机整数k:1≤k≤q-2,则密文c＝(c1,c2)∈M×M,其中脱密变换:对任意密文(c1,c2)∈M×M，明文为kkmcc21和112)(dccm