计算机网络安全与应用技术第二章-rsa

第二章 密码技术-RSA,计算机网络安全与应用技术,卫文学 信息科学与工程学院,2003 山东科技大学,1 数论导引,1 、素数和数的互素除数(因子)的概念： 设z为有全体整数而构成的集合，若 b0且a, b, m属于z 使得a=mb,此时称b整除a.记为ba,还称b为a的除数(因子). 注:若a=mb+r且01被称为素数是指p的因子仅有1,-1,p,-p。,算术基本定理：任何一个不等于0的正整数a都可以写成唯一的 表达式aP11P22Ptt ，这里P1P2P3Pt是素数，其中i0 最大公约数：若a,b,cz，如果ca，cb，称c是a和b的公约数。正整数d称为a和b的最大公约数，如果它满足 d是a和b的公约数。 对a和b的任何一个公约数c有cd。 注：1*. 等价的定义形式是：gcd（a,b）maxk ka，kb2*若gcd（a,b）=1，称a与b是互素的。,2 、模 算术全体整数构成的集合对整数的加法和乘法的两种运算是封闭的且满足算术运算的所有定律，此时我们称整数集合z为整数环。整数环z对除法运算不封闭。 带余除法： az,0，可找出两个唯一确定的整数q和r, 使a=qm+r, 0=r m,q和r这两个数分别称为以m去除a所得到的商数和余数。 (若r=0则ma） 整数同余式和同余方程：定义（同余）称整数a模正整数m同余于整数b，并写ab（mod m）是指mab, m称为模数。 注：1*.ma-ba=q1m+r,b=q2m+r即a和b分别 除以m有 相同的余数。“同余”二字的来源就在于此。,2*.相对于某个固定模数m的同余关系，是整数间的一种等价关系。具有等价关系的三点基本性质：自反性：对任意整数a有aa（mod m）对称性：如果a b( mod m)则ba（mod m）传递性：如果ab (mod m） bc（modm）则 ac(modm)于是，全体整数集合z可按模m（m1）分成一些两两不交的等价类。 3*.整数模m同余类共有m个，他们分别为mk+0,mk+1, mk+2,mk+(m-1); kz，每一个算一类，每一类都可以选一个代表元，一般选这一类中的最小的非负整数。于是称0,1,2,m-1为标准完全剩余系。Z模12的标准剩余系Z12为：0,1,2,3,4,5,6,7,8,9,10,11,4*. 对于某个固定模m的同余式可以象普通的等式那样相加相减和相乘：(1)a(mod m)b(mod m)=(ab)(mod m)(2)a(mod m)*b(mod m)=a*b(mod m) 例子.通过同余式演算证明5601是56的倍数。解： 注意53=12513(mod56)于是有561691(mod56)对同余式的两边同时升到10次幂，即有56560-1。,证明：2231是47的倍数：注意26=64 - 30(mod47), 于是223=(26)325=(26 26)26 25900*(-30)*(32) mod(47)(7)(-30)*(32) (mod47)1(mod47)于是有 47223-1定理：(消去率)对于abac（mod m）来说，若gcd(a,m)1则bc(mod m) 5*.一次同余方程axb(mod m)这个方程有没有解，相当于问有没有那样一个整数x，使得对于某个整数y来说，有ax+my=b定理：如记gcd (a,m)=d,则同余方程axb(mod m)有解的充分必要条件是db。当这个条件满足时，恰有d个模m同余类中的整数是上述方程的解。 证明：略。（从ax+my=b入手）,6*.加法逆元与乘法逆元对加法而言，对每一x，都有一y，使得x+y0 mod m 如：对于2，有6，使得2+60 mod 8， 称y为x的负数，也称加法逆元。如果(a+b)(a+c)mod n，则bc mod n，称为加法的可约率。然而类似的性质对乘法不一定成立。如6x36x72mod 8，但37mod 8。原因是6乘0到7得到的8个数仅为Z8的一部分。即如果将用6乘Z8中每一数看作Z8到Z8的映射的话， Z8中至少有两个数映射到同一个数，因此映射是多到一的，所以对6来说，没有惟一的乘法逆元。但对5来说，5X5 1mod 8，因此5有乘法逆元5，不仅如此，凡是与8互素的几个数1，3，5，7都有乘法逆元。,6*.加法逆元与乘法逆元这一结论可以推广到任一Zn ，设an，gcd(a,n)=1，则a与Zn中任意两个整数b，c相乘，其结果必然不同。因此对1属于Zn ，存在x属于Zn ，使得a * x1mod n，即x是a的乘法逆元。记为：x=a-1设p为一素数，则Zp中每一非零元素都与p互素，因此有乘法逆元，类似于加法可约率，有如下乘法可约率：如果(a x b) (a x c)mod n 且a有乘法逆元，那么对(a x b) (a x c)mod n 两边都可以乘以a-1，使得bc mod n。,3 Fermat定理和Euler定理, Fermat定理：如果p是素数并且a是正整数,gcd(a,p)=1，那么，ap-11(mod p) 证明：z*pzp(,p)=1易见，z*p=1,2,3,(p-1)且因为 gcd(a,p）1知 a z*p=a,2a,3a,(p-1)a= z*p，原因是a z*p内的元素两两不同。他们刚好为1，2，3，（p1）的一个排列(证明见P61第一自然段)。所以 a*2a*3a*(p-1)a1*2*3*(p-1)(modp)ap-1*(p-1)! 1*2*3*(p-1)(mod p)由 （(p1)！，p）1， 所以 ap-11(modp) 也可写成：若（a，p）1 则有apa(modp), Euler 函数 定义(Euler函数(n)：(n)是这样来定义的，当n1 时，(1)1；当n1时，它的值(n)等于比n小而与n互素的正整数的个数。 以n24为例，比24小而与24 互素的正整数为：1，5，7，11，13，17，19，23 因此，我们有(24)8。易见，若p为素数，则(p)p1。 注：1*.若p，q都为素数且pq，此时有 (pq)(p)(q)=（p1）（q1） 证明：考虑zpq剩余类的集合是0，1，2，（pq-1）集合中与pq不互素的元素子集为p,2p,(p-1)q和子集q,2q,(p-1)q以及0，于是若设npq，有(n)=pq-(q-1)+(p-1)+1 =(p-1)(q-1)=(p)(q)例：(21)=(3*7)=(3)(7)=2*6=12.,欧拉定理（Euler）：若整数a于整数n互素，则a(n)1(mod n) 证明：设小于n而和n互素的个正整数为r1,r2,r3,r(n) (1)他们是模n两两互不同余的。对每一个定数i来说，由于a和ri都与n互素，所以gcd(ari,n)=1，所以ari同余于（1）中的某个ri即 ariri (mod n)，1=i=(n)并且当ij时有ari arj(mod n).于是,为 的置换.所以有由(ri,n)=1, 所以,2 公钥密码学,问题的提出 1 、密钥管理量的困难传统密钥管理两两分别用一对密钥时则n个用户需要C(n,2)=n(n-1)/2个密钥当用户量增大时密钥空间急剧增大如:n=100 时C(100,2)=4,995n=5000时C(5000,2)=12,497,500 2 、数字签名的问题传统加密算法无法实现抗抵赖的需求,单钥加密模型,1、什么是公钥密码体制,公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见划时代的文献：W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654单向陷门函数是满足下列条件的函数f：(1) 给定x，计算y=f(x)是容易的；(2) 给定y, 计算x使y=f(x)是困难的。(所谓计算x=f-1(Y)困难是指计算上相当复杂，已无实际意义。),(3)存在，已知 时,对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的。注：1*. 仅满足(1)、(2)两条的称为单向函数；第(3)条称 为陷门性， 称为陷门信息。2*. 当用陷门函数f作为加密函数时，可将f公开，这 相当于公开加密密钥。此时加密密钥便称为公开 钥，记为Pk。 f函数的设计者将 保密，用作解 密密钥，此时 称为秘密钥匙，记为Sk。由于加 密函数时公开的，任何人都可以将信息x加密成 y=f(x)，然后送给函数的设计者（当然可以通过 不安全信道传送）；由于设计者拥有Sk，他自然 可以解出x=f-1(y)。3*.单向陷门函数的第(2)条性质表明窃听者由截获的 密文y=f(x)推测x是不可行的。,2、算法代表背包算法RSA椭圆曲线ECC,3 RSA公钥算法,RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的（见Communitions of the ACM. Vol.21.No.2. Feb. 1978, PP.120-126)该算法的数学基础是初等数论中的Euler（欧拉)定理，并建立在大整数因子的困难性之上。,例子：若Bob选择了p=101和q113，那么，n=11413, (n)=10011211200；然而1120026527，一个正整数e能用作加密指数，当且仅当e不能被2，5，7所整除（事实上，Bob不会分解(n)，而且用辗转相除法（欧式算法）来求得e，使（e, (n)=1)。假设Bob选择了e=3533，那么用辗转相除法将求得：d=e -1 6597(mod 11200), 于是Bob的解密密钥d=6597.Bob在一个目录中公开n=11413和e=3533, 现假设Alice想发送明文9726给Bob，她计算：97263533(mod 11413)=5761,且在一个信道上发送密文5761。当Bob接收到密文5761时，他用他的秘密解密指数（私钥）d6597进行解密：57616597（mod 11413)=9726 注：RSA的安全性是基于加密函数ek(x)=xe(mod n)是一个单向函数，所以对的人来说求逆计算不可行。而Bob能解密的陷门是分解n=pq，知 (n)=(p-1)(q-1)。从而用欧氏算法解出解密私钥d.,4、RSA密码体制的实现 实现的步骤如下：Bob为实现者(1) Bob寻找出两个大素数p和q(2) Bob计算出n=pq和 (n)=(p-1)(q-1).(3) Bob选择一个随机数e(0e (n)，满足（e， (n)）1(4) Bob使用辗转相除法计算d=e-1(mod (n)（p64）(5) Bob在目录中公开n和e作为她的公开钥。密码分析者攻击RSA体制的关键点在于如何分解n。若分 解成功使n=pq，则可以算出(n)（p-1)(q-1)，然后由公 开的e，解出秘密的d。（猜想：攻破RSA与分解n是多项式 等价的。然而，这个猜想至今没有给出可信的证明！）,于是要求：若使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来。建议选择p和q大约是100位的十进制素数。 模n的长度要求至少是512比特。EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位之间，但必须是128的倍数。国际数字签名标准ISO/IEC 9796中规定n的长度位512比特位。为了抵抗现有的整数分解算法，对RSA模n的素因子p和q还有如下要求：(1) |p-q|很大，通常 p和q的长度相同；(2) p-1 和q-1分别含有大素因子p1和q1(3) P1-1和q1-1分别含有大素因子p2和q2(4) p+1和q+1分别含有大素因子p3和q3,5、RSA签名方案签名的基本概念 传统签名（手写签名）的特征： （1）一个签名是被签文件的物理部分； （2）验证物理部分进行比较而达到确认的目的。(易伪造) （3）不容易忠实地“copy”! 定义： (数字签名方案）一个签名方案是有签署算法与验 证算法两部分构成。可由五元关系组（P,A,K,S,V）来刻化： (1) P是由一切可能消息(messages)所构成的有限集合； (2) A是一切可能的签名的有限集合； (3) k为有限密钥空间，是一些可能密钥的有限集合； (4) 任意k K，有签署算法Sigk S且有对应的验证算法 VerkV,对每一个Sigk:p A 和Verk:PA 真，假,满足条件：任意x P,y A.有签名方案的一个签名：Ver(x,y)= 注： 1*.任意kK, 函数Sigk和Verk都为多项式时间函数。 2*.Verk为公开的函数，而Sigk为秘密函数。 3*.如果坏人（如Oscar)要伪造Bob的对X的签名，在计算上是不可能的。也即,给定x，仅有Bob能计算出签名y使得Verk(x,y)真。 4*.一个签名方案不能是无条件安全的，有足够的时间，Oscar总能伪造Bob的签名。 RSA签名：n=pq,P=A=Zn,定义密钥集合K=(n,e,p,q,d)|n=pq,d*e1(mod (n),真 若y=sig(x) 假 若ySig(x),注意：n和e为公钥；p,