椭圆曲线密码快速算法.pdf

文档介绍：西北大学硕士学位论文摘要1985年Koblitz和Miller分别提出在椭圆曲线上构造密码系统的思想,即椭圆曲线密码(EEC)(【1】【2】)。它的基本思想是找到一条安全的椭圆曲线,将明文通过编码嵌入到椭圆曲线中,。由于求解该离散对数的难度与求解乘法群上的离散对数的难度相同,所以在椭圆曲线上可构造出相对安全的密码系统。又因为在与其它密码系统具有相同安全性的前提下,椭圆曲线密码的运算速度快,所产生的密钥较小,节省带宽,所以它被广泛地应用于智能卡、无线电设备等。椭圆曲线密码体制中,最耗时的运算是倍点运算也就是椭圆曲线上的点与一个整数的乘法运算。由于椭圆曲线密码系统的执行主要是计算倍点,因此椭圆曲线密码系统所消耗的时间主要是倍点运算所消耗掉的时间。因此倍点运算的快速计算是椭圆曲线密码快速实现的关键。本文提出三种计算倍点艘的算法,使倍点计算效率在原有的基础上有所提高。递推算法首先推导出计算二倍点的递推公式,其次推导出计算任意倍点的递推公式,将这两个公式结合起来得到有效的计算胛的递推算法。递推算法比逐点法效率提高38%,([14])提出的对任意一个正整数的已知的r元展开的修改算法,。%∞的窗口方法进行改进,使得改进后的∞一NAF递推法比宽度为∞的窗口方法效率提高l—1。6—+一607以上。9+907关键字:椭圆曲线密码,倍点算法,算法分析,Koblitz曲线西北大学硕士学位论文AbstraetIn1985,alvedefinedovgrafinitefieldtocOustructcryptosystem,urveseryptography(ECC)([1][2]).urveandbyencoding,irce,,80ispossibletocons缸',urvecryptogramhavesmallerkeysize,bandwidthsavings,andfasterimplementations,soitwasemployedextensivelyinsmartcardandwirelessdevicesand∞,,,,putingmultiplepoiot,,%,([14]),deriveasigneddigitrepresentationofminimalH