群论在计算机安全领域中应用.ppt
《群论在计算机安全领域中应用.ppt》由会员分享,可在线阅读,更多相关《群论在计算机安全领域中应用.ppt(24页珍藏版)》请在三一文库上搜索。
1、群论在计算机安全领域中的应用,搜集整理: 01047 牛先芳 信息管理系 E-mail: ,群论在计算机安全领域中的应用,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 + a2x
2、2 + 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
3、+ 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).关于|E
4、p(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=
5、(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攻击 对中间人攻击的抵抗力远好于“
6、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是一个大素数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 群论 计算机 安全 域中 应用
链接地址:https://www.31doc.com/p-2600637.html