椭圆曲线密码体制E.ppt

椭圆曲线密码（ECC）体制 一般椭圆曲线 有限域上的椭圆曲线 椭圆曲线密码算法 椭圆曲线密码体制的安全性 2 ELGamal密码体制能够在任何离散对数难处 理的有限群中实现。我们已经使用了乘法群Zp*， 但其他群也是合适的候选者，如椭圆曲线群。 椭圆曲线在代数学和几何学上已广泛研究了 150多年之久，有丰富而深厚的理论积累。椭圆曲 线密码体制（Ellipse Curve Cryptosystem，ECC） 在l 985年由Koblitz和Miller提出，不过一直没有像 RSA等密码系统一样受到重视。纵观目前的发展 趋势，椭圆曲线已经逐渐被采用，很可能是一个 重要的发展方向。 3 椭圆曲线并非椭圆，这么命名是因为它们是 由三次方程描述的，而这些三次方程类似于计算椭 圆周长的方程。一般的，描述椭圆曲线方程的形式 是 y2 + axy + by = x3 + cx2 + dx + e 其中a、b、c、d和e是满足一些简单条件的实数 一般来说，椭圆曲线还包含了一个特殊的点 ，即称为无穷远点(Point at Infinity)或零点(Zero Point)的O。 4.4.1 一般椭圆曲线 4 对于椭圆曲线上的点可以定义一种形式的加 法：如果一个椭圆曲线上的三个点处于一条直线 上，那么它们的和为O。从这个定义可以导出椭 圆曲线上点的加法法则。 w (1) O是加法的单位元，因而OO；对于椭 圆曲线上的任何一点P，有P+OP。 w (2) 一条与x轴垂直的线和曲线相交于两个x坐 标相同的点P1=(x，y)和P2(x,y)，同时它也和 曲线相交于无穷远点，因此P1+P2+OO。因而 一个点的负值是与其有着相同x坐标和相反的y坐 标的点，如图4.1(a)所示。 5 6 w(3)要对具有不同x坐标的两个点Q与R进行相加， 先在它们之间画一条直线并求出第三个交点P1。 容易看出这种交点是惟一的。 注意到Q+R+P1O，有Q+RP。 特别地，当Q=R时，相当于对一个点Q加倍 ，只需画出一条切线并求出另一个交点S，那么 Q+Q=2Q=S。 显然，根据定义，此类加法满足交换率和结 合率.而一个点的倍乘定义为 nPP+P+P+P 7 4.4.2 有限域上的椭圆曲线 密码学中关心的是有限域F上的椭园曲线。讨 论比较多的是素域Fp上的椭圆曲线，这里P是一个 素数。选择两个小于P的非负整数a和b满足 4a3 + 27b2 (mod p) 0 用Ep(a，b)表示如下模p的椭圆群中的点(或如 下有限域Fp上的椭圆曲线的点)，再加上一个无穷 远点O。 设(x，y)是Ep(a，b)中的点，x和y是小于p的 非负整数，则有如下椭圆曲线方程： y2 x3 + ax + b (mod p) 8 如取p23，a=b=l，有 4*13 + 27 * 12 (mod 23 ) 8 0， 则y2=x3 + x +1 是椭圆曲线。因此E23(1，1)是一个模 23的椭圆群。产生E23 (1，1)是中点的过程如下： (1) 对x=0,1,2,p-1, 计算x3 + x +1 (mod p)； (2)对于上一步骤得到的每个结果确定它是否有一 个模P的平方根，如果没有，则E23 (1，1)中没有 具有与该结果相应的x坐标的点。如果有，就有两 个平方根y和py，从而点(x，y)和(x，py)是E23 (1，1)中的点(特别情况下，如果结果是0，只有一 个点(x，0)。 9 椭圆曲线E23(1，1)上的点 （0，1）（5，4）（9，7）（17，3） （0，22）（5，19）（11，3）（17，20） （1，7）（6，4）（11，20）（18，3） （1，16）（6，19）（12，19）（18，20） （3，10）（7，12）（12，4）（19，5） （3，13）（7，11）（13，7）（19，18） （4，0）（9，16）（13，16） 10 Ep(a，b)上的加法规则 w P十OP； w如果P(x , y)，则P + ( x , y) =O，点(x，y)是P 的加法逆元，记为 P； w如果P(x1，y1)，Q(x2，y2)，并且PQ，则P + Q = (x3，y3)由下列规则确定: x32 x1 x2 ( mod p ) y3 ( x1 x3) y1 (mod p ) 其中： (y2-y1)/(x2x1) 如果PQ = (3x12a)/2y1 如果 P=Q 11 例子： 考虑P=(3,10) , Q=(9,7) 则： =(710)/(93)=3/6=1/2=11 mod 23 x3=11239=109 17 mod 23 y3=11(3(6)10=89 =20 mod 23 因而P+Q=(17,20). 计算2P: =(3(32)+1)/(2*10)=5/20=1/4=6 mod 23 x3=6233=30=7 mod 23 y3=6(37)10=34= 12 mod 23 因此 2P=(7,12) 12 椭圆曲线群中的离散对数也属于难解问题。 与通常理解的对数概念不同，由于椭圆曲线群中 的运算是加法，加法的倍数对应于原来乘法的指 数，因而椭圆曲线群中的离散对数问题是指已知 群中的Q和R，求解方程： RkQ 中k值的问题。 13 对基于F23的椭圆群y2x3 + 9x + 17，求R=(4， 5)对于Q=(16，5)的离散对数,最直接的方法就是计 算Q的倍数，直到找到R。 Q(16，5)，2Q=(20，20)，3Q(14，14), 4Q=(19，20)，5Q(13，10)， 6Q(7，3)， 7Q(8，7)，8Q(12，17)，9Q(4，5) 因此k关于Q的离散对数是9，对于大素数构成 的群Fp，这样计算离散对数是不现实的，事实上 现在也没有更好的(非指数级的)算法来解离散对 数问题。 14 4.4.3 椭圆曲线密码算法 基于上面讲的椭圆群上的离散对数问题，可以 用椭圆曲线密码(ECC)算法加密，具体方法如下： 首先选择个点G和一个椭圆群Ep(a,b)作为参 数，用户A选择一个私有密钥nA并产生一个公开密 钥PA=nAG。 发送者要加密并发送一个报义Pm给A，可选择 一个随机整数k，并产生由如下点对组成的密文 Cm(kG，Pm+kPA)。 注意这里使用了A的公开密钥PA。要解密这个 报文，A用这个点对的第一个点乘以A的私有密钥 ，再从第二个点中减去这个值 Pm + kPA nA (kG) =Pm + k(nAG) nA (kG) =Pm 15 发送者通过对Pm加上kPA来保护Pm。 除了发送者之外没有人知道k的值，因此即 便PA是公开密钥也没有人能去掉kPA，当然 只有知道nA的人才可以去掉kPA。攻击者在 不知道nA的情况下要想得到报文只能在知 道G和kG的情况下计算出k，这归结为求解 椭圆曲线离散对数问题，是非常困难的。 16 1、用户A选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点， 作为基点G。 2、用户A选择一个私有密钥nA，并生成公开密钥PA=nAG。 3、用户A将Ep(a,b)和点PA，G传给用户B。 4、用户B接到信息后 ，将待传输的明文编码到Ep(a,b)上一 点Pm ，并产生一个随机整数k（kn, n为基点G的阶）。 5、用户B计算点C1= Pm +kPA；C2=kG。 6、用户B将C1、C2传给用户A。 7、用户A接到信息后，计算C1-nAC2，结果就是点Pm 。因 为 Pm + kPA nA (kG) =Pm + k(nAG) nA (kG) =Pm 再对点Pm进行解码就可以得到明文。 利用椭圆曲线进行加密通信的过程： 17 这个加密通信中，如果有一个偷窥者H ，他只能看到Ep(a,b)、 PA 、G、C1、C2 而通过K、G 求nA 或通过C2、G求k 都是相 对困难的。因此，H无法得到A、B间传送 的明文信息。 18 注意到以上的过程并没有说明怎样将 作为字符串(当然可以看成分段的整数)的消 息编码嵌入到椭圆群的点中(将明文嵌入椭 圆曲线)，实际中的转化方式多种多样，关 键的步骤与其正确性证明都涉及到复杂的 数学推导，可以参看相关文献。 19 4.4.4 椭圆曲线密码体制的安全性 椭圆曲线密码体制的安全性依赖于求解椭圆 曲线离散对数问题的困难性，即已知椭圆曲线上 的点P和kP计算k的困难程度。 下图比较了目前计算椭圆曲线对数和分解大数 因子的难度。可以看出，与RSA相比，ECC可以 用小得多的密钥取得与RSA相同的安全性。另外 ，在密钥大小相等时，ECC与RSA所需要的计算 量相当。 因此，在安全性相当的情况下，使用ECC比使 用RSA具有计算上的优势。两者都可以用于加解 密、密钥交换和数字签名。 20 椭圆曲线和RSA安全性的比较 密钥大小 150 205 234 MIPS年 3.8*1010 7.1*1018 1.6*1028 密钥大小 512 768 1024 1280 1536 2048 MIPS年 3*104 2*108 3*1011 1*1014 3*1016 3*1020 MIPS: 21 T=(p，a，b，G，n，h)。 （p 、a 、b 用来确定一条椭圆曲线，G为基点，n为点G的阶 ， h 是椭圆曲线上所有点的个数m与n相除的整数部分） 这几个参量取值的选择，直接影响了加密的安全性。参 量值一般要求满足以下几个条件： 1、p 当然越大越安全，但越大，计算速度会变慢，200位 左右可以满足一般安全要求； 2、pnh； 3、pt1 (mod n)，1t20； 4、4a3+27b20 (mod p)； 5、n 为素数； 6、h4。 密码学描述一条Fp上的椭圆曲线用到六个参量： 22 椭圆曲线在软件注册保护的应用 将公开密钥算法作为软件注册算法的好处是Cracker很 难通过跟踪验证算法得到注册机。 软件作者按如下方法制作注册机（也称为签名过程） 1、选择一条椭圆曲线Ep(a,b)，和基点G； 2、选择私有密钥nA（nAn，n为G的阶），利用基点G 计算公开密钥PA=nAG； 3、产生一个随机整数k（kn），计算点R=kG； 4、将用户名和点R的坐标值x,y作为参数，计算SHA（ Secure Hash Algorithm 安全散列算法，类似于MD5）值， 即Hash=SHA(username,x,y)； 5、计算snk Hash *nA (mod n) 6、将sn和Hash作为用户名username的序列号 23 软件验证过程如下： （软件中存有椭圆曲线Ep(a,b)，和基点G，公开密钥PA） 1、从用户输入的序列号中，提取sn以及Hash； 2、计算点Rsn*G+Hash*PA ( mod p )，如果sn、Hash正 确，其值等于软件作者签名过程中点R(x,y)的坐标，因为 snk-Hash*nA （mod n） 所以 sn*G + Hash*PA =(k-Hash*nA)*G+Hash*PA =kG-Hash*nAG+Hash*PA =kG- Hash*PA+ Hash*PA =kG=R ； 3、将用户名和点R的坐标值x,y作为参数，计算 H