群论在计算机安全领域中应用.ppt
群论在计算机安全领域中的应用,搜集整理: 01047 牛先芳 信息管理系 E-mail: rosalieccermail.net,群论在计算机安全领域中的应用,1.椭圆曲线密码 2.子群成员问题 3.DES,1.椭圆曲线密码,椭圆曲线密码介绍,1985年Miller,Koblitz 独立提出 y2+axy+by=x3+cx2+dx+e 曲线上的点连同无穷远点O的集合 加法:若曲线三点在一条直线上,则其和为零 倍数:一个点的两倍是它的切线与曲线的另一个交点,问题阐释,有限域上的椭圆曲线 设K表示一个有限域，E是域K上的椭圆曲线，则E是一个点的集合： E/K = ( x, y ) | y2+ a1xy + a3y = x3 + a2x2 + a4x + a6, a1, a3, a2, a4, a6 x, y K O 其中O表示无穷远点。 在E上定义+运算，P + Q = R，R是过P、Q的直线与曲线的另一交点关于x轴的对称点，当P = Q时R是P点的切线与曲线的另一交点关于x轴的对称点。这样，( E, + )构成可换群( Abel群)，O是加法单位元(零元)。椭圆曲线离散对数问题ECDLP定义如下：给定定义在K上的椭圆曲线E，一个n阶的点P E/K，和点Q E/ K，如果存在l，确定整数l, 0 l n - 1, Q = lP。前面已经提到，ECDLP是比因子分解难得多的问题。,椭圆曲线密码示意图,椭圆曲线上的加法: P + Q = R 椭圆曲线上一点的2倍: P + P = R.,有限域上椭圆曲线,有限域上椭圆曲线 y2x3+ax+b mod p p是奇素数,且4a3+27b20 mod p y2+xyx3+ax2+b mod 2m 加法公式: P=(x1,y1), Q=(x2,y2) 若x1=x2且y1=-y2,则P+Q=O,否则 P+Q=(x3,y3) x3=2-x1-x2 y3=(x1-x3)-y1 其中, =(y2-y1)/(x2-x1), 如果PQ =(3x12+a)/2y1, 如果P=Q,Ep(a,b),椭圆曲线上的整数点在上述运算下成为一个交换群(Abelian群),记作Ep(a,b).关于|Ep(a,b)|,有如下不等式: p+1-2p1/2 |Ep(a,b)| p+1+2p1/2 该不等式表明: |Ep(a,b)| p G是Ep(a,b)的一个元素,使得nG=O的最小正整数n称为元素G的阶.,有限域上椭圆曲线,有限域上椭圆曲线 y2x3+ax+b mod p p是奇素数,且4a3+27b20 mod p 针对所有的0= x p，可以求出有效的y，得到曲线上的点(x,y)，其中x,y p。记为Ep(a,b) Ep(a,b)中也包括O 加法公式: P+O=P 如果P=(x,y)，则P+(x,-y)=O，(x,-y)点是P的负点，记为-P。而且(x,-y)也在Ep(a,b)中 如果P=(x1,y1)，Q=(x2,y2)，则 P+Q=(x3,y3)为 x3=2-x1-x2 (mod p) y3=(x1-x3)-y1 (mod p) 其中，如果PQ，则 = (y2-y1)/(x2-x1) 如果P=Q，则 = (3x12+a)/(2y1),椭圆曲线密钥交换,双方选择Ep(a,b)以及Ep(a,b)的一个元素G,使得G的阶n是一个大素数 A选择Xn,计算PA=XG, AB: PA B选择Yn,计算PB=YG, BA: PB A计算: X(PB)=XYG B计算: Y(PA)=YXG=XYG 双方获得了一个共享会话密钥(XYG) 不能抵抗replay攻击 对中间人攻击的抵抗力远好于“Simple secret key distribution(Merkle的建议)”,椭圆曲线密钥交换的攻击,双方选择Ep(a,b)以及Ep(a,b)的一个元素G,使得G的阶n是一个大素数 A选择Xn,计算PA=XG, AB: PA E截获PA,选Z,计算PE=ZG,冒充AB:PE B选择Yn,计算PB=YG, BA: PB E截获PB,冒充BA: PE A计算: XZE = XZG B计算: YZE = YZG E计算: ZPA=ZXG, ZPB =ZYG E无法计算出XYG E永远必须实时截获并冒充转发,否则会被发现.,椭圆曲线加密解密,选择Ep(a,b)的元素G,使得G的阶n是一个大素数,秘密选择整数r.计算P=rG,公开(p,a,b,G,P),保密r. 加密M: 选择随机数k,C=kG,M+kP) 如果k使得kG或者kP为O,则要重新选择k. 解密C: (M+kP)-r(kG)=M+krG-rkG=M 加密信息有扩张,椭圆曲线用于加密,找到一个难题： 考虑等式Q=kP，其中Q、P属于Ep(a,b)，kp 已知k和P，计算Q，是容易的 已知Q和P，计算k，是困难的 选择Ep(a,b)的元素G,使得G的阶n是一个大素数 G的阶是指满足nG=O的最小n值 秘密选择整数r，计算P=rG，然后 公开(p,a,b,G,P)，P为公钥 保密r 加密M：先把消息M变换成为Ep(a,b)中一个点Pm 然后，选择随机数k，计算密文Cm=kG,Pm+kP) 如果k使得kG或者kP为O，则要重新选择k. 解密Cm: (Pm+kP)-r(kG)=Pm+krG-rkG=Pm 加密信息有扩张,椭圆曲线密码的安全性,难点: 从P和kP获得k 对椭圆曲线研究的时间短 椭圆曲线要求密钥长度短,速度快 对比: ECC RSA,2.子群成员问题,子群成员问题的例子(1),n,l是自然数,Zn*,的阶为l, := 1,2, l-1是Zn*的l阶子群,A要向B证明.开始时B检查n1, l1, ,Zn*, , l=1,如果不是,停机;否则A,B重复执行下列步骤m次(m=|n|: n的二进制长度) : A随机选择jZl*,计算=j mod n,把发给B B读出并检查是否Zn*,若不是,否定A的证明,停机;若是,从随机带读出一位i(0或1),把i发给A; A计算h=(j+ik) mod n, k=log mod n;把h发给B B读出h,验证是否 h i mod n 容易知道B的所有计算量是|n|的多项式. 上述协议也可以“并行”完成,子群成员问题的例子: 完全性,完全性:如果A遵守协议且,B是否以很大的概率接收A的证明结论? 由于,因此 h mod n = j+ik mod n (h=(j+ik) mod n) = jik mod n = i mod n (=j mod n, =k mod n) 所以B以概率1接收A的证明.,子群成员问题的例子: 合理性,合理性:如果,B是否以很小的概率接收A的证明? A随机选择jZl*,计算=j mod n,把发给B B读出,随机选择i(0或1)发给A; A计算h=(j+ik) mod n, k=log mod n;把h发给B B读出h,验证是否 h i mod n 假如,由于Zn*, 和最多只有一个属于,i为0或1决定B要验证哪一个(或),也决定A如何生成(伪造),A无法事先知道,只好靠猜测,每次A只能有一半的机会猜中,m次后只有2-m机会. 零知识性: 可以证明该协议是完全零知识的.,DES,多重DES的应用,DES是否构成一个闭合群? 任给K1,K2,是否存在K3,使得: EK1EK2 = EK3 Double DES Triple DES ,DES: Expansion table,32 | 01 02 03 04 | 05 04 | 05 06 07 08 | 09 08 | 09 10 11 12 | 13 12 | 13 14 15 16 | 17 16 | 17 18 19 20 | 21 20 | 21 22 23 24 | 25 24 | 25 26 27 28 | 29 28 | 29 30 31 32 | 01,DES: S-box(S1),14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 07 00 15 07 04 14 02 13 01 10 06 12 11 09 05 03 08 04 01 14 08 13 06 02 11 15 12 09 07 03 10 05 00 15 12 08 02 04 09 01 07 05 11 03 14 10 00 06 13,DES: Permutation,16 07 20 21 29 12 28 17 01 15 23 26 05 18 31 10 02 08 24 14 32 27 03 09 19 13 30 06 22 11 04 25,参考文献,离散数学 第3分册 代数结构与组合数学 屈婉玲编著 北京 北京大学出版社 1998 漫话群 邓应生编 出版发行项: 北京 高等教育出版社 1989.10 http:/www.cns911.com/docs/encrypt/enc0015.php 2002.6. http:/www.icst.pku.edu.cn/ 2002.6,
